탐색·정렬·그래프 알고리즘의 선택

이어 읽을 선수 설명: 추상 자료형과 구현을 구분한다, 시간·공간 복잡도와 Big-O. 각 설명의 전제를 확인한 뒤 아래의 단계 풀이와 자체 문제를 연결한다.

빠른 알고리즘보다 전제가 맞는 알고리즘이 먼저다

전화번호부가 정렬되어 있다면 가운데를 보고 절반씩 버리는 이진 탐색을 쓸 수 있다. 정렬되어 있지 않으면 절반을 버리는 근거가 깨져 정답을 보장하지 못한다. 정렬된 연결리스트처럼 중간 위치로 바로 이동할 수 없는 구조에서는 같은 비교 규칙의 정확성을 유지할 수 있지만, 중간 원소에 도달하는 순회비용 때문에 배열의 O(log n) 접근시간을 그대로 주장할 수 없다. 도로의 최소비용을 찾을 때도 모든 간선 가중치가 0 이상이면 Dijkstra 알고리즘을 검토할 수 있지만, 음수 가중치가 섞이면 이미 확정한 경로가 나중에 더 짧아질 수 있다.

이 절의 핵심은 알고리즘 이름을 많이 외우는 것이 아니다. 문제의 입력·출력·제약을 고정하고, 자료구조와 알고리즘의 전제를 확인한 뒤, 정당성과 시간·공간 비용을 함께 설명하는 것이다. 전제를 빠뜨린 O(log n)이나 최단경로라는 표현은 기술사 답안에서 완전한 논거가 되지 못한다.

한 문장으로 말하면

알고리즘 선택은 같은 문제를 푸는 절차 중 입력 전제와 정답 조건을 만족하면서 허용된 시간·공간·입출력 비용 안에 드는 방법을 고르는 일이다.

탐색은 원하는 항목의 존재나 위치를 찾고, 정렬은 모든 항목을 정해진 순서로 재배열하며, 그래프 알고리즘은 정점과 간선으로 표현한 관계에서 방문순서·의존순서·최소비용을 구한다. 세 종류 모두 무엇이 정답인가, 왜 그 결과가 정답인가, 어떤 입력에서 비용이나 정답이 깨지는가를 답해야 한다.

정확히 말하면: 알고리즘은 계약과 불변조건으로 설명한다

알고리즘의 계약은 입력조건, 출력조건, 종료조건과 허용 자원을 명시한다. 예를 들어 탐색 결과는 찾은 위치뿐 아니라 없음도 포함해야 하며, 중복 키가 있으면 첫 위치·마지막 위치·아무 위치 중 무엇을 반환할지 정해야 한다. 정렬 결과는 다음 두 조건을 동시에 만족해야 한다.

1. 인접한 두 항목이 정한 비교규칙에 맞게 순서대로 놓인다.
2. 출력은 입력 항목의 순열이다. 즉 항목이 사라지거나 새로 생기지 않는다.

작동 중 계속 참인 성질을 불변조건이라고 한다. 이진 탐색에서는 찾는 값이 존재한다면 아직 버리지 않은 구간 안에 있다, 병합에서는 이미 출력한 앞부분은 정렬되어 있고 두 입력의 처리된 항목만 정확히 포함한다가 예다. 종료할 때 불변조건과 종료조건을 결합하면 정답을 설명할 수 있다.

복잡도는 입력 크기에 따라 연산 횟수와 추가 공간이 증가하는 모양이다. Big-O 하나만 쓰지 말고 평균·최악·상환 중 어떤 값인지, 비교·이동·간선검사·저장장치 입출력 중 무엇을 센 것인지 밝혀야 한다.

전체에서 어디인가: 문제에서 검증까지

문제의 입력·출력·정답·규모·지연·메모리를 명세하고, 정렬 여부·직접 접근·그래프 방향·가중치·순환을 확인한다. 탐색·정렬·순회·위상순서·최단경로 후보마다 불변조건·종료로 정당성을, 시간·공간·입출력으로 비용을 각각 검토한다. 대표·경계·반례 입력을 검증한 뒤 선택 근거와 실패 시 대안을 설명한다. 아래의 기존 단계별 선택 절차가 이 전체 과정을 풀어 쓴다.

정당성과 성능은 별도 질문이다. 답이 틀리는 알고리즘은 아무리 빨라도 후보가 아니고, 정답을 내더라도 자원 한도를 넘으면 운영 가능한 해법이 아니다.

먼저 알아둘 것

앞 절에서 배열은 위치에 직접 접근하고, 연결리스트는 참조를 따라 이동하며, 큐와 스택은 꺼내는 순서를 제한한다고 배웠다. 그래프는 인접 행렬이나 인접 리스트로 표현하고, 우선순위 큐는 현재 우선순위가 가장 높은 항목을 꺼내므로 같은 절차도 표현에 따라 비용이 달라진다. 시간·공간 복잡도는 이 연산비용을 입력 크기에 따라 비교하며, 그래프에서는 정점 수를 V, 간선 수를 E로 표시한다.

탐색 전에 검색계약을 고정한다

값을 찾는다는 말만으로는 구현을 결정할 수 없다. 다음 질문을 먼저 고정한다.

• 키가 정확히 같은 항목을 찾는가, 범위나 가장 가까운 값을 찾는가.
• 데이터는 정렬되어 있는가, 검색 중에도 변경되는가.
• 중복 키에서 첫 항목·마지막 항목·모든 항목 중 무엇을 반환하는가.
• 배열처럼 위치로 바로 이동할 수 있는가, 순차적으로만 읽을 수 있는가.
• 한 번 검색하는가, 정렬·인덱스 구축비용을 회수할 만큼 반복 검색하는가.

정렬되지 않은 작은 목록에서 항목을 한 번만 찾는다면 선형 탐색이 단순하다. 반복 검색을 위해 먼저 정렬하면 검색은 빨라질 수 있지만 정렬비용과 갱신 때 순서 유지비용이 생긴다. 키–값 정확 조회가 중심이면 해시도 후보지만, 이 절에서는 순서 전제를 이용하는 선형·이진 탐색을 비교한다.

선형 탐색: 앞에서부터 하나씩 확인한다

선형 탐색은 배열이나 목록의 항목을 한 번에 하나씩 검사한다. 현재 항목이 키와 같으면 계약에 맞는 위치를 반환하고, 끝까지 없으면 없음을 반환한다. 정렬 전제가 없고 순차 접근만 가능한 입력에서도 동작한다.

입력은 [7, 3, 9, 3], 찾을 키는 9다.

앞에서 i-1까지 검사했는데 찾지 못했다면, 찾는 항목은 아직 보지 않은 i 이후에만 있을 수 있다는 것이 불변조건이다. 모든 항목을 검사하고도 일치가 없으면 목록 안에 키가 없다고 결론 낼 수 있다.

첫 항목이 답이면 O(1)에 끝날 수 있지만, 마지막에 있거나 없으면 n개를 확인하므로 최악 시간은 O(n)이다. 추가 위치변수만 쓰는 전형적 반복 구현의 추가 공간은 O(1)이다. 중복 키에서 모든 위치를 반환하면 첫 일치에서 멈추지 않아야 한다.

이진 탐색: 정렬된 구간을 절반씩 버린다

이진 탐색은 정렬된 배열에서 검색 구간의 가운데 항목과 키를 비교한다. 키가 더 작으면 오른쪽 절반을, 더 크면 왼쪽 절반을 버리고 남은 구간에서 반복한다. 구간이 비면 없음이다.

값 16이 남는 실제 인덱스 범위 · 상태 따라가기

배열 [2,5,8,12,16,23,31]에서 값 16을 찾는다. 모든 단계에서 탐색 범위·mid·판정의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

넓은 화면과 모바일에서 같은 관계를 각각의 배치로 읽을 수 있습니다.

위치는 0부터 세며 low..high 양 끝을 포함한다. 첫 가운데는 위치 3의 12여서 4..6만 남긴다. 다음 가운데는 위치 5의 23여서 4..4만 남긴다. 마지막 위치 4의 16이 일치한다. 아래 띠의 가로 위치는 배열의 실제 위치이며 시간축이 아니다. 키 17의 없음 종료와 경계 갱신식은 바로 아래 원문 설명과 대조한다.

보존한 원 가로 그림 설명의 실제 배열 위치 축을 위에서는 세로로 돌렸다. 세 띠는 같은 위치 축에서 양끝을 포함한 low..high 구간을 나타내며 점은 비교한 가운데 위치다. 첫 띠 0..6은 가운데 3의 12, 다음 띠 4..6은 가운데 5의 23, 마지막 띠 4..4는 가운데 4의 16과 대응한다. 키가 더 크면 low=가운데+1, 더 작으면 high=가운데−1로 이미 비교한 위치를 제외한다. 키 17은 16을 비교한 뒤 5..4가 되어 low>high로 끝난다. 위치 4와 5 사이에 별도 배열 칸이 있는 것은 아니다.

이 예의 조건

• 위치는 0부터 세며 low..high 양 끝을 포함한다. 첫 가운데는 위치 3의 12여서 4..6만 남긴다. 다음 가운데는 위치 5의 23여서 4..4만 남긴다. 마지막 위치 4의 16이 일치한다. 아래 띠의 가로 위치는 배열의 실제 위치이며 시간축이 아니다. 키 17의 없음 종료와 경계 갱신식은 바로 아래 원문 설명과 대조한다.
• 배열 2,5,8,12,16,23,31을 위치 0부터 6까지 세로로 배치한다. 각 위치의 높이는 64px이며 오른쪽 세 띠는 각각 양 끝을 포함한 0..6,4..6,4..4 범위를 같은 위치 축에 표시한다. 첫 가운데는 위치 3의 12, 둘째는 위치 5의 23, 셋째는 위치 4의 16이다. 띠 안의 점은 각 비교 위치다. 색뿐 아니라 번호와 경계를 통해 남는 범위를 읽는다. 축은 배열의 실제 정수 위치이고 시간이나 값 사이의 연속축이 아니다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림 가로·세로 배치의 모든 라벨과 관계 설명

