코딩테스트
Brute-force
완전탐색, 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 완전 탐색 자체로는 알고리즘이라기 보다는 문제를 푸는 기법이며, 답으로 가능한 경우의 수가 많을 때 시간복잡도가 크므로 경우의 수가 작은지 파악하는 것이 중요하다. 완전 탐색 기법 단순 Brute-force 비트마스크 Bitmask 재귀 함수 순열 Permutation BFS / DFS 단순 Brute-force 어느 기법을 사용하지 않고 단순히 반복문과 조건문 등으로 모든 case 들을 만들어 답을 구하는 방법이다. 비트마스크 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식이며, 문제에서 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나 포함되지 않는 두 가지 선택으로 구성되는 경우 ..
Greedy
Greedy 그리디 알고리즘은 탐욕법이라고도 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 문제 풀 때 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제가 된다고 한다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰', '가장 작은'와 같은 기준을 제시해준다.
Backtracking
모든 경우의 수를 전부 고려하는 알고리즘이며, 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. DFS를 사용하여 만약 조건에 맞지 않으면 그 즉시 중단하고 이전으로 돌아가여 다시 확인하는 것을 반복하면서 원하는 조건을 찾는 알고리즘 한정 조건 백트래킹은 모든 경우의 수에서 한정 조건에 유망한 promissing 경우를 탐색하는 것이기 때문에 완전탐색기법인 BFS 나 DFS 모두 구현이 가능하다. 하지만 백트래킹의 특성에서 한정 조건에 부합하지 않다면 이전 수행으로 돌아와야하기 때문에 BFS보다 DFS가 구현에 편하다. 백트래킹을 구현할 때 가장 중요한 것은 한정 조건이다. 한정 조건을 걸어 완전 탐색에서 유망하지 않은 시도를 걸러내는 것이 백트래킹의 본질이다. n, m = map(int, inpu..
DFS/BFS
대표적인 그래프 탐색 알고리즘 DFS Depth-First Search 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이며, 스택 자료구조나 재귀 함수를 이용한다. 탐색 시작 노드로 재귀함수를 호출해 방문 처리한다. 현재 방문 노드에서 방문하지 않은 인접 노드가 하나라도 있으면 그 노드로 재귀함수를 호출해 방문 처리한다. 방문하지 않은 인접 노드가 없으면 해당 재귀 함수는 종료된다. 더 이상 2 - 3번의 과정을 수행할 수 없을 때까지 반복한다. # 재귀함수로 구현한 DFS def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in g..
DP
Dynamic Programming, 다이나믹 프로그래밍 : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방식의 알고리즘 메모리를 적절하게 사용하여 수행시간 효율성을 비약적으로 향상시킨다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 구현은 일반적으로 탑다운과 바텀업 방식으로 나뉜다. DP의 조건 1. 최적 부분 구조 Optimal Substructure : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 Overlapping Subproblem : 동일한 작은 문제를 반복적으로 해결해야 한다. 메모이제이션 한 번 계산한 결과를 메모리 공간에 기록해두고 다시 계산하지 않는 방법 같은..
