읍내리 까치골

편의점에서 야간 근무 중 한산한 시간에 백준을 들어갔다가, 재미있는 문제를 풀어서 글을 써봅니다.어렵지는 않은데 접근법을 달리하는 것이 저난도 PS의 재미인 것 같습니다. https://www.acmicpc.net/problem/10989 정렬 문제인데 일반적인 vector와 sort()를 사용하는 접근법이 불가능한 문제입니다.그 이유는 입력 조건에 있습니다. 데이터 개수가 총 천만(10,000,000)건메모리 제한 8mb각 요소는 10,000 이하 자연수단순 계산으로 천만 건의 데이터를 8mb 안에 담는 것은 불가능합니다 int : 4byte * 10,000,000 = 40mbshrot: 2byte * 10,000,000 = 20mb byte형 또한 10mb에 달하는 것과 동시에 unsigned..

알고리즘을 공부할 때 그래프 구조에서 사용하는 대표적 알고리즘으로 DFS와 BFS가 있습니다. Depth First Search, Breadth First Search의 약자로 풀이하면 깊이 우선 탐색, 너비 우선 탐색이라 부를 수 있습니다. 두 알고리즘은 원리 자체는 동일하다 볼 수 있고, 단지 노드 탐색에 있어 Queue에서 넣고 꺼내는 순서의 차이가 있다고 생각하면 될 것 같습니다. BFS 하면 가장 많이 보이는 그림입니다. Root는 탐색을 시작하는 지점이며 레벨 0으로 간주하겠습니다. BFS의 동작은 해당 레벨의 노드를 모두 탐색하면 다음 레벨의 노드를 탐색합니다. 그림에서 보시다시피 레벨 1의 노드 두 개 (1, 2번)을 모두 탐색한 후에는 레벨 2로 넘어가서 탐색을 계속합니다. 이러한 원리로..