Algorithm/알고리즘 개념 정리21 [실전 알고리즘] 배열 정의와 성질 배열: 메모리 상에 원소를 연속하게 배치한 자료구조 배열의 성질 1. O(1)에 k번째 원소를 확인/변경 가능 2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 3. Cache hit rate가 높음 4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 기능과 구현 전체를 특정 값으로 초기화 시키기: algorithm 헤더의 fill 함수 fill(a,a+21,0); for(int i=0;i 2022. 8. 8. [실전 알고리즘] 기본적인 코드작성요령 코딩테스트 필요 역량 배경지식, 문제해결능력, 구현력 기초 코드 작성 요령 문제를 보고 시간 복잡도를 먼저 생각하자 정수 자료형 int, long long 형 생각하기 Integer Overflow 실수 자료형 float : 4 byte double : 8 byte 1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다 2. double에 long long 범위의 정수를 함부로 담으면 안된다 3. 실수를 비교할 때는 등호를 사용하면 안된다(오차범위 존재) STL과 함수 인자 구조체, STL 모두 값이 복사되어서 원본에 영향 주지 않음 표준 입출력 - 공백이 포함된 문자열을 받을 땐 getline을 쓰자. 대신 이건 type이 C++ string이어야 함 - scanf/printf와 다르게 c.. 2022. 8. 8. DFS, BFS 구현 방법 코드랑 원리를 아예 다 외워버리자!!! 출처: 강의 - 그래프 - 02. 그래프 순회: DFS와 BFS 1. DFS 구현: 재귀 이용 2. DFS : 스택 이용 함수 반환값( vector )은 dfs 함수에서 정점들이 방문한 순서를 정수형 벡터 형태로 반환 visited: 각각 정점 방문 여부 기록 visit_order: 각각 정점 방문 순서 기록 3. BFS : 큐 이용 #include #include #include #include #include using namespace std; const int N = 6; bool gVisited[N] = {}; void dfs_recursion(const vector& adj_list, int s) { if (gVisited[s]) return; gVisi.. 2022. 6. 16. 이전 1 2 3 4 다음
