by
May 24. 2023
재귀(recursive) 함수와 DFS에 대한 소고
본질을 이해하지 못하면 되는 일이 없다.
Why,
개발 경력 n년차에 대이직 시대를 맞이했다. 아마 이 글을 읽고 있는 여러분 또한 아주 높은 확률로 동시대를 살고 있을 것이다. 우리가 가슴속에 담아두면 언젠가 한 번은 '옛 말이 틀린 게 없구나'를 느끼게 되는 옛 선현의 말씀 하나를 여기서 소개한다.
너의 모든 에너지를 너의 것이 아닌 회사에 몰빵 하지 말라.
따라서 현대 직장인이라면 유사시 당기면 의자째 사출 되어 다른 회사로 날아가는 탈출 레버 하나씩은 필수로 구비해두는 것이 인지상정일 터, 경력 개발자가 탈출 레버를 만들기 위해 필요한 것 중 하나가 알고리즘 문제 풀이 능력 재배양 되시겠다.
Why 2,
코딩 테스트(LIVE or not)를 위해 알아둬야 하는 알고리즘은 정말 많다. 별도의 알고리즘 공부를 하지 않아도 문제에 대한 통찰과 직관만으로 최적의 해를 찾을 수 있는 사람은 노력하지 않아도 고통받지 않는다. 그런 사람은 이런 글을 읽는데 시간을 투자하지 않을 것이니 독자 중에 그런 사람은 존재하지 않는다고 가정했다.
n년차 경력 개발자라면 쉬운 알고리즘 문제는 거창한 알고리즘을 몰라도 적절한 시공간 복잡도를 가지는 코드로 해결할 수 있기 마련이다. 다만 특정 알고리즘을 겨냥하여 출제된 문제의 경우, 즉, 문제의 의도 자체가 불순한(=자네가 이 방법을 알고 있는지 검증하겠네!) 경우에는 해당 알고리즘 풀이에 대한 경험이 없으면 상당한 삽질을 수반하게 되는 경우가 생기고, 기업에서 코딩테스트나 라이브 코딩 문제를 준비할 때, 이런 경우가 비일비재하다는 것이다. (누가 세상이 아름답다고 했나.)
개인적으로는 도메인에 따라 코딩 테스트 문제를 선별하는 것이 효율적이라 생각하고, 그렇게 선별해서 문제나 과제를 출제하고 있다. 하지만 모든 기업의 코딩 테스트 담당자들이 같은 방식으로 생각하길 바라는 것은 역시나 무리.
그렇다면 우리는 불순한 의도로 코딩 테스트 문제가 출제되는 경우에 대해서도 준비되어 있어야 한다.
Why the recursive function?
모든 알고리즘에 대해 글을 하나씩 올릴 것이냐? 그렇지 않다. 소위 천상계 알고리즘에 대한 내 이해도는 글로 적기에 처참한 수준이고, 쉬운 알고리즘이나 일반론에 대한 글은 이미 인터넷에 넘쳐나고 또 넘쳐나는 형국이니 역시 쓸 이유가 없다.
개인적으로 재귀 함수와 dfs, bfs, backtracking 알고리즘 문제 풀이를 온전히 이해하는데 받았던 고통이 가장 인상적이었기 때문에 이에 대한 회고를 남김으로써 세상의 고통을 줄이는데 일조하고 싶었다.
Why suffer?
별 거 없다.
어려운 것을 구현하지 못하는 것은 스스로의 부족함 때문이다. 이 부분에 이견이 있는 사람은 찾기 힘들다. 다만 '쉬워 보이고 할 수 있을 것 같은데' 답이 원하는 대로 나오지 않는 경우, 판도라의 상자에 들어있던 모든 부정적 감정을 다양한 조합으로 맛볼 수 있다. (판도라 너..너.. 희망만 빼고 다 꺼내놨으렸다!)
개발자는 별 거 아닌 (것처럼 보이는) 코드를 못 짤 때 가장 아프고 슬프다.
재귀, dfs, bfs, backtracking 문제는 상대적으로 사람이 이해하기 쉽다. 그리고 구현을 하는데 뜻대로 되지 않으면 심혈관계 이상 상태가 유발될 가능성이 급격히 높아진다.
간단한 예시를 보자.
Q. 1부터 9까지의 숫자 카드가 n장 주어진다. 이 숫자 카드들을 조합하여 만들 수 있는 모든 숫자 중 1과 자기 자신 이외로는 나누어 떨어지지 않는 소수의 개수를 구하여라. 각 숫자를 만들 때 사용할 수 있는 카드의 수는 1~n장이고 1 ≤ n ≤ 1000이다.
(입력 예시) [1,2]
(출력 예시) 1
(해설) 숫자 카드가 2장(1, 2)이 주어진 경우, 만들 수 있는 숫자는 1, 2, 12, 21의 4개, 그중 소수는 2 뿐이다.
이 얼마나 간단한가! 쉽다. 쉬워.
초등학교(혹은 국민학교)에서 배운대로 모든 경우의 수를 구한 다음, 소수 판별만 하면 간단히 해결된다. 소수 판별은 어려울 것이 없으니 패스.
private boolean isPrime(int number) {
if (number == 2) return true;
if (number < 2 || number % 2 == 0) return false;
for (int i = 3; i <= Math.sqrt(number); i += 2) {
if (number % i == 0) {
return false;
}
}
return true;
}
남은 것은 경우의 수를 구하는 것이고 이게 어려울 것이 뭐가 있겠는가!라고 생각했(었)다.
그리고 작성된 코드를 보자.
class NumberCombinationSolution {
public int solution(int[] cards) {
SortedSet<String> set = new TreeSet<>();
boolean[] checked = new boolean[cards.length];
for (int length = 1; length <= cards.length; length++) {
dfs(cards, set, "", checked, length);
}
return set.size();
}
private void dfs(int[] cards, SortedSet<String> set, String current, boolean[] checked, int length) {
if (current.length() == length) {
set.add(current);
return;
}
for (int i = 0; i < cards.length; i++) {
if (!checked[i]) {
checked[i] = true;
dfs(cards, set, current + cards[i], checked, length);
checked[i] = false;
}
}
}
private boolean isPrime(int number) {
if (number == 2) return true;
if (number < 2 || number % 2 == 0) return false;
for (int i = 3; i <= Math.sqrt(number); i += 2) {
if (number % i == 0) {
return false;
}
}
return true;
}
}
????????
DFS(Depth-First Search) 문제 풀이에 익숙하지 않은 사람은 보는 순간 가슴이 두근거리는 것을 느낄 수도 있다. 나도 그랬지만 보통은 치명적인 건강 문제로 바로 이어지진 않으니 너무 많이 당황하지는 말자.
재귀라매! 재귀라매!?
dfs는 기본적으로 stack을 이용한 완전 탐색 기법이다. 이를 명시적인 stack 자료 구조로 푸느냐, 본문의 예시 코드처럼 묵시적인 stack 자료 구조로 푸느냐의 차이가 있을 뿐, 본질은 동일하다.
이 글에서 다룰 핵심 내용은 '그래, 알겠는데 그걸 어떻게 설계해서 써먹냐고!'이다. 내가 고통받았던 부분이 이 부분이기 때문이다. (마이 프레셔스 페인 포인트)
What's the recursive function?
문제 풀이에 재귀 함수를 이용하기 위해서는 재귀 함수의 본질을 이해할 필요가 있다. 우선 정의는, 재귀(再歸)라는 이름 그대로, 개발 분야에서 재귀 함수란 함수 내부에서 스스로를 호출하는 코드를 일컫는다.
대동소이한 정의가 정말 백사장의 모래알만큼이나 인터넷과 유튜브에 많이 올라와있으니 의심스러우면 직접 찾아봐도 좋다.
핵심은 이거다: 잘 설계된 재귀 함수는 절대적으로 아래 2가지의 공통점을 가진다.
1. 재귀함수는 호출이 종료되는 부분을 반드시 포함한다.
무한 호출을 일으키지 않으려면 지극히 당연한 말로, 위 예시에서는 아래 주석으로 표시된 부분을 가리킨다. 종료 시점을 숨기려면 숨길 수 있겠지만, 재귀 함수 설계 시 그런 짓을 했다가는 가독성과 유지보수성이 내 주식 시장가 마냥 급격히 떨어지게 된다.
케이스를 극단적으로 줄여서 생각해 보면 종료 조건을 찾는데 도움이 되는 경우가 많다. 이 내용은 마지막 예제를 다루는 부분에서 다시 한번 언급한다.
if (current.length() == length) {
set.add(current);
return;
}
2. 스스로를 호출할 때는 매개변수가 코드 내에서 반드시 동적으로 변경된다.
아래의 current + cards[i] 부분을 말한다. 역시 객체 등을 이용하여 변경되는 부분을 숨길 수 있겠지만, 제발 그러지 않기로 하자.
dfs(cards, set, current + cards[i], checked, length);
거의 비를 맞으면 옷이 젖는다 수준의 당연한 명제지만 이 단순한 사실을 직시하기까지 걸리는 시간은 사람마다 천차만별이다. 똑똑한 여러분은 순식간에 간파했겠지만 불행히도 그렇지 못한 나는 함수명을 비롯해 이곳저곳에 낚여대며 꽤 오랜 시간을 허비해야 했다.
Let's make some.
자, 이제 재귀 함수를 설계해 보자.
2개의 새로운 예제와, 앞서 예를 들었던 dfs 문제 풀이까지 총 3개의 예제로 재귀 함수 설계 방법을 체득해 보자.
제일 쉬운 것부터!
임의의 자연수를 입력받아, 1부터 이 자연수까지의 합을 구하는 재귀 함수를 만들어보자.
public int solution(int number) {
// return IntStream.rangeClosed(1, number).sum(); // 이건 재귀 함수가 아니다, jdk8+ 이용자여!
return sum(number);
}
재귀 함수 설계의 첫 조건: 종료 부분을 우선 아래와 같이 작성해보자.
int sum(int number) {
if (number == 1) {
return 1;
}
return ?
}
재귀 함수니까 (?) 자리에 sum이라는 함수가 어떻게든 사용될 것이라는 것을 쉽게 유추할 수 있다.
우리는 재귀 함수 설계의 두번째 조건: 매개변수가 동적으로 변한다는 것 역시 이미 알고 있다. 요구사항을 생각해 보면 자연스럽게 아래와 같은 재귀 함수가 완성된다.
int sum(int number) {
if (number == 1) {
return 1;
}
return number + sum(number - 1);
}
와!!! 재귀 함수가 뚝딱 완성됐다.
겪어봐서 자신있게 말하건대 재귀 함수의 코드 형태에 사로잡히지 말고, 어떻게 재귀 함수가 만들어지는지 그 과정에 집중하면 고통을 경감하는데 도움이 된다.
다음은 주어진 10진법 숫자를 2진법 문자열로 변환하는 재귀 함수를 만들어보자. 라이브 코딩 때 자주 출제되는 문제인만큼 좋은 예제가 되어 줄 것이다.
public String solution(int decimal) {
return convert(decimal);
}
10진수를 2진수로 변환하는 방법은 간단하다.
주어진 수가 5일 때,
- 5를 2로 나눈 몫과 나머지를 구한다. (몫: 2, 나머지: 1)
- 몫을 다시 2로 나눈 몫과 나머지를 구한다. (몫: 1, 나머지 0)
- 몫이 2보다 작아질 때까지 반복하는데, 이미 작아졌으니 나눗셈은 여기서 끝난다.
- 마지막으로 나온 몫(1) 마지막으로 나온 나머지(0) 그전에 나온 나머지(1)를 순서대로 써주면 완성(101)
설계의 첫번째 조건에 해당하는 종료 조건은 '몫이 2보다 작을 때'라는 것을 알 수 있다.
재귀 함수를 만들어보자.
String convert(int decimal) {
if (decimal < 2) {
return String.valueOf(decimal);
}
return ?;
}
그리고 '?' 자리에 어떤 코드가 들어가야 할지를 요구사항을 보며 맞춰보면 아래와 같은 함수를 완성할 수 있을 것이다.
String convert(int decimal) {
if (decimal < 2) {
return String.valueOf(decimal);
}
return convert(decimal / 2) + decimal % 2;
}
와!!! 재귀 함수가 뚝딱 완성됐다2.
이제 숫자 배열을 받아서 해당 숫자들로 만들어질 수 있는 숫자 경우의 수를 모두 구하는 첫 번째 문제로 다시 돌아가보자.
Q'. 1부터 9까지의 숫자 카드가 n장 주어진다. 이 숫자 카드들을 조합하여 만들 수 있는 모든 숫자를 표준 출력으로 출력하라.
앞에서 다룬 2개 예제와는 다소의 이질감이 느껴지는데, 이는 명시적으로 '재귀 함수'를 만들라는 말이 없기 때문이다. 그럼에도 불구하고 '재귀 함수' 사용을 선택하는 것에는 간단한 이유가 있는데, 문제를 해석하면서 '아.. 뭔가 비슷한 로직이 반복되어야 할 것 같은데..'라는 싸한 느낌이 들기 때문이다.
망치를 든 사람의 눈에는 모든 것이 못으로 보인다는 말이 있지만 모든 문제를 재귀로 풀려고 하다가는 단언컨대 원치 않는 결말을 맞이할 것이다. 이 점 곁다리로 유의해두길 바라며, 다시 문제로 돌아가서 살펴보자.
우리는 만들어질 수 있는 모든 숫자가 필요하다. 그때그때 출력돼도 괜찮겠지만 여기서는 set에 모아보자.
우선 기본 뼈대가 아래와 같다고 가정하고, print 함수는 재귀 함수라는 것을 염두에 두자.
public void solution(int[] cards) {
Set<String> numbers = new HashSet<>();
print(cards, set);
numbers.forEach(System.out::println);
}
private void print(int[] cards, Set<String> numbers) {
return;
}
1번 조건에 따라 종료 조건을 찾아야 한다.
케이스를 극단적으로 줄여 생각하면 종료 조건을 찾기 쉽다고 본문에 언급했었는데 지금이 그럴 때다. 숫자 카드가 1장인 경우를 생각해 보자.
int[] cards = {1};
따질 것도 없다. 이 경우라면 답은 무조건 "1" 하나다.
아직 불명확하니 숫자 카드가 2장인 경우를 생각해 보자.
int[] cards = {1, 2};
우리는 답은 이미 알고 있다. 1, 2, 12, 21이겠지.
set에 저장되는 자릿수가 변경되는 것을 눈치챘는가? 골격 성형이 필요한 시간이다.
뼈대를 아래와 같이 바꿔보자.
public void solution(int[] cards) {
Set<String> numbers = new HashSet<>();
for (int length = 1; length <= cards.length; length++) {
print(cards, numbers, length);
}
numbers.forEach(System.out::println);
}
private void print(int[] cards, Set<String> numbers, int length) {
return;
}
카드가 1장이면, length는 1, 카드가 2장이면 length가 2, 뭐 좋다.
그런데, 여전히 종료 조건을 적기에는 뭔가 부족하다.
일련의 연산을 통해 만들어진 숫자의 길이가 length와 같으면 set에 넣고 종료하면 될 것 같은데, 그 '만들어진 숫자'를 보관할 변수가 없다.
다시 골격을 수정하자.
public void solution(int[] cards) {
Set<String> numbers = new HashSet<>();
for (int length = 1; length <= cards.length; length++) {
print(cards, numbers, "", length);
}
numbers.forEach(System.out::println);
}
private void print(int[] cards, Set<String> numbers, String current, int length) {
return;
}
됐다!
이제 1번 조건에 따라 종료 조건을 재귀 함수에 추가해 줄 수 있다. 종료 조건을 추가하면 아래와 같이 함수가 변경된다.
private void print(int[] cards, Set<String> numbers, String current, int length) {
if (current.length() == length) {
numbers.add(current);
return;
}
return;
}
절반은 왔다.
이제 설계의 두번째 조건을 생각해 볼 차례다. 요구사항은 주어진 카드를 조합하여 숫자를 만드는 것이다. 우리가 임의로 성형한 골격에 따라 print라는 함수는, 숫자 카드를 조합해서 주어진 length만큼의 길이를 만드는 것에서 그 역할이 끝난다.
역할을 성공적으로 수행하기 위해 아래와 같이 구현해 보자.
private void print(int[] cards, Set<String> numbers, String current, int length) {
if (current.length() == length) {
numbers.add(current);
return;
}
for (int i = 0; i < cards.length; i++) {
print(cards, numbers, current + cards[i], length);
}
}
됐다. 출력을 해보면 아래와 같은 출력 값을 얻을 수 있다.
11
22
1
12
2
21
이 시점에서 값이 이렇게 나오기까지의 과정을 한번 되짚어 완전히 이해할 필요가 있다. 완전히 이해가 끝났다면, 요구사항에서 숫자 카드를 '조합'하여라는 말에 '카드를 중복해서 사용할 수 없다'는 뜻이 포함되어 있다는 것도 기억해 내자.
어떻게 한번 사용된 카드는 다시 사용되지 않도록 할 수 있을까?
여기서 dfs의 묘미, 사용 이력 배열이 사용된다.
골격 성형이랄 것까진 없지만 해당 배열은 print 함수가 재귀 호출 될 때 초기화되면 의미가 없어지기 때문에 print 함수 스코프를 벗어난 곳에 선언되어야 한다.
아래와 같이 사용 이력 배열을 추가해 주자.
public void solution(int[] cards) {
Set<String> numbers = new HashSet<>();
boolean[] visited = new boolean[cards.length];
for (int length = 1; length <= cards.length; length++) {
print(cards, numbers, "", visited, length);
}
numbers.forEach(System.out::println);
}
private void print(int[] cards, Set<String> numbers, String current, boolean[] visited, int length) {
if (current.length() == length) {
numbers.add(current);
return;
}
for (int i = 0; i < cards.length; i++) {
print(cards, numbers, current + cards[i], visited, length);
}
}
이제 거의 끝났다.
print 함수에서 사용된 카드가 재귀 호출된 print 함 내부에서는 사용되지 않도록 print 함수를 아래와 같이 변경해 준다.
private void print(int[] cards, Set<String> numbers, String current, boolean[] visited, int length) {
if (current.length() == length) {
numbers.add(current);
return;
}
for (int i = 0; i < cards.length; i++) {
if (!visited[i]) {
visited[i] = true;
print(cards, numbers, current + cards[i], visited, length);
visited[i] = false;
}
}
}
print 함수 내부에서 print 함수 재귀호출이 일어난 시점에는 이력 배열 내 모든 값이 항상 false로 유지되는 것, 그리고 이력 배열 내 값이 true인 숫자 카드는 해당 재귀(재귀(재귀..))가 모두 완료되기 전까지 결코 사용되지 않는다는 것을 이해하면, 중복 숫자 카드가 이용되지 않는 것을 자연스럽게 이해할 수 있다.
이제 출력 결과를 살펴보면 아래와 같다.
1
12
2
21