원 항목	설명·조건
원 항목24	설명·조건배열 2,5,8,12,16,23,31을 위치 0부터 6까지 세로로 배치한다. 각 위치의 높이는 64px이며 오른쪽 세 띠는 각각 양 끝을 포함한 0..6,4..6,4..4 범위를 같은 위치 축에 표시한다. 첫 가운데는 위치 3의 12, 둘째는 위치 5의 23, 셋째는 위치 4의 16이다. 띠 안의 점은 각 비교 위치다. 색뿐 아니라 번호와 경계를 통해 남는 범위를 읽는다. 축은 배열의 실제 정수 위치이고 시간이나 값 사이의 연속축이 아니다.

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
범위 0..6 배열 [2,5,8,12,16,23,31]에서 값 16을 찾는다.	값·보충 정보 탐색 범위: low0·high6 mid·판정: mid가 3인 위치의 값 12	변화·이유 정렬 조건과 양 끝 포함 범위를 고정한다.
12보다 큰 16 위치 3의 12가 작으므로 low=mid+1로 바꾼다.	값·보충 정보 탐색 범위: low4·high6 mid·판정: 다음 mid가 5인 위치의 값 23	변화·이유 0..3에는 16이 없어 제외한다.
23보다 작은 16 위치 5의 23이 크므로 high=mid−1로 바꾼다.	값·보충 정보 탐색 범위: low4·high4 mid·판정: 다음 mid가 4인 위치의 값 16	변화·이유 5..6은 제외하고 실제 남은 위치 4만 검사한다.
위치 4에서 일치 16이 같으므로 위치 4를 결과로 반환한다.	값·보충 정보 탐색 범위: 발견 위치 4 mid·판정: 16=16	변화·이유 키 17의 없음 종료는 원정보 설명의 별도 조건이다.

값 16이 남는 실제 인덱스 범위 · 상태 따라가기

배열 [2,5,8,12,16,23,31]에서 값 16을 찾는다. 모든 단계에서 탐색 범위·mid·판정의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

넓은 화면과 모바일에서 같은 관계를 각각의 배치로 읽을 수 있습니다.

위치는 0부터 세며 low..high 양 끝을 포함한다. 첫 가운데는 위치 3의 12여서 4..6만 남긴다. 다음 가운데는 위치 5의 23여서 4..4만 남긴다. 마지막 위치 4의 16이 일치한다. 아래 띠의 가로 위치는 배열의 실제 위치이며 시간축이 아니다. 키 17의 없음 종료와 경계 갱신식은 바로 아래 원문 설명과 대조한다.

보존한 원 가로 그림 설명의 실제 배열 위치 축을 위에서는 세로로 돌렸다. 세 띠는 같은 위치 축에서 양끝을 포함한 low..high 구간을 나타내며 점은 비교한 가운데 위치다. 첫 띠 0..6은 가운데 3의 12, 다음 띠 4..6은 가운데 5의 23, 마지막 띠 4..4는 가운데 4의 16과 대응한다. 키가 더 크면 low=가운데+1, 더 작으면 high=가운데−1로 이미 비교한 위치를 제외한다. 키 17은 16을 비교한 뒤 5..4가 되어 low>high로 끝난다. 위치 4와 5 사이에 별도 배열 칸이 있는 것은 아니다.

이 예의 조건

• 위치는 0부터 세며 low..high 양 끝을 포함한다. 첫 가운데는 위치 3의 12여서 4..6만 남긴다. 다음 가운데는 위치 5의 23여서 4..4만 남긴다. 마지막 위치 4의 16이 일치한다. 아래 띠의 가로 위치는 배열의 실제 위치이며 시간축이 아니다. 키 17의 없음 종료와 경계 갱신식은 바로 아래 원문 설명과 대조한다.
• 배열 2,5,8,12,16,23,31을 위치 0부터 6까지 세로로 배치한다. 각 위치의 높이는 64px이며 오른쪽 세 띠는 각각 양 끝을 포함한 0..6,4..6,4..4 범위를 같은 위치 축에 표시한다. 첫 가운데는 위치 3의 12, 둘째는 위치 5의 23, 셋째는 위치 4의 16이다. 띠 안의 점은 각 비교 위치다. 색뿐 아니라 번호와 경계를 통해 남는 범위를 읽는다. 축은 배열의 실제 정수 위치이고 시간이나 값 사이의 연속축이 아니다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림 가로·세로 배치의 모든 라벨과 관계 설명

원 항목	설명·조건
원 항목24	설명·조건배열 2,5,8,12,16,23,31을 위치 0부터 6까지 세로로 배치한다. 각 위치의 높이는 64px이며 오른쪽 세 띠는 각각 양 끝을 포함한 0..6,4..6,4..4 범위를 같은 위치 축에 표시한다. 첫 가운데는 위치 3의 12, 둘째는 위치 5의 23, 셋째는 위치 4의 16이다. 띠 안의 점은 각 비교 위치다. 색뿐 아니라 번호와 경계를 통해 남는 범위를 읽는다. 축은 배열의 실제 정수 위치이고 시간이나 값 사이의 연속축이 아니다.

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
범위 0..6 배열 [2,5,8,12,16,23,31]에서 값 16을 찾는다.	값·보충 정보 탐색 범위: low0·high6 mid·판정: mid가 3인 위치의 값 12	변화·이유 정렬 조건과 양 끝 포함 범위를 고정한다.
12보다 큰 16 위치 3의 12가 작으므로 low=mid+1로 바꾼다.	값·보충 정보 탐색 범위: low4·high6 mid·판정: 다음 mid가 5인 위치의 값 23	변화·이유 0..3에는 16이 없어 제외한다.
23보다 작은 16 위치 5의 23이 크므로 high=mid−1로 바꾼다.	값·보충 정보 탐색 범위: low4·high4 mid·판정: 다음 mid가 4인 위치의 값 16	변화·이유 5..6은 제외하고 실제 남은 위치 4만 검사한다.
위치 4에서 일치 16이 같으므로 위치 4를 결과로 반환한다.	값·보충 정보 탐색 범위: 발견 위치 4 mid·판정: 16=16	변화·이유 키 17의 없음 종료는 원정보 설명의 별도 조건이다.

불변조건은 키가 배열에 있다면 low부터 high 사이에 있다이다. 정렬규칙이 일관되므로 가운데보다 작은 키가 오른쪽에 없고, 큰 키가 왼쪽에 없다. 매 단계 구간 크기가 절반 수준으로 줄어 직접 접근 배열에서 최악 비교 횟수는 O(log n)이다.

위 예에서 위치는 0부터 세며 low..high는 양 끝을 포함한 구간이다. 가운데는 low + (high - low) / 2에서 나눗셈 결과의 소수 부분을 버려 정수 위치로 계산한다. 키가 가운데 값보다 크면 이미 비교한 가운데까지 제외하여 low=가운데+1, 작으면 high=가운데-1로 바꾼다. low>high가 되면 남은 위치가 없어 검색을 끝낸다.

같은 배열에서 키를 17로 바꾸면 어떻게 끝나는지 먼저 예상해 보자. 가운데 12 뒤에 구간 4..6, 가운데 23 뒤에 4..4, 가운데 16 뒤에 5..4가 되어 없음이다. 16과 23 사이를 더 찾아야 한다고 생각했다면 배열의 실제 정수 위치와 값 사이의 빈 공간을 혼동한 것이다. 마지막에 16을 다시 포함시키면 같은 구간을 반복할 수 있으므로 이미 검사한 가운데를 제외하는 규칙을 위 세 단계와 대조한다.

전제는 엄격하다. 검색 중 정렬순서가 깨지면 어느 절반을 버려도 되는지 알 수 없다. 비교함수가 항목마다 다른 규칙을 쓰거나 같음을 일관되게 판단하지 않아도 실패한다. 가운데 위치를 위 형태로 계산하면 큰 인덱스의 덧셈 넘침 위험을 줄일 수 있다. 중복 키의 첫 위치를 원하면 일치해도 왼쪽 구간을 더 탐색하도록 경계를 바꿔야 한다.

선형 탐색과 이진 탐색을 같은 축으로 비교한다

검색만 O(log n)이라고 해서 전체 처리가 항상 빠른 것은 아니다. 한 번 찾으려고 먼저 O(n log n) 정렬을 수행한다면 선형 탐색보다 총비용이 클 수 있다. 데이터 생성·갱신·반복 질의까지 경계를 넓혀 판단한다.

정렬은 순서뿐 아니라 항목 보존까지 증명한다

정렬 입력을 S, 출력을 S'라고 하자. 올바른 정렬은 S'의 인접 항목이 비교규칙에 맞고, S'가 S의 순열이어야 한다. 순서가 맞아 보여도 중복 항목 하나가 사라졌다면 정렬이 아니다.

비교규칙도 계약이다. 대소문자를 무시해 두 이름을 같은 키로 보는 것처럼 동등한 항목을 허용하는 규칙은 정상이며, 안정 정렬이면 그 동등류의 입력 상대순서를 보존한다. 동등한 항목까지 하나의 결정적 순서로 출력해야 한다면 시간이나 입력순번 같은 동률 규칙을 추가한다. 반면 a < b, b < c인데 c < a가 되는 비추이 규칙이나 호출할 때마다 결과가 바뀌는 비교자는 정렬의 정답을 보장하지 못하고 구현에 따라 오류나 미종료를 일으킬 수 있다.

