현대의 소프트웨어 개발 환경에서 알고리즘은 매우 중요한 역할을 합니다. 코딩 테스트에서
자주 출제되는 문제 중 하나인 위상 정렬에 대해 알아보겠습니다. 위상 정렬은 방향 그래프(directed graph)에서
노드의 간선 방향을 고려하여 모든 노드를 정렬하는 기법입니다. 이는 주로 작업 간의 종속성을
표현할 때 유용하게 사용됩니다.
문제 설명
다음과 같은 입력을 받는 문제를 살펴보겠습니다. 주어진 작업들 간의 선후 관계가 주어졌을 때,
모든 작업을 완료하기 위한 순서를 위상 정렬을 이용하여 출력하는 문제입니다.
예시 문제:
N개의 작업이 있으며, 각 작업은 1부터 N까지의 번호로 식별됩니다.
M개의 간선이 주어지며, 이를 통해 작업 간의 선후 관계를 정의합니다.
아래 주어진 작업을 위상 정렬을 통해 처리할 수 있는지와 그 순서를 출력하세요.
입력 예제:
6 6
6 5
5 4
4 3
2 5
3 1
1 2
출력 예제:
6 5 4 3 1 2
문제 풀이 과정
1. 문제 이해하기
먼저, 위상 정렬이 무엇인지, 그리고 이 문제에서 요구하는 것이 무엇인지 이해해야 합니다.
위상 정렬은 방향 그래프의 각 노드를 정렬하여, 모든 간선의 방향을 존중하며 나열하는 과정입니다.
주어진 간선의 방향에 따라 각 작업이 선행되어야 하는 순서를 정의할 수 있습니다.
위상 정렬이 가능한 그래프는 사이클이 없는 그래프(Directed Acyclic Graph, DAG)여야 합니다.
2. 문제 해결 접근법
문제를 해결하는 기본적인 접근법은 다음과 같습니다:
- 주어진 작업들 간의 선후 관계를 그래프로 표현합니다.
- 각 작업의 진입 차수(indegree)를 계산합니다.
- 진입 차수가 0인 작업을 큐에 추가합니다.
- 큐에서 작업을 하나씩 꺼내어 처리하면서 해당 작업과 연결된 작업의 진입 차수를 감소시킵니다.
진입 차수가 0이 된 작업은 다시 큐에 추가합니다. - 모든 작업이 처리될 때까지 반복합니다.
- 위상 정렬의 결과를 출력합니다.
3. 자바스크립트 구현
이제 위 단계에 따라 자바스크립트 코드를 구현해 보겠습니다.
아래의 코드에서는 주어진 입력을 기반으로 위상 정렬을 수행합니다.
function topologicalSort(N, edges) {
const graph = {};
const indegree = new Array(N + 1).fill(0);
const result = [];
// 그래프 생성 및 진입 차수 초기화
edges.forEach(([u, v]) => {
if (!graph[u]) graph[u] = [];
graph[u].push(v);
indegree[v]++;
});
const queue = [];
// 진입 차수가 0인 작업 추가
for (let i = 1; i <= N; i++) {
if (indegree[i] === 0) {
queue.push(i);
}
}
while (queue.length > 0) {
const node = queue.shift();
result.push(node);
// 연결된 노드의 진입 차수를 감소시킴
if (graph[node]) {
graph[node].forEach(neighbor => {
indegree[neighbor]--;
if (indegree[neighbor] === 0) {
queue.push(neighbor);
}
});
}
}
// 위상 정렬이 가능했는지를 확인.
if (result.length !== N) {
return "사이클이 존재합니다.";
}
return result;
}
// 입력 예제
const N = 6;
const edges = [
[6, 5],
[5, 4],
[4, 3],
[2, 5],
[3, 1],
[1, 2],
];
console.log(topologicalSort(N, edges));
4. 코드 설명
위 코드를 통해 위상 정렬을 구현하는 방법을 설명하겠습니다.
-
그래프 구성:
주어진 간선 리스트를 기반으로 그래프를 인접 리스트 형태로 생성합니다.
각 노드의 진입 차수를 기록하여, 노드가 얼마나 많은 간선에 의해 의존되고 있는지를 나타냅니다. -
진입 차수가 0인 노드 찾기:
모든 노드를 살펴보며 진입 차수가 0인 노드를 큐에 추가합니다. -
BFS를 통한 처리:
큐에서 노드를 하나씩 꺼내어 처리하고, 그 노드에 연결된 노드의 진입 차수를 감소시킵니다.
만약 진입 차수가 0이 되는 노드가 있다면, 그것을 큐에 추가하세요. -
결과의 길이 확인:
모든 작업이 처리된 경우에 결과 배열의 길이가 노드의 수와 동일해야 하며,
이 경우 위상 정렬이 성공적으로 수행된 것입니다.
5. 결론 및 배운 점
위상 정렬은 작업 간의 의존 관계를 바탕으로 특정 순서로 작업을 수행해야 할 때 매우 유용합니다.
이 강좌를 통해 위상 정렬의 기본 아이디어와 자바스크립트로의 구현 방법을 익혔습니다.
다양한 데이터 구조와 알고리즘을 활용할 수 있는 기회를 갖는 것은 코딩 테스트에서의 성공적인 성과에 필수적입니다.
실제 문제에서 위상 정렬을 요구하는 경우는 다양하기 때문에,
각 문제의 특성을 이해하고 올바른 데이터 구조와 알고리즘으로 해결하는 것이 중요합니다.
계속해서 다양한 문제를 연습하여 능력을 향상시키세요!