1. 소수 구하기 알고리즘에 대하여 알고리즘을 공부하는 사람이라면 누구나 소수를 찾는 문제에 직면하게 된다. 가장 쉽게는 가능한 모든 수 범위에서 소수를 구할 수 있지만, 범위가 클 경우 시간이 매우 오래 걸린다. 그러므로 큰 범위에서 소수를 찾기 위해서는 효율적인 알고리즘을 사용할 필요가 있는데, 여기에서 알아볼 알고리즘이 '에라토스테네스의 체' 이다. 2. 에라토스테네스의 체 '에라토스테네스(Eratosthenes)의 체'란, 다음과 같이 반복적인 과정을 반복함으로서 주어진 범위에서의 소수를 찾는 것이다. (1) 2부터 시작해, 2를 제외하고 2의 배수들을 모두 제외시킨다. (2) 3부터 시작해, 3을 제외하고 3의 배수들을 모두 제외시킨다. (3) 4는 이미 제외되었으므로, 5부터 시작하고 5를 제..

1. N-Queen 문제란? N-Queen 문제란 다음과 같이 (N * N) 체스판이 있을 때, N개의 퀸을 체스판에 놓을 수 있는 경우를 찾는 문제이다. 이 문제는 백트래킹(Back-Tracking) 알고리즘을 적용하는 전형적인 문제이다. 2. Back-Tracking 이란? 말 그대로 가능하지 않는 노드는 배제하고 뒤로 돌아가는 형태이다. 어떤 노드에 방문했을 때, 그 노드가 '유망한' 노드가 아니라면 그 전 상태로 돌아가는 것이다. 3. 풀이 코드 #include using namespace std; int n, cnt = 0; bool cols[15], incs[29], decs[28]; void nQueen(int r) { if (r > n) { cnt++; return; } for (int i..

1. 벨만-포드 알고리즘이란? 그래프에서 최단 경로를 찾는 알고리즘은 여러 개가 있기 때문에, 알고리즘이 필요할 때에는 각 상황에 맞는 적절한 최단경로 알고리즘을 선택해야한다. 널리 사용되는 최단경로 알고리즘으로는 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘이 있다. 특히, 다익스트라 알고리즘과 벨만-포드 알고리즘은 굉장히 많이 쓰이기 때문에, 다음과 같이 비교하면 좋다. 벨만-포드 알고리즘은 간선 간의 가중치가 음수일 때 사용한다. 다익스트라 알고리즘은 양수 가중치만 가능하다. 다익스트라 알고리즘은 정점을 기준으로 최단 경로는 찾고, 벨만-포드 알고리즘은 간선을 기준으로 찾는다. 2. 벨만-포드 알고리즘의 조건 벨만-포드 알고리즘을 적용하기 위한 조건은 다음과 같다. 최단 경로는 ..

1. 다익스트라 알고리즘이란? 알고리즘을 공부하다보면 그래프를 공부하는 것이 굉장히 중요하다는 것을 자주 느낄 것이다. 그 중에서도 DFS, BFS와 더불어 가장 기초적이면서도 중요하게 생각되는 것이 최단경로 알고리즘일 것이고, 그 중에서도 다익스트라 알고리즘은 한 노드에서 다른 노드로의 최단 거리를 계산하는 중요한 알고리즘이다. 2. 간단하게 구현하기 소제목이 '간단하게 구현하기'인 만큼 문제가 있는 코드라고 생각할 지도 모르겠다. 실제로 아래와 같은 구현은 시간복잡도에서 조금은 '복잡한 구현' 보다 불리한 면이 있다. 하지만 다익스트라를 처음 공부할 때, 이해를 위해서 이와 같은 방법을 꼭 알고 있는 것이 좋다고 생각한다. 이것이 '간단하게 구현하기'인 이유는 3번에서 서술하겠다. 다른 알고리즘들이 ..

1. DFS / BFS 란? DFS와 BFS는 그래프에서 사용하는 대표적인 탐색 알고리즘이다. 방법의 차이는 있지만, 두 알고리즘 모두 한 노드에서부터 시작해 그 노드에 연결된 모든 노드를 탐색한다. DFS와 BFS가 무엇인지, 사용되는 기술은 무엇인지 알아보자. (1) DFS DFS는 'Depth First Search' 의 줄임말이다. 해석하자면 '깊이 우선 탐색' 이라고 할 수 있겠다. 즉, 한 노드를 집중적으로 파고들어, 그 노드에 연결된 노드를 깊숙이 들어가보는 것이다. 그렇기 때문에 DFS를 위해서는 스택이 사용된다. DFS를 C++과 STL로 구현한 코드는 다음과 같다. #include #include using namespace std; void DFS(vector v, int start)..