성능 비교에는 비교 횟수 외에 항목 이동비용과 추가 공간을 넣는다. 큰 레코드 자체를 옮기는 대신 참조나 키를 정렬할 수 있고, 메모리에 다 들어오지 않는 데이터는 저장장치의 순차 읽기·쓰기와 병합 횟수가 중요하다.

안정·제자리·외부정렬은 서로 다른 선택축이다

안정 정렬은 키가 같은 항목의 입력 상대순서를 출력에서도 보존한다. 부서 순으로 이미 정렬된 직원을 직급으로 안정 정렬하면 같은 직급 안에서 기존 부서 순서를 보존할 수 있다. 불안정 정렬도 키 순서는 맞을 수 있으므로 안정성은 정답 계약이 요구할 때 선택한다.

제자리 정렬은 원래 항목 저장공간을 결과 저장공간으로 사용하고 항목 수에 비례한 별도 배열을 요구하지 않는 방식이다. 추가 메모리가 작다는 장점이 있지만, 제자리 여부와 안정 여부는 같은 말이 아니다. 어떤 알고리즘의 변형과 구현 세부에 따라 둘 다 달라질 수 있으므로 알고리즘 이름만으로 단정하지 않는다.

외부정렬은 정렬 중 디스크 같은 외부 메모리를 사용하는 방식이다. 데이터가 주메모리보다 크면 메모리에 들어오는 조각을 각각 정렬한다. 이렇게 메모리에서 정렬해 외부 저장장치에 써 둔 정렬된 조각을 런(run)이라고 하며, 여러 런을 순차적으로 병합해 전체 결과를 만든다. 단순히 파일에서 읽고 결과를 파일에 쓰는 것만으로 외부정렬이 되는 것은 아니다. 무작위 접근보다 큰 블록의 순차 입출력을 늘려 저장장치 비용을 줄이는 것이 핵심이다.

병합 정렬: 나누고 정렬된 두 줄을 합친다

병합 정렬은 항목을 두 그룹으로 나누고, 각 그룹을 재귀적으로 정렬한 뒤, 두 정렬 결과의 맨 앞을 비교해 작은 항목부터 새 결과에 넣는다. 원소 하나인 그룹은 이미 정렬되어 있으므로 재귀가 끝난다.

서로 다른 두 정렬 결과를 비교하며 병합한다 · 상태 따라가기

[8,3,6,2]의 두 부분이 [3,8]과 [2,6]으로 정렬됐다. 모든 단계에서 병합 입력·출력의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

입력 [8, 3, 6, 2]를 두 부분으로 나누어 각 부분을 정렬한 뒤 [2, 3, 6, 8]을 얻는다. 한 원소까지의 재귀 호출은 각 정렬 단계 안에 접어 표현했다. 합류는 순서에 맞게 앞 항목을 비교하는 병합이며 두 배열의 단순 이어 붙이기가 아니다. 안정성·항목 보존 불변조건과 추가 공간은 원문 설명에 남아 있다.

이 예의 조건

• 입력 [8, 3, 6, 2]를 두 부분으로 나누어 각 부분을 정렬한 뒤 [2, 3, 6, 8]을 얻는다. 한 원소까지의 재귀 호출은 각 정렬 단계 안에 접어 표현했다. 합류는 순서에 맞게 앞 항목을 비교하는 병합이며 두 배열의 단순 이어 붙이기가 아니다. 안정성·항목 보존 불변조건과 추가 공간은 원문 설명에 남아 있다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림의 모든 대상과 설명

대상	원 설명
대상[8, 3, 6, 2]	원 설명원그림의 대상
대상[8, 3]	원 설명원그림의 대상
대상[6, 2]	원 설명원그림의 대상
대상[3, 8]	원 설명원그림의 대상
대상[2, 6]	원 설명원그림의 대상
대상[2, 3, 6, 8]	원 설명원그림의 대상

원그림의 모든 관계와 조건

연결	원 라벨·방향
연결[8, 3, 6, 2] → [8, 3]	원 라벨·방향분할 / 정방향 / 실선
연결[8, 3, 6, 2] → [6, 2]	원 라벨·방향분할 / 정방향 / 실선
연결[8, 3] → [3, 8]	원 라벨·방향재귀 정렬 / 정방향 / 실선
연결[6, 2] → [2, 6]	원 라벨·방향재귀 정렬 / 정방향 / 실선
연결[3, 8] → [2, 3, 6, 8]	원 라벨·방향비교 병합 / 정방향 / 실선
연결[2, 6] → [2, 3, 6, 8]	원 라벨·방향비교 병합 / 정방향 / 실선

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
두 부분 정렬 [8,3,6,2]의 두 부분이 [3,8]과 [2,6]으로 정렬됐다.	값·보충 정보 병합 입력: [3,8] / [2,6] 출력: []	변화·이유 각 입력의 정렬 조건이 병합 선택의 근거다.
작은 머리 2 3과 2 중 2를 선택하고 둘째 입력의 위치를 옮긴다.	값·보충 정보 병합 입력: [3,8] / [6] 출력: [2]	변화·이유 선택한 값만 소비한다.
다음 3·6 3과 6 중 3을, 다음 8과 6 중 6을 선택한다.	값·보충 정보 병합 입력: [8] / [] 출력: [2,3,6]	변화·이유 작은 머리 선택을 반복해 출력 순서를 지킨다.
나머지 8 둘째 입력 소진 뒤 남은 8을 붙인다.	값·보충 정보 병합 입력: [] / [] 출력: [2,3,6,8]	변화·이유 이미 정렬된 남은 부분을 보전한다.

서로 다른 두 정렬 결과를 비교하며 병합한다 · 상태 따라가기

[8,3,6,2]의 두 부분이 [3,8]과 [2,6]으로 정렬됐다. 모든 단계에서 병합 입력·출력의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

입력 [8, 3, 6, 2]를 두 부분으로 나누어 각 부분을 정렬한 뒤 [2, 3, 6, 8]을 얻는다. 한 원소까지의 재귀 호출은 각 정렬 단계 안에 접어 표현했다. 합류는 순서에 맞게 앞 항목을 비교하는 병합이며 두 배열의 단순 이어 붙이기가 아니다. 안정성·항목 보존 불변조건과 추가 공간은 원문 설명에 남아 있다.

이 예의 조건

• 입력 [8, 3, 6, 2]를 두 부분으로 나누어 각 부분을 정렬한 뒤 [2, 3, 6, 8]을 얻는다. 한 원소까지의 재귀 호출은 각 정렬 단계 안에 접어 표현했다. 합류는 순서에 맞게 앞 항목을 비교하는 병합이며 두 배열의 단순 이어 붙이기가 아니다. 안정성·항목 보존 불변조건과 추가 공간은 원문 설명에 남아 있다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림의 모든 대상과 설명

대상	원 설명
대상[8, 3, 6, 2]	원 설명원그림의 대상
대상[8, 3]	원 설명원그림의 대상
대상[6, 2]	원 설명원그림의 대상
대상[3, 8]	원 설명원그림의 대상
대상[2, 6]	원 설명원그림의 대상
대상[2, 3, 6, 8]	원 설명원그림의 대상

원그림의 모든 관계와 조건

연결	원 라벨·방향
연결[8, 3, 6, 2] → [8, 3]	원 라벨·방향분할 / 정방향 / 실선
연결[8, 3, 6, 2] → [6, 2]	원 라벨·방향분할 / 정방향 / 실선
연결[8, 3] → [3, 8]	원 라벨·방향재귀 정렬 / 정방향 / 실선
연결[6, 2] → [2, 6]	원 라벨·방향재귀 정렬 / 정방향 / 실선
연결[3, 8] → [2, 3, 6, 8]	원 라벨·방향비교 병합 / 정방향 / 실선
연결[2, 6] → [2, 3, 6, 8]	원 라벨·방향비교 병합 / 정방향 / 실선

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
두 부분 정렬 [8,3,6,2]의 두 부분이 [3,8]과 [2,6]으로 정렬됐다.	값·보충 정보 병합 입력: [3,8] / [2,6] 출력: []	변화·이유 각 입력의 정렬 조건이 병합 선택의 근거다.
작은 머리 2 3과 2 중 2를 선택하고 둘째 입력의 위치를 옮긴다.	값·보충 정보 병합 입력: [3,8] / [6] 출력: [2]	변화·이유 선택한 값만 소비한다.
다음 3·6 3과 6 중 3을, 다음 8과 6 중 6을 선택한다.	값·보충 정보 병합 입력: [8] / [] 출력: [2,3,6]	변화·이유 작은 머리 선택을 반복해 출력 순서를 지킨다.
나머지 8 둘째 입력 소진 뒤 남은 8을 붙인다.	값·보충 정보 병합 입력: [] / [] 출력: [2,3,6,8]	변화·이유 이미 정렬된 남은 부분을 보전한다.

병합 중 출력된 앞부분은 정렬되어 있고, 두 입력에서 꺼낸 항목을 빠짐없이 한 번씩 포함한다는 불변조건을 유지한다. 두 부분이 올바르게 정렬되어 있다면 작은 앞 항목을 택하는 동작으로 전체 순서와 항목 보존을 만족한다.

분할 단계 수는 log n 수준이고 각 단계에서 전체 n개를 병합하므로 시간은 Θ(n log n)이다. 배열의 전형적 구현은 병합용 O(n) 추가공간을 사용한다. 키가 같을 때 왼쪽 입력 항목을 먼저 내보내면 안정성을 보존할 수 있다. 순차 병합이 가능해 외부정렬과 연결하기 좋지만, 추가 저장공간과 데이터 복사 비용을 계산해야 한다.

퀵 정렬: 피벗을 기준으로 제자리 후보를 나눈다

퀵 정렬은 피벗 하나를 고르고 나머지 항목을 피벗보다 작은 쪽과 큰 쪽으로 분할한 뒤 각 부분을 재귀적으로 정렬한다. 분할이 끝나면 피벗의 최종 위치 또는 피벗과 같은 구간이 정해지고, 서로 섞일 필요가 없는 작은 부분문제로 바뀐다.

