포스팅 목적 코딩 테스트 유형을 알아보고 유형별로 문제를 풀어봐야 대응할 수 있기 때문에 자주 출제되는 유형을 알고 빠르게 알고리즘을 선택하기 위해 포스팅 했습니다. (알고리즘) 코딩 테스트 유형 중요도 순 정리 완전 탐색 Exhaustive Search ( Brute Force ) 깊이 우선 탐색 ( DFS ) 넓이 우선 탐색 ( BFS ) 동적 프로그래밍 ( Dynamic Programming ) 그리디 ( Greedy ) 이진 탐색 ( Binary Search ) 파라메트릭 서치 ( Parametric Search ) 투 포인터 ( Two Pointer ) 유니온 파인드 ( Union-Find ) 크루스칼 프림 다익스트라 GCD (최대공약수, 최소공배수) 순열/조합 Backtracking Divid..

포스팅 목적 효율적인 탐색 알고리즘 중 하나인 이진 탐색을 코드 구현을 중심으로 알아봅니다. 이진 탐색의 정의 이진 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다. 예를 들어 특정 범위에 있는 숫자를 맞추는 UP & DOWN 게임을 할 때를 생각해 보면 가장 안정적이고 빠르게 답을 찾는 방법은 가장 한 숫자 범위 내에 있는 수 중에서 중간에 있는 숫자를 찍어서 그 숫자보다 큰지 작은지에 따라 다음 숫자를 결정하는 것 입니다. 이것이 이진 탐색입니다. 이진 탐색의 장단점 이진 탐색의 장점은 높은 효율성 입니다. 한 번 탐색할때 마다 탐색의 범위가 절반으로 줄어들기 때문에 시간 복잡도는 O(log N) 입니다. 앞의 정의에 나왔듯이 이진 탐색은 정렬되어 있는 배열에서만 사용할 ..

포스팅 목적 알고리즘의 유형 중 완전 탐색 기법과 그 유형에는 어떤 것이 있는지 알아봅니다. 완전 탐색이란? 완전 탐색(Exhaustive Search)이란 가능한 경우의 수를 모두 확인하는 방법으로, 무식하게 푼다는 뜻의 Brute-Force 라고도 합니다. 완전 탐색 기법 완전 탐색 기법을 사용하기 위해서는 가능한 경우의 수를 중복 없이 모두 확인할 수 있는 순회 방법들을 사용합니다. 단순한 중첩 for 문 : 순회하는데 별다른 기법 없이 모든 경우를 셀 수 있을 때 사용합니다. 재귀 함수 : 순열 (permutation), 조합 (combination) 과 같이 반복적인 작업을 구현할 때 사용합니다. 2^n 경우의 수 : 개수의 제한 없이 포함이나 선택 여부를 판단해야할 때 사용합니다. 완전 탐색 ..

1. DFS, BFS 그래프 탐색을 위해서는 DFS ( Depth-First Search, 깊이 우선 탐색 ), BFS ( Breadth-First Search, 너비 우선 탐색 ) 를 사용한다. 2. 그래프와 트리 비교 그래프는 노드와 노드를 잇는 (없을 수도 있지만) 간선을 가진 자료구조이며, 그 중 방향성이 있는 비순환 그래프가 트리이다. 3. DFS, BFS 시간복잡도 인접 리스트로 표현된 그래프 : O(N+E) 인접 행렬로 표현된 그래프 : O(N^2) 참고 : [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)