Dutch National Flag

 

❒ Description

---

[LeetCode#75] Sort Colors 문제를 풀면서 알게된 Dutch National Flag 알고리즘을 정리해보자.

 

 

 

 

 

❒ DNF 알고리즘

---

1. DNF란?

Dutch National Flag Problem(네덜란드 국기 문제)은 컴퓨터 과학자 다이크스트라가 제안한 알고리즘

문제로, 배열 내의 요소들을 세 개의 범주로 나누는 문제다. 네덜란드 국기의 색깔(빨강, 하양, 파랑)에 비유해서

이름이 붙여졌다.

 

이 문제의 목표는 배열에 세 가지 다른 값이 있을 때, 이를 특정 순서대로 배열하는 것이다. 보통 이 문제는 0, 1, 2로

이루어진 배열을 다루며, 0은 왼쪽에, 1은 중간에, 2는 오른쪽에 배치하는 것을 목표로 한다.

 

 

2. 동작 방식

• mid가 2이면 mid와 high의 값을 교환하고, high를 왼쪽으로 한 칸 이동한다.
• mid가 1이면 mid를 오른쪾으로 한 칸 이동한다.
• mid가 0이면 mid와 low의 값을 교환하고, mid와 low 각각 오른쪽으로 한 칸 이동한다.

 

 

3. 시간 복잡도

In-place 알고리즘 중 하나로 추가적인 메모리 공간 없이 O(N)의 시간 복잡도를 갖는다.

 

 

 

 

 

 

---