이 표는 원문의 논리적 분할 결과이며 특정 제자리 분할 구현의 모든 교환 순서를 가정하지 않는다.

분할의 불변조건은 왼쪽 확정구간은 피벗보다 작거나 같고, 오른쪽 확정구간은 피벗보다 크거나 같으며, 가운데 미검사 구간만 남았다처럼 구현 계약에 맞게 세운다. 분할이 항목을 잃거나 복제하지 않고 두 부분이 재귀적으로 정렬되면 전체도 정렬된다.

분할이 대체로 균형이면 실행시간은 보통 O(n log n)이고, 배열 안에서 교환하는 전형적 구현은 큰 보조 배열이 필요 없다. 그러나 피벗이 계속 최솟값이나 최댓값에 가까우면 한쪽 크기가 거의 줄지 않아 최악 Θ(n²)가 된다. 재귀 스택도 균형 분할에서는 O(log n) 수준이지만 심한 편향에서는 O(n)까지 커질 수 있다. 전형적 제자리 분할은 안정성을 보장하지 않으며, 같은 키가 매우 많을 때는 세 구간 분할 같은 변형을 검토한다.

병합 정렬과 퀵 정렬을 같은 축으로 비교한다

이 표는 특정 라이브러리 구현의 보증표가 아니다. 안정성·추가공간·피벗 선택·작은 구간 처리 방식은 구현에 따라 달라질 수 있으므로 실제 답안에는 전형적 구현이라는 전제를 붙인다.

여기까지의 결론

탐색은 정렬 여부·직접 접근·조회 횟수에 따라 선형과 이진 방식을 고른다. 정렬은 순서와 입력 보존을 함께 만족해야 하며 안정성, 보조공간, 피벗 편향, 외부메모리 조건을 분리해서 본다. 이제 같은 원칙을 정점과 간선으로 이루어진 그래프 문제에 적용한다.

그래프 알고리즘은 간선의 의미부터 다르게 읽는다

그래프 G=(V,E)를 받으면 다음을 먼저 적는다.

• 방향 그래프인가, 무방향 그래프인가.
• 간선은 단순 연결인가, 비용·거리·시간 같은 가중치를 갖는가.
• 자기루프·중복간선·순환을 허용하는가.
• 한 시작점의 도달성, 모든 정점 방문, 의존순서, 최소 간선 수, 최소 가중치 합 중 무엇을 구하는가.
• 인접 리스트와 인접 행렬 중 어떤 표현을 쓰며 V와 E의 최댓값은 얼마인가.

방문표시도 정답의 일부다. 순환 그래프에서 방문 여부를 기록하지 않으면 같은 정점을 끝없이 다시 넣을 수 있다. 여러 연결요소 전체를 처리하려면 한 시작점 탐색이 끝난 뒤 아직 방문하지 않은 정점에서 다시 시작해야 한다.

BFS: 가까운 층부터 큐로 넓힌다

너비우선 탐색(Breadth-First Search, BFS)은 시작 정점을 방문표시하고 큐에 넣는다. 큐에서 정점을 하나 꺼내 아직 방문하지 않은 이웃을 표시하고 거리와 선행자를 기록한 뒤 큐 뒤에 넣는다. 먼저 들어온 정점을 먼저 처리하므로 시작점에서 간선 하나 떨어진 정점, 두 개 떨어진 정점 순으로 층이 넓어진다.

같은 간선 수의 거리 층을 먼저 방문한다 · 상태 따라가기

원문의 발견 즉시 방문표시 규칙으로 A를 등록하고 큐에 넣는다. 모든 단계에서 발견·방문표시·큐·처리 순서의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

넓은 화면과 모바일에서 같은 관계를 각각의 배치로 읽을 수 있습니다.

원문의 무가중치 예시 A–B, A–C, B–D, B–E, C–F를 그대로 배치했다. 선은 인접 관계이고 방향 간선을 새로 가정하지 않는다. A를 시작으로 B·C가 거리 1, D·E·F가 거리 2다. 큐 방문순서 A, B, C, D, E, F는 이 예시의 인접 열거 순서에 따른다. 모든 그래프가 트리라는 뜻은 아니며 아래 DFS 설명은 같은 그래프를 사용한다.

A–B와 A–C, B–D와 B–E, C–F의 실제 선을 유지한다. 위아래 배치는 BFS의 거리 층을 보여 주기 위한 것이며 선 자체에 방향이나 가중치를 추가하지 않는다. 같은 층 안에서 먼저 꺼내는 정점은 이웃을 열거한 순서에 따라 달라질 수 있다. 이 예시의 BFS 큐는 A,B,C,D,E,F이고, 바로 이어지는 원문 DFS는 같은 간선을 사용해 A,B,D,E,C,F로 방문한다. DFS 첫 경로의 최단성을 새로 주장하지 않는다.

이 예의 조건

• 원문의 무가중치 예시 A–B, A–C, B–D, B–E, C–F를 그대로 배치했다. 선은 인접 관계이고 방향 간선을 새로 가정하지 않는다. A를 시작으로 B·C가 거리 1, D·E·F가 거리 2다. 큐 방문순서 A, B, C, D, E, F는 이 예시의 인접 열거 순서에 따른다. 모든 그래프가 트리라는 뜻은 아니며 아래 DFS 설명은 같은 그래프를 사용한다.
• A–B,A–C,B–D,B–E,C–F 다섯 무방향 인접 관계를 그대로 연결한다. A는 거리 0, B와 C는 거리 1, D와 E와 F는 거리 2로 실제 층을 이룬다. 선에는 화살촉을 붙이지 않아 방향 간선을 새로 가정하지 않는다. 예시의 이웃 열거 순서를 따르는 큐 방문순서는 A,B,C,D,E,F다. 모든 일반 그래프가 트리라는 뜻은 아니다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림 가로·세로 배치의 모든 라벨과 관계 설명

원 항목	설명·조건
원 항목13	설명·조건A–B,A–C,B–D,B–E,C–F 다섯 무방향 인접 관계를 그대로 연결한다. A는 거리 0, B와 C는 거리 1, D와 E와 F는 거리 2로 실제 층을 이룬다. 선에는 화살촉을 붙이지 않아 방향 간선을 새로 가정하지 않는다. 예시의 이웃 열거 순서를 따르는 큐 방문순서는 A,B,C,D,E,F다. 모든 일반 그래프가 트리라는 뜻은 아니다.

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
A 시작 원문의 발견 즉시 방문표시 규칙으로 A를 등록하고 큐에 넣는다.	값·보충 정보 발견·방문표시: 발견 A·거리 0 큐·처리 순서: 큐 A·처리 전	변화·이유 큐에 넣기 전에 방문표시하여 같은 정점을 중복 삽입하지 않는다.
A 처리·B와 C 발견 A를 꺼내 이웃 B와 C에 즉시 방문표시·거리 1을 기록하고 넣는다.	값·보충 정보 발견·방문표시: 발견 A B C·B와 C 거리 1 큐·처리 순서: 큐 B C·처리 A	변화·이유 아직 처리하지 않은 B와 C도 이미 발견·방문표시된 정점이다.
B 처리·D와 E 발견 B를 꺼내 이웃 D와 E에 즉시 방문표시·거리 2를 기록한다.	값·보충 정보 발견·방문표시: 발견 A B C D E 큐·처리 순서: 큐 C D E·처리 A B	변화·이유 B-D·B-E의 부모 관계를 기록하며 이미 발견한 정점은 다시 넣지 않는다.
C 처리·F 발견 C를 꺼내 C-F로 F를 발견하고 즉시 방문표시한다.	값·보충 정보 발견·방문표시: 발견 A B C D E F 큐·처리 순서: 큐 D E F·처리 A B C	변화·이유 거리 1의 B와 C를 거리 2 후보보다 먼저 처리하되 방문표시는 발견할 때 한다.
남은 처리 완료 D·E·F를 차례로 꺼내 처리하여 큐가 빈다.	값·보충 정보 발견·방문표시: 발견 A B C D E F 큐·처리 순서: 큐 비움·처리 A B C D E F	변화·이유 발견 집합과 처리 순서는 뜻이 다르며 무방향 이웃 재방문을 막는다.

같은 간선 수의 거리 층을 먼저 방문한다 · 상태 따라가기

원문의 발견 즉시 방문표시 규칙으로 A를 등록하고 큐에 넣는다. 모든 단계에서 발견·방문표시·큐·처리 순서의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

넓은 화면과 모바일에서 같은 관계를 각각의 배치로 읽을 수 있습니다.

원문의 무가중치 예시 A–B, A–C, B–D, B–E, C–F를 그대로 배치했다. 선은 인접 관계이고 방향 간선을 새로 가정하지 않는다. A를 시작으로 B·C가 거리 1, D·E·F가 거리 2다. 큐 방문순서 A, B, C, D, E, F는 이 예시의 인접 열거 순서에 따른다. 모든 그래프가 트리라는 뜻은 아니며 아래 DFS 설명은 같은 그래프를 사용한다.

A–B와 A–C, B–D와 B–E, C–F의 실제 선을 유지한다. 위아래 배치는 BFS의 거리 층을 보여 주기 위한 것이며 선 자체에 방향이나 가중치를 추가하지 않는다. 같은 층 안에서 먼저 꺼내는 정점은 이웃을 열거한 순서에 따라 달라질 수 있다. 이 예시의 BFS 큐는 A,B,C,D,E,F이고, 바로 이어지는 원문 DFS는 같은 간선을 사용해 A,B,D,E,C,F로 방문한다. DFS 첫 경로의 최단성을 새로 주장하지 않는다.

이 예의 조건

