Gonna be my Best part

분할 정복 알고리즘은 이름에서 부터 알 수 있듯, 그대로 해결할 수 없는 문제를 거의 같은 크기의 여러개의 작은 문제로 분할하여 해결하는 방법이다. 또한 분할 정복 알고리즘의 경우 보통 재귀함수를 통해서 구현되지만 거의 같은 크기의 문제로 나눠야 한다는 것에 차이가 있다. 분할 정복의 구성 1) 주어진 문제를 여러개의 부분 문제로 나눈다. (divide) 2) 재귀 함수를 통해서 각각의 부분 문제를 해결한다 (conquer) 3) 각 부분의 문제의 답으로 부터 전체 문제의 답을 계산한다. (merge) 문할 정복의 적용을 위해 요구되는 특성 1) 문제를 둘 이상으로 나누는 자연스러운 방법이 있어야한다. 2) 부분 문제의 답을 조합하여 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다. 문할 정복 문..

깊이 우선 탐색(DFS)과 함께 가장 많이 사용되는 탐색 알고리즘으로, 다익스트라 알고리즘이나 최소 스패닝 트리 알고리즘 등의 기본이 되는 알고리즘. BFS알고리즘은 시작점에서 가까운 정점부터 순서대로 방문한다. BFS의 탐색 방법 BFS알고리즘의 경우엔 각 정점을 방문할 때마다 모든 인접한 정점들을 검사하고, 이중 아직 방문하지 않은 정점이 있는 경우 그 정점을 방문할 예정이라고 저장해둔다. 하나의 정점에 대해 모든 인접한 정점을 검사한 후에는 저장해둔 방문예정인 목록에서 다음 정점을 뽑아서 동일하게 그 정점의 인접한 정점을 검사하는 것을 반복한다. 그렇기 때문에 BFS에서 방문 순서는 정점의 목록에서 어떤 정점을 먼저 뽑는지에 의해 결정된다. 위의 그림의 예시에서 보면 시작점 a를 방문하고 나면 인접..

다이나믹 프로그래밍은 최적화를 연구하는 수학 이론에서 온 것이다. 큰 의미에서 분할 정복과 같은 접근방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고 이 답으로 부터 원래 문제에 대한 답을 계산해내기 때문이다. 그러나 차이점은 문제를 나누는 방식에서 생긴다. DP에서 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 여러번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있다. 출처: 알고리즘 문제해결 전략(구종만)

깊이 우선 탐색(DFS)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있는 경우 그 간선을 무조건 따라가는 것이다. 더이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 다시 뒤로 돌아간다. 깊이 우선 탐색이 이루어 지는 과정 정점 S에서 탐색을 시작하면 처음으로 간선 (S, A)를 탐색하게 된다. A를 아직 탐색한 적이 없으므로 A로 움직인다. 같은 원리로 B, C로 가는 경로를 찾으면 갈 길이 없음을 알 수 있다. A는 이미 방문하였으므로 (A, C)간선을 따라갈 수는 없기 때문이다. 따라서 마지막으로 따라온 간선인 (B, C)를 따라 다시 이동하여 B에서 다시 방문하지..

그리디 알고리즘은 원하는 답을 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어가는 방식이다. 이는 완전 탐색이나 동적 계획법과 유사하지만 각 단계마다 지금 당장 가장 좋은 방법만 선택한다. 즉 이 방식은 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다. 이렇게 문제를 해결하는 경우 최적해를 찾지못하는 경우가 많아진다. 그럼에도 그리디 알고리즘이 사용되는 경우는 아래 두 가지가 있다. 1) 그리디 알고리즘을 사용해도 항상 최적해를 구할 수 있느 문제를 만난 경우, 이는 동적 계획법보다 수행시간이 훨씬 빠르다. 2) 시간이나 공간적 제약으로 인해 다른 방식으로 최적해를 찾기 힘든 경우 대신 적당한 근사해를 찾는 것으로 타협할 수 있다. 이때 그리디 알고리즘은 최적은 ..

다익스트라 알고리즘은 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서 다른 정점들까지의 최단거리를 계산하는 알고리즘이다. BFS 알고리즘의 경우 가중치가 있는 그래프에선 너비우선 탐색을 그대로 적용하는데에는 어려움이 있다. 위의 예시처럼 BFS로 시작점 S에서 C까지의 최단 경로를 구하고자한다면, S->A->C->이런 순서로 탐색이 진행되어 S->C: 12의 거리가 된다. 그러나 실제 S에서 C로 가는 최단 거리 경로는 S->A->B->C로 A, B를 거쳐 도착하는 경로이다. 즉, 더 늦게 발견한 정점이더라도 더 먼저 방문할 수 있어야 하는데 BFS에서는 그게 되지 않아 실제 최단 경로를 찾는데에 문제가 생기는 것이다. 다익스트라 알고리즘 다익스트라 알고리즘은 큐를 사용하는 BFS와 달리 우선순위..

며칠 동안 c언어로 계속 코딩을 하다 보니 c++을 얼른 공부해서 표준 라이브러리를 사용해야겠다는 생각이 너무 절실했다. 같은 코드를 짜도 c++로 짜는 경우와 c로 짜는 경우 코드 길이의 차이가 어마어마하다ㅠㅠ 코딩 테스트에는 객체까지 사용할 필요는 없어 보여서 일단 절실한 표준 라이브러리 사용을 먼저 익히기로 하였다! 입출력 입출력의 경우엔 c에서 사용하던 scanf(), printf()를 그냥 그대로 사용할 것이다. 평소 c++의 입출력을 사용할 때 처럼 개행에 endl을 사용하면 출력 버퍼를 비우는 시간까지 소요되기 때문이다. c의 입출력 사용을 위해서는 또는 헤더를 추가해야한다. STL c를 사용하지 않고 c++을 사용함으로써 얻을 수 있는 가장 큰 이점은 아무래도 STL(표준 라이브러리)를 사..