• 원문의 무가중치 예시 A–B, A–C, B–D, B–E, C–F를 그대로 배치했다. 선은 인접 관계이고 방향 간선을 새로 가정하지 않는다. A를 시작으로 B·C가 거리 1, D·E·F가 거리 2다. 큐 방문순서 A, B, C, D, E, F는 이 예시의 인접 열거 순서에 따른다. 모든 그래프가 트리라는 뜻은 아니며 아래 DFS 설명은 같은 그래프를 사용한다.
• A–B,A–C,B–D,B–E,C–F 다섯 무방향 인접 관계를 그대로 연결한다. A는 거리 0, B와 C는 거리 1, D와 E와 F는 거리 2로 실제 층을 이룬다. 선에는 화살촉을 붙이지 않아 방향 간선을 새로 가정하지 않는다. 예시의 이웃 열거 순서를 따르는 큐 방문순서는 A,B,C,D,E,F다. 모든 일반 그래프가 트리라는 뜻은 아니다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림 가로·세로 배치의 모든 라벨과 관계 설명

원 항목	설명·조건
원 항목13	설명·조건A–B,A–C,B–D,B–E,C–F 다섯 무방향 인접 관계를 그대로 연결한다. A는 거리 0, B와 C는 거리 1, D와 E와 F는 거리 2로 실제 층을 이룬다. 선에는 화살촉을 붙이지 않아 방향 간선을 새로 가정하지 않는다. 예시의 이웃 열거 순서를 따르는 큐 방문순서는 A,B,C,D,E,F다. 모든 일반 그래프가 트리라는 뜻은 아니다.

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
A 시작 원문의 발견 즉시 방문표시 규칙으로 A를 등록하고 큐에 넣는다.	값·보충 정보 발견·방문표시: 발견 A·거리 0 큐·처리 순서: 큐 A·처리 전	변화·이유 큐에 넣기 전에 방문표시하여 같은 정점을 중복 삽입하지 않는다.
A 처리·B와 C 발견 A를 꺼내 이웃 B와 C에 즉시 방문표시·거리 1을 기록하고 넣는다.	값·보충 정보 발견·방문표시: 발견 A B C·B와 C 거리 1 큐·처리 순서: 큐 B C·처리 A	변화·이유 아직 처리하지 않은 B와 C도 이미 발견·방문표시된 정점이다.
B 처리·D와 E 발견 B를 꺼내 이웃 D와 E에 즉시 방문표시·거리 2를 기록한다.	값·보충 정보 발견·방문표시: 발견 A B C D E 큐·처리 순서: 큐 C D E·처리 A B	변화·이유 B-D·B-E의 부모 관계를 기록하며 이미 발견한 정점은 다시 넣지 않는다.
C 처리·F 발견 C를 꺼내 C-F로 F를 발견하고 즉시 방문표시한다.	값·보충 정보 발견·방문표시: 발견 A B C D E F 큐·처리 순서: 큐 D E F·처리 A B C	변화·이유 거리 1의 B와 C를 거리 2 후보보다 먼저 처리하되 방문표시는 발견할 때 한다.
남은 처리 완료 D·E·F를 차례로 꺼내 처리하여 큐가 빈다.	값·보충 정보 발견·방문표시: 발견 A B C D E F 큐·처리 순서: 큐 비움·처리 A B C D E F	변화·이유 발견 집합과 처리 순서는 뜻이 다르며 무방향 이웃 재방문을 막는다.

큐에 있는 정점의 거리는 아직 처리하지 않은 정점 중 앞에서 뒤로 감소하지 않는다는 것이 핵심 불변조건이다. 따라서 모든 간선을 같은 한 단계로 세는 비가중 그래프에서는 어떤 정점을 처음 발견했을 때의 거리와 선행자 경로가 최소 간선 수 경로다.

인접 리스트를 사용하면 각 정점과 간선을 일정 횟수 확인해 시간은 O(V+E), 방문배열·큐·선행자 저장은 O(V) 추가공간이다. 인접 행렬의 모든 칸을 확인하면 O(V²)가 될 수 있다. 가중치가 서로 다른데 BFS 층수를 최소비용으로 해석하면 틀린 답이 된다.

DFS: 한 갈래를 끝까지 따라가고 되돌아온다

깊이우선 탐색(Depth-First Search, DFS)은 현재 정점에서 아직 방문하지 않은 이웃으로 계속 들어가고, 더 갈 곳이 없으면 이전 정점으로 되돌아온다. 재귀 호출의 호출 스택이나 명시적 스택으로 구현할 수 있다. 한 시작점에서 닿지 않는 정점이 있으면 새 시작점을 잡아 DFS를 다시 하는데, 각 시작점에서 생긴 탐색트리들을 모은 것을 탐색 숲(search forest)이라 한다. 정점을 처음 만난 발견시각과 모든 이웃 처리를 마친 종료시각을 기록하면 이 탐색 숲과 간선 관계를 분석할 수 있다.

위 BFS 도식의 같은 인접 관계에서 깊이를 먼저 방문한다.

방문순서 A, B, D, E, C, F와 되돌아가는 지점을 구분한다. 정점마다 모든 이웃이 처리될 때까지 재귀 호출이나 명시적 스택이 경로를 보존한다.

현재 스택에는 시작점부터 현재 정점까지 아직 처리가 끝나지 않은 경로가 놓인다는 것이 핵심이다. 방향 그래프에서 현재 스택에 있는 정점으로 되돌아가는 간선을 만나면 순환의 근거가 된다. 종료시각의 역순은 순환이 없는 방향 그래프의 위상순서를 만드는 방식에도 사용할 수 있다.

인접 리스트에서 시간은 O(V+E), 방문표시와 스택은 O(V)다. 매우 긴 사슬에서는 재귀 깊이가 V까지 커져 호출 스택 한도를 넘을 수 있으므로 명시적 스택을 검토한다. DFS의 첫 발견 경로는 일반 그래프의 최소 간선 수나 최소 가중치 경로를 보장하지 않는다.

BFS와 DFS를 같은 축으로 비교한다

둘의 Big-O가 같아도 방문순서와 메모리 모양이 다르다. 필요한 산출물이 가까운 순서인지 깊은 의존구조와 되돌아오기인지로 선택한다.

위상정렬: 모든 선행자를 앞에 둔다

위상정렬은 방향 비순환 그래프(Directed Acyclic Graph, DAG)의 정점에 선형 순서를 부여해 모든 간선 u → v에서 u가 v보다 앞에 오게 한다. 부분순서를 하나의 실행 가능한 전체 순서로 펼치는 것이며, 가능한 결과가 여러 개일 수 있다.

진입차수 방식은 각 정점으로 들어오는 간선 수를 센다. 진입차수가 0인 정점을 큐에서 꺼내 결과에 넣고, 그 정점에서 나가는 간선을 제거한 효과로 후속 정점의 진입차수를 줄인다. 새로 0이 되면 큐에 넣는다.

추가 선행 간선까지 계산한 배포 순서 · 상태 따라가기

설계부터 가능하며 구현·시험·배포는 선행 조건을 기다린다. 모든 단계에서 준비·완료·남은 의존의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

설계→구현→시험→배포에 설계→시험 간선도 존재한다. 각 본문 숫자는 초기 진입차수다. 설계 완료 후 시험 차수는 아직 1이며 구현까지 끝나야 0이 된다. 추가 선행 간선 때문에 시험을 먼저 실행하지 않는다. 초기 차수, 갱신 과정, 순환 판정은 원문의 완성 풀이와 함께 읽는다.

이 예의 조건

• 설계→구현→시험→배포에 설계→시험 간선도 존재한다. 각 본문 숫자는 초기 진입차수다. 설계 완료 후 시험 차수는 아직 1이며 구현까지 끝나야 0이 된다. 추가 선행 간선 때문에 시험을 먼저 실행하지 않는다. 초기 차수, 갱신 과정, 순환 판정은 원문의 완성 풀이와 함께 읽는다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림의 모든 대상과 설명

대상	원 설명
대상설계	원 설명초기 진입차수 0
대상구현	원 설명초기 진입차수 1
대상시험	원 설명초기 진입차수 2
대상배포	원 설명초기 진입차수 1

원그림의 모든 관계와 조건

연결	원 라벨·방향
연결설계 → 구현	원 라벨·방향선행 / 정방향 / 실선
연결구현 → 시험	원 라벨·방향선행 / 정방향 / 실선
연결시험 → 배포	원 라벨·방향선행 / 정방향 / 실선
연결설계 → 시험	원 라벨·방향추가 선행 / 정방향 / 실선

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
선행 설계 설계부터 가능하며 구현·시험·배포는 선행 조건을 기다린다.	값·보충 정보 준비·완료: 설계 준비 남은 의존: 설계→구현·시험	변화·이유 진입차수 0인 노드만 선택한다.
설계 제거 설계를 완료하고 나가는 간선을 제거한다.	값·보충 정보 준비·완료: 설계 완료·구현 준비 남은 의존: 구현→시험 유지	변화·이유 시험은 구현 선행 조건도 있어 아직 준비 상태가 아니다.
구현 뒤 시험 구현 완료로 시험의 남은 조건이 없어져 시험을 진행한다.	값·보충 정보 준비·완료: 구현·시험 완료 남은 의존: 시험→배포	변화·이유 모든 선행이 완료돼야 다음 노드가 준비 상태가 된다.
배포 가능 시험 완료 뒤 배포가 가능해진다.	값·보충 정보 준비·완료: 배포 준비·완료 남은 의존: 남은 의존 없음	변화·이유 노드 배열 순서를 실행 근거로 쓰지 않는다.

추가 선행 간선까지 계산한 배포 순서 · 상태 따라가기

설계부터 가능하며 구현·시험·배포는 선행 조건을 기다린다. 모든 단계에서 준비·완료·남은 의존의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

설계→구현→시험→배포에 설계→시험 간선도 존재한다. 각 본문 숫자는 초기 진입차수다. 설계 완료 후 시험 차수는 아직 1이며 구현까지 끝나야 0이 된다. 추가 선행 간선 때문에 시험을 먼저 실행하지 않는다. 초기 차수, 갱신 과정, 순환 판정은 원문의 완성 풀이와 함께 읽는다.

이 예의 조건

• 설계→구현→시험→배포에 설계→시험 간선도 존재한다. 각 본문 숫자는 초기 진입차수다. 설계 완료 후 시험 차수는 아직 1이며 구현까지 끝나야 0이 된다. 추가 선행 간선 때문에 시험을 먼저 실행하지 않는다. 초기 차수, 갱신 과정, 순환 판정은 원문의 완성 풀이와 함께 읽는다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림의 모든 대상과 설명

대상	원 설명
대상설계	원 설명초기 진입차수 0
대상구현	원 설명초기 진입차수 1
대상시험	원 설명초기 진입차수 2
대상배포	원 설명초기 진입차수 1

원그림의 모든 관계와 조건

연결	원 라벨·방향
연결설계 → 구현	원 라벨·방향선행 / 정방향 / 실선
연결구현 → 시험	원 라벨·방향선행 / 정방향 / 실선
연결시험 → 배포	원 라벨·방향선행 / 정방향 / 실선
연결설계 → 시험	원 라벨·방향추가 선행 / 정방향 / 실선

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
선행 설계 설계부터 가능하며 구현·시험·배포는 선행 조건을 기다린다.	값·보충 정보 준비·완료: 설계 준비 남은 의존: 설계→구현·시험	변화·이유 진입차수 0인 노드만 선택한다.
설계 제거 설계를 완료하고 나가는 간선을 제거한다.	값·보충 정보 준비·완료: 설계 완료·구현 준비 남은 의존: 구현→시험 유지	변화·이유 시험은 구현 선행 조건도 있어 아직 준비 상태가 아니다.
구현 뒤 시험 구현 완료로 시험의 남은 조건이 없어져 시험을 진행한다.	값·보충 정보 준비·완료: 구현·시험 완료 남은 의존: 시험→배포	변화·이유 모든 선행이 완료돼야 다음 노드가 준비 상태가 된다.
배포 가능 시험 완료 뒤 배포가 가능해진다.	값·보충 정보 준비·완료: 배포 준비·완료 남은 의존: 남은 의존 없음	변화·이유 노드 배열 순서를 실행 근거로 쓰지 않는다.

큐에 들어온 정점은 아직 출력하지 않은 정점 가운데 자신보다 먼저 와야 할 선행자가 없다는 불변조건을 가진다. 모든 정점을 출력했다면 각 간선의 선행조건을 만족한다. 출력 수가 V보다 작고 진입차수 0 정점이 더 없다면 남은 부분에 순환이 있어 위상순서가 존재하지 않는다. 인접 리스트의 시간은 O(V+E), 저장공간은 O(V)에 그래프 공간을 더한다.

Dijkstra 알고리즘: 가장 작은 잠정거리를 확정한다

Dijkstra 알고리즘은 모든 간선 가중치가 0 이상인 가중 방향 그래프에서 한 시작점으로부터 다른 모든 정점까지 최소 가중치 합을 구한다. 시작점 거리는 0, 나머지는 무한대로 두고, 잠정거리가 가장 작은 미확정 정점을 꺼내 확정한다. 그 정점 u에서 v로 가는 간선을 거친 후보거리 dist[u]+w(u,v)가 현재 dist[v]보다 작으면 거리와 선행자를 바꾸는데, 이 비교·갱신을 완화(relaxation)라고 한다.

간선 u → v의 가중치가 w일 때 dist[u] + w < dist[v]이면 dist[v]와 선행자를 갱신한다. 우선순위 큐에는 더 짧아진 후보를 넣는다. 같은 정점의 오래된 후보가 나중에 나오면 현재 거리와 다른지 확인해 건너뛸 수 있다.

직접 간선보다 두 단계를 거친 경로가 짧다 · 상태 따라가기

S의 거리 0으로 시작해 A 거리 4·B 거리 1을 후보로 둔다. 모든 단계에서 확정 집합·후보 거리의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

원문의 가중치 S→A 4, S→B 1, B→A 2, B→T 6, A→T 1을 그대로 표시했다. 정점 본문은 최종 거리이고 T의 값은 4다. 경로 S→B→A→T가 1+2+1=4가 된다. 모든 가중치는 0 이상이며 dist[u] + w < dist[v]일 때 완화한다. 부모·낡은 큐 항목·가중치 변형의 계산은 바로 아래 원문 표를 보존했다.

이 예의 조건

• 원문의 가중치 S→A 4, S→B 1, B→A 2, B→T 6, A→T 1을 그대로 표시했다. 정점 본문은 최종 거리이고 T의 값은 4다. 경로 S→B→A→T가 1+2+1=4가 된다. 모든 가중치는 0 이상이며 dist[u] + w < dist[v]일 때 완화한다. 부모·낡은 큐 항목·가중치 변형의 계산은 바로 아래 원문 표를 보존했다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림의 모든 대상과 설명

대상	원 설명
대상S	원 설명거리 0
대상B	원 설명거리 1
대상A	원 설명거리 3
대상T	원 설명거리 4

원그림의 모든 관계와 조건

연결	원 라벨·방향
연결S → B	원 라벨·방향1 / 정방향 / 실선
연결S → A	원 라벨·방향4 / 정방향 / 실선
연결B → A	원 라벨·방향2 / 정방향 / 실선
연결B → T	원 라벨·방향6 / 정방향 / 실선
연결A → T	원 라벨·방향1 / 정방향 / 실선

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
S 출발 S의 거리 0으로 시작해 A 거리 4·B 거리 1을 후보로 둔다.	값·보충 정보 확정 집합: S 확정 후보 거리: A 거리 4 / B 거리 1	변화·이유 가장 작은 미확정 거리를 다음으로 선택한다.
B 완화 거리 1인 B를 확정하면 A는 1+2=3, T는 1+6=7로 갱신된다.	값·보충 정보 확정 집합: S·B 확정 후보 거리: A 거리 3 / T 거리 7	변화·이유 기존 A의 거리 4보다 작아 바꾸며 경로를 보전한다.
A 완화 거리 3인 A에서 T를 3+1=4로 갱신한다.	값·보충 정보 확정 집합: S·B·A 확정 후보 거리: T 거리 4	변화·이유 기존 T의 거리 7보다 짧은 경로를 찾았다.
T 확정 T의 최단 거리는 4이며 경로는 S-B-A-T다.	값·보충 정보 확정 집합: S·B·A·T 후보 거리: 최종 T 거리 4	변화·이유 원문의 음이 아닌 가중치 조건을 유지한다.

직접 간선보다 두 단계를 거친 경로가 짧다 · 상태 따라가기

S의 거리 0으로 시작해 A 거리 4·B 거리 1을 후보로 둔다. 모든 단계에서 확정 집합·후보 거리의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

원문의 가중치 S→A 4, S→B 1, B→A 2, B→T 6, A→T 1을 그대로 표시했다. 정점 본문은 최종 거리이고 T의 값은 4다. 경로 S→B→A→T가 1+2+1=4가 된다. 모든 가중치는 0 이상이며 dist[u] + w < dist[v]일 때 완화한다. 부모·낡은 큐 항목·가중치 변형의 계산은 바로 아래 원문 표를 보존했다.

이 예의 조건

• 원문의 가중치 S→A 4, S→B 1, B→A 2, B→T 6, A→T 1을 그대로 표시했다. 정점 본문은 최종 거리이고 T의 값은 4다. 경로 S→B→A→T가 1+2+1=4가 된다. 모든 가중치는 0 이상이며 dist[u] + w < dist[v]일 때 완화한다. 부모·낡은 큐 항목·가중치 변형의 계산은 바로 아래 원문 표를 보존했다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림의 모든 대상과 설명

대상	원 설명
대상S	원 설명거리 0
대상B	원 설명거리 1
대상A	원 설명거리 3
대상T	원 설명거리 4

원그림의 모든 관계와 조건

연결	원 라벨·방향
연결S → B	원 라벨·방향1 / 정방향 / 실선
연결S → A	원 라벨·방향4 / 정방향 / 실선
연결B → A	원 라벨·방향2 / 정방향 / 실선
연결B → T	원 라벨·방향6 / 정방향 / 실선
연결A → T	원 라벨·방향1 / 정방향 / 실선

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
S 출발 S의 거리 0으로 시작해 A 거리 4·B 거리 1을 후보로 둔다.	값·보충 정보 확정 집합: S 확정 후보 거리: A 거리 4 / B 거리 1	변화·이유 가장 작은 미확정 거리를 다음으로 선택한다.
B 완화 거리 1인 B를 확정하면 A는 1+2=3, T는 1+6=7로 갱신된다.	값·보충 정보 확정 집합: S·B 확정 후보 거리: A 거리 3 / T 거리 7	변화·이유 기존 A의 거리 4보다 작아 바꾸며 경로를 보전한다.
A 완화 거리 3인 A에서 T를 3+1=4로 갱신한다.	값·보충 정보 확정 집합: S·B·A 확정 후보 거리: T 거리 4	변화·이유 기존 T의 거리 7보다 짧은 경로를 찾았다.
T 확정 T의 최단 거리는 4이며 경로는 S-B-A-T다.	값·보충 정보 확정 집합: S·B·A·T 후보 거리: 최종 T 거리 4	변화·이유 원문의 음이 아닌 가중치 조건을 유지한다.

가중치가 음수가 아니므로 현재 잠정거리가 가장 작은 정점보다 더 짧은 경로가 미확정 정점을 거쳐 뒤늦게 나타날 수 없다. 이것이 확정 정점의 거리는 실제 최단거리라는 불변조건의 근거다. 음수 간선이 있으면 이 논리가 깨지므로 Dijkstra를 그대로 쓰면 안 된다.

단순 배열로 최소 정점을 고르는 구현은 O(V²)가 될 수 있다. 정점당 힙 항목 하나를 유지하고 decrease-key를 지원하는 인덱스형 이진 힙은 최대 V개를 저장하므로 O((V+E) log V)다. 반면 위에서 설명한 재삽입·오래된 항목 건너뛰기 구현은 성공한 완화마다 항목을 추가하여 최대 O(E+1)개를 보관할 수 있으므로 일반적으로 시간 O(V+(E+1) log(E+2)), 힙 공간 O(E+1)로 잡는다. 단순 그래프에서는 E=O(V²)여서 흔히 log E=O(log V)로 줄여 쓰지만, 중복간선을 제한하지 않는 모형에서는 그 경계를 자동 적용하지 않는다. 도달 불가능한 정점은 무한대 상태로 남으며, 실제 경로가 필요하면 완화 때 선행자를 저장해 역추적한다.

작은 그래프의 거리·부모 갱신

방향간선 S→A:4, S→B:1, B→A:2, B→T:6, A→T:1라고 하자. 표의 A:3/B는 A의 잠정거리 3, 부모 B를 뜻한다.

재삽입형 힙에는 예전 후보 A:4, T:7도 남는다. A:4를 꺼내면 현재 dist[A]=3과 다르므로 확정·완화하지 않고 버린다. 최종 T에서 부모를 거슬러 T←A←B←S를 얻고 이를 뒤집으면 경로 S→B→A→T, 비용 1+2+1=4다. 잠정거리 4가 처음 발견됐다는 사실과 그 정점이 유효 최솟값으로 확정됐다는 사실을 구분한다.

이제 B→A의 가중치를 2에서 5로만 바꾸면 A와 T의 최종 거리·부모는 어떻게 되는가? B를 확정한 뒤 A의 후보는 1+5=6으로 기존 4보다 크므로 A는 4/S를 유지한다. T는 먼저 7/B가 되지만 다음 A를 확정하면 4+1=5<7이므로 5/A로 바뀐다. 최종 경로는 S→A→T, 비용 5다. 새 후보가 생길 때마다 무조건 덮어쓰면 A를 6으로 잘못 바꾸므로, 위 표의 B 행에서 더 작을 때만 갱신한다는 조건을 복습한다. BFS라면 가중치를 보지 않고 S→A→T와 S→B→T를 모두 두 간선 경로로 본다. 간선 수와 가중치 합은 같은 질문이 아님을 이 결과로 확인할 수 있다.

그래프 질문을 알고리즘에 연결한다

최단경로라는 한 단어만 보고 알고리즘을 고르지 않는다. 무엇을 길이로 세는지, 가중치 부호와 그래프 방향, 한 출발점인지 모든 쌍인지부터 구분한다.

정당성은 불변조건과 종료를 한 줄로 잇는다

답안에서는 긴 수학증명 대신 전제 → 불변조건 → 한 단계가 성질을 보존하는 이유 → 종료 시 정답을 쓰면 정당성의 뼈대가 선다.

어디서 실패하는가

실패조건은 단순 주의사항이 아니다. 알고리즘을 사용할 수 있는 경계를 보여 주므로 정의와 복잡도 바로 뒤에 붙여 쓴다.

선택은 여덟 단계로 기록한다

답안을 쓸 때는 알고리즘의 명칭과 함께 선택 전제·작동원리·비용·검증을 연결해야 한다. 특히 복잡도 옆에는 자료구조, 최단 옆에는 거리의 정의와 가중치 전제, 정렬 옆에는 안정성·공간·외부메모리 여부를 둔다.

실무에서는 이렇게 보인다: 배포 분석 파이프라인

한 조직이 매일 생성되는 대용량 배포 기록과 서비스 의존관계를 처리한다고 하자.

• 기록 파일은 메모리보다 크고, 시각이 같으면 입력순서를 보존해 정렬해야 한다.
• 시간순 기록과 별도로 만든 배포번호순 색인에서 특정 배포번호를 반복 조회한다.
• 서비스 의존관계에 순환이 없는지 확인하고 가능한 배포순서를 만든다.
• 한 서비스 장애가 몇 단계 만에 전파될 수 있는지와, 복구시간 가중치 합이 가장 작은 경로를 각각 구한다.

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

큰 레코드는 시간키의 런을 안정 병합해 (시간, 입력순번) 스냅샷을 만든다. 여기서 (배포번호, 레코드위치)를 추출하고 번호키로 외부정렬해 별도 검색 인덱스를 만든다. 배포번호 질의는 번호 인덱스와 같은 키의 변경 영역을 함께 찾아 중복 제거한다. 다음 배치가 두 스냅샷에 변경을 반영한 뒤 변경 영역을 비운다. 시간순 파일에서 배포번호 이진 탐색을 하지 않는다.

외부정렬은 메모리 크기의 run을 만든 뒤 순차 병합하고, 동률에서 앞 run의 입력순서를 보존하도록 안정 규칙을 둔다. 이때 (시각, 입력순번)으로 정렬한 시간순 기록은 배포번호순이 아니므로 배포번호를 이진 탐색할 수 없다. 시간순 기록에서 (배포번호, 기록위치) 쌍을 추출하고 이를 배포번호순으로 다시 외부정렬한 별도 색인을 만든다. 고정된 번호순 색인에서는 배포번호를 이진 탐색하고, 중복번호가 가능하면 같은 번호의 첫·마지막 위치 또는 모든 기록위치를 반환한다는 계약을 정한다. 실시간 삽입은 두 스냅샷과 분리된 변경영역에 두되, 이 사례의 실시간 조회는 고정 색인과 배포번호로 찾는 변경영역 색인을 함께 조회한 뒤 결과를 합치고 중복을 제거한다. 배치 시점까지만 보이는 시스템이라면 반대로 조회 기준시각을 명시해야 하며, 다음 병합에서는 변경영역을 두 스냅샷에 반영하고 비운다.

의존 그래프는 DFS 또는 위상정렬 결과 수로 순환을 확인한다. 최소 전파단계는 간선 수를 세므로 BFS, 복구시간의 최소합은 모든 가중치가 0 이상인지 검증한 뒤 Dijkstra를 사용한다. 두 질문을 모두 최단경로라고 뭉개지 않는 것이 설계의 핵심이다.

시험에서는 어떻게 묻는가: 10점

다음 문제는 이 절의 학습목표를 확인하기 위해 만든 자체 제작 문제다. 실제 기출 원문이나 출제 사실을 뜻하지 않는다.

선형 탐색과 이진 탐색을 비교하고, 병합 정렬과 퀵 정렬의 작동원리·복잡도·안정성·공간 및 실패조건을 설명하시오.

두 쌍 모두 이름 나열이 아니라 전제를 묻는다. 이진 탐색은 정렬과 직접 접근, 병합 정렬은 정렬된 부분의 병합과 보조공간, 퀵 정렬은 피벗 분할과 편향 위험을 연결한다. 안정성과 제자리 여부를 알고리즘 이름만으로 절대화하지 말고 전형적 구현의 범위를 명시한다.

답안 목차·풀이·교정 근거 보기

10점 답안 목차

1. 탐색의 정의와 비교
   • 선형: 순차 확인, 정렬 불필요, 최악 O(n)
   • 이진: 정렬·직접 접근, 구간 절반 축소, O(log n)
2. 정렬의 정답조건과 작동원리
   • 순서와 순열 조건
   • 병합: 분할–정렬–병합 / 퀵: 피벗–분할–재귀
3. 복잡도·안정성·공간 비교
   • 병합 Θ(n log n)·보조공간 / 퀵 보통 O(n log n)·최악 Θ(n²)
4. 실패조건과 선택기준
   • 미정렬·중복계약, 메모리 밖 입력, 피벗 편향·재귀 깊이

10점 답안 도식

입력·출력 계약과 정렬·직접 접근·방향·가중치·순환 전제를 먼저 확인한다. 탐색은 선형·이진의 정렬/접근 조건, 정렬은 병합·퀵의 안정성/공간/최악 비용, 그래프는 BFS·DFS·위상정렬·Dijkstra의 방문·선행·비용 의미를 구분한다. 정당성의 불변조건·종료와 시간·공간·입출력 비용을 함께 논증하고 대표·경계·반례 검증 및 실패 시 대안을 답안에 넣는다. 이미 위에 있는 탐색·정렬 비교표와 각 그래프 예시를 답안의 근거로 사용한다.

10점 모범답안

탐색은 키의 존재나 위치를 구하는 절차다. 선형 탐색은 항목을 차례로 확인하므로 정렬 전제가 없고 순차 입력에도 적용되지만 최악 O(n)이다. 이진 탐색은 같은 비교규칙으로 정렬된 직접 접근 배열에서, 답이 있다면 남은 구간 안에 있다는 불변조건을 유지하며 절반을 버려 O(log n)이다. 미정렬 입력, 검색 중 변경, 경계 갱신과 중복 키의 첫·마지막 위치 계약을 누락하면 실패한다. 한 번 찾기 위해 먼저 정렬하는 비용까지 포함해 선택해야 한다.

올바른 정렬은 출력이 비교규칙에 맞고 입력의 순열이어야 한다. 병합 정렬은 둘로 나눈 부분을 재귀적으로 정렬하고 작은 앞 항목부터 병합한다. 시간은 Θ(n log n)이며 전형적 배열 구현은 O(n) 보조공간을 쓴다. 동률에서 왼쪽 항목을 먼저 선택하면 안정성을 보존할 수 있고 순차 병합이라 외부정렬에 적합하다.

퀵 정렬은 피벗을 기준으로 작은 쪽과 큰 쪽을 분할해 재귀 정렬한다. 균형 분할이면 보통 O(n log n)이고 전형적 배열 구현은 큰 보조배열이 없지만, 편향 분할이 반복되면 Θ(n²)와 O(n) 재귀 깊이가 될 수 있다. 전형적 제자리 분할은 불안정하다. 따라서 데이터 크기·분포, 안정성, 최악지연, 추가공간과 외부메모리 여부를 함께 비교하고, 실제 구현의 피벗·동률·공간 보장을 확인한다.

시험에서는 어떻게 묻는가: 25점

다음은 탐색·정렬·그래프 알고리즘을 종합해 설명하는 자체 제작 문제다. 실제 기출이나 공식 배점 기준을 뜻하지 않는다.

메모리보다 큰 배포기록과 방향성 서비스 의존그래프를 처리하는 분석체계를 설계하시오. 기록의 안정 정렬·반복 조회, 의존순서, 도달성, 최소 전파단계와 0 이상 복구시간의 최소경로를 지원해야 한다. 알고리즘·자료구조·복잡도·정당성·실패조건 및 검증방안을 설명하시오.

요구어가 설계이므로 알고리즘별 정의를 독립적으로 쓰고 끝내면 부족하다. 각 업무질문을 정확한 입력·출력으로 바꾸고, 시간순 외부정렬과 배포번호순 검색색인을 분리한 뒤 DFS/BFS–위상정렬–Dijkstra의 책임을 연결한다. 서로 다른 키로 정렬한 두 결과를 섞지 않는 것과 최소 전파단계·최소 복구시간 합의 차이가 핵심 논점이다.

답안 목차·풀이·교정 근거 보기

25점 답안 목차

1. 문제 경계와 알고리즘 계약
   • 기록 크기·안정성·조회시점, 그래프 방향·순환·가중치 의미
2. 기록 처리흐름
   • 시간키 run → 안정 다중병합 → 시간순 기록
   • 번호·기록위치 추출 → 번호키 외부정렬 → 번호순 색인 → 이진 탐색
3. 그래프 처리흐름
   • DFS 순환확인, 위상정렬 의존순서
   • BFS 최소 간선 수, Dijkstra 0 이상 가중치 최소합
4. 정당성과 복잡도
   • 알고리즘별 불변조건, n, V, E, 공간·입출력 비용
5. 실패조건과 통제
   • 정렬 갱신, 동률, 순환, 재귀 깊이, 음수 가중치, 도달 불가
6. 검증과 결론
   • 대표·경계·반례·최대규모 입력과 대안 선택기준

25점 답안 도식

큰 로그 처리의 두 키와 변경 병합 경계는 위의 시간순 스냅샷/번호순 인덱스 도식을 재사용한다. 시간키 안정 병합, (배포번호, 레코드위치) 추출, 번호키 외부정렬, 번호 인덱스 이진 탐색, 변경 영역 조회·중복 제거를 모두 포함한다.

별도 그래프 질문	선택과 전제
의존관계가 순환하는가	DFS로 순환을 검증한다.
선행을 만족하는 배포 순서는 무엇인가	DAG에서 위상정렬을 사용한다.
최소 의존 단계 수는 얼마인가	무가중치 간선 수를 BFS로 센다.
최소 복구시간은 얼마인가	복구시간 가중치가 0 이상일 때 Dijkstra를 사용한다.

원문의 아래 완성 풀이에서 각 정답 조건·경계 입력·불변조건·시간/공간/입출력 및 변경 일관성 검증을 확인한다.

25점 모범답안

대상은 하루 배포기록 파일과 방향성 서비스 의존그래프다. 시간순 보관 결과의 정렬키는 (시각, 입력순번)으로 두어 같은 시각의 입력 상대순서를 보존한다. 반복 조회에는 이 결과와 별도로 (배포번호, 기록위치)를 배포번호순으로 정렬한 검색색인을 사용한다. 그래프 간선 u → v는 u가 v보다 먼저 배포되어야 함으로 정의한다. 전파단계는 간선 수, 복구시간 경로는 0 이상 간선 가중치 합으로 서로 다른 거리계약을 둔다.

기록이 메모리보다 크므로 (시각, 입력순번) 기준 run을 만들고 안정 다중병합하여 시간순 기록을 만든다. 각 병합 출력은 정렬되어 있고 처리한 입력을 정확히 포함한다는 불변조건으로 순서와 항목 보존을 설명한다. 이어 시간순 기록을 한 번 순회해 (배포번호, 기록위치) 쌍을 만들고, 번호 기준 run과 다중병합으로 별도 검색색인을 만든다. 이 번호순 색인은 답이 남은 구간 안에 있다는 불변조건으로 배포번호를 O(log n)에 이진 탐색하며, 중복번호 계약에 따라 같은 키 구간의 위치들을 반환한다. 두 외부정렬의 비교작업은 각각 전형적으로 O(n log n) 범주지만 실제 설계에서는 run 수·병합 차수·블록 입출력 횟수와 두 결과의 저장공간을 별도로 산정한다. 실시간 추가분은 두 정렬 스냅샷을 깨뜨리지 않도록 배포번호로 조회 가능한 별도 변경영역에 둔다. 조회는 고정 색인과 변경영역을 함께 검색해 결과를 합치고 중복을 제거하며, 다음 병합 때 변경분을 두 스냅샷에 반영한다.

그래프는 희소성을 고려해 인접 리스트로 표현한다. DFS는 현재 스택으로 되돌아가는 간선을 통해 순환을 확인하고, 깊은 사슬의 재귀 한도를 피하려면 명시적 스택을 쓴다. 순환이 없으면 진입차수 0 정점을 큐로 처리하는 위상정렬로 모든 간선의 선행 정점이 앞서는 배포순서를 만든다. 결과 정점 수가 V보다 작으면 순환으로 판정한다. 두 절차는 O(V+E)다.

장애 시작점의 최소 전파단계는 BFS로 구한다. 큐가 거리 비감소 순서로 처리되므로 첫 발견 거리가 최소 간선 수이며 시간 O(V+E), 추가공간 O(V)다. 복구시간 최소합은 모든 가중치가 0 이상인지 검증한 뒤 Dijkstra를 사용한다. 가장 작은 잠정거리 정점을 확정하고 간선을 완화하며, 이 설계에서는 정점당 한 항목의 인덱스형 이진 힙을 선택하여 시간 O((V+E) log V)를 사용한다. 재삽입형으로 바꾸면 오래된 항목 검사를 추가하고 중복간선을 포함한 E와 실제 힙 크기로 비용·공간을 다시 산정한다. 음수 가중치가 발견되면 확정 불변조건이 깨지므로 실행을 중단하고 요구에 맞는 다른 알고리즘을 선택한다.

검증에는 빈·한 건·동일 시각·중복번호·메모리 경계의 기록과, 고립 정점·긴 사슬·넓은 층·자기루프·순환·중복간선·도달 불가·0 및 음수 가중치 그래프를 포함한다. 정렬 결과의 순서·순열·안정성, 위상순서의 모든 간선 방향, BFS 거리, Dijkstra의 완화조건과 경로 가중치 합을 독립적으로 검사한다. 이처럼 같은 빠른 처리나 최단경로로 묶지 않고 정답 계약·자료표현·전제·불변조건·비용을 연결해야 설명 가능하고 복구 가능한 분석체계가 된다.

근거와 현행성

정의·전제·대표 복잡도는 미국 국립표준기술연구소(National Institute of Standards and Technology, NIST) 정보기술연구소의 Dictionary of Algorithms and Data Structures에서 다음 공식 항목을 대조했다. 기준 확인일은 2026-08-31이다.

• 탐색: linear search, binary search
• 정렬: sort, stable, in-place sort, external sort, merge sort, quicksort
• 그래프: breadth-first search, depth-first search, topological sort, topological order, Dijkstra's algorithm, shortest path
• 자료구조 연결: queue, priority queue, graph

항목 주소는 NIST DADS의 https://xlinux.nist.gov/dads/HTML/ 아래에서 각각 linearSearch.html, binarySearch.html, sort.html, stable.html, inplacesort.html, externalsort.html, mergesort.html, quicksort.html, breadthfirst.html, depthfirst.html, topologicalSort.html, topologicalOrder.html, dijkstraalgo.html, shortestpath.html, queue.html, priorityque.html, graph.html이다. 사전 사이트 DOI는 10.18434/T4/1422485이다.

본문의 사례·비교표·불변조건 표·선택절차·문제·답안과 모든 도식은 원문 그림이나 표를 복제하지 않고 이 교재를 위해 독자적으로 작성했다. 복잡도는 명시한 자료표현과 전형적 구현에 대한 이론값이며 특정 언어·라이브러리·제품의 성능 보증이 아니다. 문제와 답안은 위 전제를 확인하기 위한 학습 예시이며 공식 채점 기준이 아니다.

30초 정리

1. 탐색·정렬·그래프 알고리즘은 이름보다 입력 전제, 정답 계약과 자료구조가 먼저다.
2. 이진 탐색은 정렬·직접 접근, 위상정렬은 DAG, Dijkstra는 0 이상 가중치라는 전제가 깨지면 보장도 깨진다.
3. 병합·퀵 정렬과 BFS·DFS는 Big-O만 비교하지 말고 안정성·공간·입출력·방문순서·최악 입력을 함께 비교한다.
4. 답안은 전제 → 작동원리 → 불변조건 → 복잡도 → 실패조건 → 검증으로 쓰면 정의에서 설계 논점까지 자연스럽게 연결된다.

다음 절에서는 분할정복·탐욕법·동적계획법·백트래킹이 문제를 작은 선택과 부분문제로 바꾸는 원리를 살펴본다.