인사
안녕하세요. 오늘은 플래티넘으로 가는 길 첫 번째 포스팅입니다.
저는 현재 Baekjoon Online Judge에서 추천한 알고리즘 학습 루트를 따라 문제를 풀고 있습니다.
그 시작점은 바로 N과 M 시리즈였는데요, 이번 글에서는 이 문제들을 어떻게 접근하고 해결했는지 제 풀이 과정을 공유드리려 합니다.
문제
백준의 알고리즘 문제 중 'N과 M' 시리즈는 총 12문제로 구성되어 있습니다. 이 시리즈는 각각의 문제에서 주어진 배열을 어떤 방식으로 정렬하거나 조합할지를 묻고 있으며, 문제 유형은 비슷하지만 조건이 조금씩 다르게 주어집니다.
핵심은 단 하나의 아이디어만 잘 이해하면, 나머지 문제들도 그 흐름 안에서 충분히 해결할 수 있다는 점입니다. 처음에는 어렵게 느껴질 수 있지만, 하나를 제대로 이해하고 나면 이후 문제들은 훨씬 수월하게 느껴질 것입니다.
물론 마지막 문제를 풀었다고 해서 앞선 문제들의 모든 내용을 자동으로 이해하게 되는 것은 아닙니다. 문제마다 담고 있는 개념과 조건이 다르기 때문에 직접 하나하나 풀어보면서 감을 익히는 것이 중요합니다.
제가 이번에 소개하고 싶은 문제는 시리즈 중 비교적 뒤쪽에 위치한 문제로, 앞서 나왔던 여러 가지 개념들이 잘 녹아 있는 문제입니다. 이 문제 하나만으로도 많은 것을 배울 수 있기 때문에, 충분히 학습용으로 좋은 예시가 될 수 있습니다. 하지만 이 문제만으로 전체를 설명할 수는 없기 때문에, 꼭 시리즈 전체를 직접 풀어보시길 추천드립니다.
핵심 아이디어
이 문제의 핵심 아이디어는 재귀함수를 이용한 탐색입니다. 여기서 더 나아가 중요한 개념은 바로 **백트래킹(Backtracking)**입니다. 백트래킹이란 단순히 깊이 들어가는 것뿐만 아니라, 이전 선택이 이후의 탐색에 영향을 줄 수 있기 때문에 그 흐름을 제어하는 방식을 말합니다.
즉, 탐색 도중 조건에 맞지 않거나 더 이상 진행할 필요가 없다고 판단되면, 바로 이전 단계로 되돌아가 다른 경우를 탐색합니다. 이러한 방식은 모든 경우의 수를 탐색하되 불필요한 경우는 미리 제외하는 효율적인 기법으로, 재귀함수를 사용할 때 자주 활용됩니다.
저는 이 문제를 다음과 같은 흐름으로 풀이했습니다:
1. 입력 처리: n과 m, 그리고 수열 받기
문제에서 n과 m을 입력받은 후, n개의 수를 문자열 형태로 받아 배열로 치환합니다. 이때 getline이나 istringstream 같은 방법을 사용하면 공백 기준으로 쉽게 파싱할 수 있습니다.
2. 수열 정렬
중복을 제거하거나 조합의 순서를 일정하게 하기 위해, 입력받은 배열을 정렬합니다. 이는 이후 탐색 과정에서 중복 방지나 사전 순 출력에 도움이 됩니다.
3. DFS(깊이 우선 탐색)와 정답 저장 방식 설계
정답을 담기 위한 적절한 자료구조(예: vector, set)를 설계한 뒤, DFS 방식을 통해 가능한 조합을 탐색합니다. 이때 이전 숫자보다 같거나 큰 숫자만을 선택하게 하면 조건을 만족하는 조합만 생성할 수 있습니다. 이 과정에서 재귀 호출이 사용되며, 필요할 경우 되돌아가서 다른 경로를 탐색하는 백트래킹이 자연스럽게 이뤄집니다.
4. 결과 출력
모든 유효한 조합이 수집된 후, 이를 출력 형식에 맞춰 정리하여 출력합니다. 중복 제거가 필요한 경우, set 자료구조를 이용하거나 DFS 호출 전에 중복 조건을 직접 체크해주는 것도 방법입니다.
1. 입력 처리: n과 m, 그리고 수열 받기
먼저, 문제 해결을 위한 가장 첫 단계는 사용자로부터 입력을 받는 부분입니다. 저는 C++에서 C 스타일의 입력 방식과 함께 getline, istringstream을 조합하여 다음과 같이 처리했습니다.
수열 입력은 다음과 같은 함수로 처리했습니다:
이 코드에서 주목해야 할 입력 처리 방식 세 가지를 정리해보겠습니다.
1-1. scanf()와 getchar()의 조합
일반적으로 C++에서는 std::cin >> n >> m; 방식으로 입력을 받는 것이 더 보편적입니다. 그럼에도 불구하고 scanf()를 사용하는 이유는 입력 속도가 더 빠르기 때문입니다.
여기서 중요한 점은 scanf() 이후 getchar()를 호출한 이유입니다. 이는 scanf()를 사용할 경우, 입력 버퍼에 남아 있는 개행 문자(\n)가 이후의 getline() 입력에 영향을 주기 때문입니다. 따라서 getchar()를 통해 이 개행 문자를 제거해주는 것이 안전한 입력 처리를 위해 꼭 필요합니다.
1-2. getline()으로 한 줄 전체 입력 받기
getline(std::cin, arr_s)를 사용하면 한 줄 전체의 입력을 문자열로 받아올 수 있습니다. 이 방법은 공백이 포함된 여러 개의 값을 한 번에 처리해야 할 때 매우 유용합니다.
예를 들어, 사용자가 "1 3 5 7"을 입력했다면, 이 전체를 문자열로 받아 후속 처리를 할 수 있게 됩니다.
1-3. istringstream을 이용한 문자열 파싱
std::istringstream은 문자열을 마치 입력 스트림처럼 다룰 수 있게 해줍니다. 즉, 문자열 안에 있는 여러 값을 공백 단위로 하나씩 추출할 수 있습니다.
예를 들어 "1 2 3 a 4" 같은 문자열이 있다면, iss >> value를 통해 정수값만 필터링해 1, 2, 3, 4를 추출할 수 있습니다. 이 방식은 불필요한 예외 처리 없이 간결하게 숫자만 뽑아내고 싶을 때 매우 편리합니다.
2. 수열 정렬
입력을 받은 수열을 본격적으로 탐색하기 전에 먼저 해야 할 일은 정렬입니다. 정렬을 해두면 이후 조합을 생성할 때 중복 제거나 사전 순 출력 조건을 훨씬 쉽게 처리할 수 있기 때문입니다.
보통은 C++ 표준 라이브러리에서 제공하는 std::sort()를 사용하는 것이 가장 간단하고 빠릅니다:
하지만 저는 이번 문제에서 **힙 정렬(Heap Sort)**을 직접 구현해 사용했습니다. 그 이유는 단순히 문제를 푸는 것을 넘어서, 정렬 알고리즘을 직접 손으로 구현해보는 것이 진짜 이해하는 길이라고 생각했기 때문입니다.
직접 구현한 힙 정렬
아래는 제가 구현한 힙 정렬 코드입니다:
왜 손코딩 정렬을 선택했을까?
정렬 알고리즘은 자료구조와 알고리즘 공부에서 가장 중요한 파트 중 하나입니다. 특히 힙 정렬, 병합 정렬, 퀵 정렬은 컴퓨터 과학에서 매우 기본적이고 핵심적인 정렬 방식이죠.
이러한 알고리즘을 단순히 '쓸 줄만 아는 것'과 '직접 구현할 수 있는 것' 사이에는 큰 차이가 있습니다. 그래서 저는 연습 삼아 HeapSortFunc()를 직접 구현하고, 이를 문제 풀이에 적용해보았습니다.
참고로 std::sort()와 힙 정렬 모두 평균 시간복잡도는 **O(n log n)**이며, 이 문제처럼 입력 크기가 크지 않은 상황에서는 메모리나 시간에서 큰 차이를 보이지 않습니다.
정렬의 목적
이 과정을 통해 수열을 오름차순으로 정렬하게 됩니다. 이는 이후 중복 조합을 생성할 때, 같은 수가 여러 번 등장하더라도 정해진 순서대로만 조합되도록 도와주며, 결과적으로 중복 제거와 사전 순 출력을 보다 깔끔하게 처리할 수 있도록 합니다.
3. DFS(깊이 우선 탐색)와 정답 저장 방식 설계
std::set 자료구조를 이용해 정답을 저장했습니다.정답 저장 구조
- answer: 정답을 저장할 집합입니다. 중복 없이 자동 정렬되며, 삽입 순서와 관계없이 사전 순으로 관리됩니다.
- current: 현재 탐색 중인 조합을 담고 있는 배열입니다.
DFS 함수 정의
DFS에서의 핵심 단계 3가지
3-1. current[depth++] = arr[node];
현재 위치에서 선택한 값을 현재 깊이 인덱스에 저장합니다. 여기서 한 가지 중요한 점은, 값을 직접 current 배열에 저장하고 있다는 점입니다.
처음에는 참조 문제나 값 덮어쓰기 문제가 생기지 않을까 우려될 수 있지만, 백트래킹의 핵심은 재귀 호출 이후에도 이전 상태가 보존되어 있다는 점에 있습니다. 이미 current는 매 호출마다 동일한 객체를 공유하지만, DFS가 마치 스택처럼 작동하기 때문에 호출 이후 복귀하면서 상태가 자연스럽게 되돌아옵니다.
3-2. answer.insert(current);
목표 깊이에 도달했을 경우, 현재 조합을 정답 집합에 추가합니다. 이때 중요한 점은 set은 내부적으로 값을 복사하여 저장한다는 것입니다. 즉, 단순히 참조만 유지하는 것이 아니라 해당 시점의 값을 그대로 보존하므로, 이후 탐색에서 current가 변경되어도 이전 조합에는 영향을 주지 않습니다.
이는 백트래킹 구조에서 매우 유리하며, 불필요한 중복 저장이나 복잡한 복사 처리 없이 안정적으로 데이터를 저장할 수 있습니다.
3-3. for (int new_node = node; new_node < n; new_node++)
DFS 탐색 시, 현재 노드보다 같거나 이후 인덱스부터 다시 탐색을 시작합니다. 이 방식은 문제에서 "같은 수를 여러 번 골라도 된다"는 조건을 만족시키면서도, 중복된 조합이 생성되지 않도록 보장합니다.
또한 이 방식은 visited 배열을 따로 쓰지 않아도 되기 때문에, 코드가 훨씬 간결하고 직관적으로 구성됩니다.
4. 결과 출력
탐색이 끝나면, 이제는 저장된 정답을 출력하는 일만 남았습니다. 저는 이 과정을 다음과 같은 함수로 처리했습니다:
핵심 포인트
이 출력 함수에서 주목할 만한 점은 다음과 같습니다.
1. auto를 활용한 반복문
std::set<std::array<int, MAX_N>>는 다소 복잡한 자료형입니다. 이 경우 범위 기반 for문과 auto를 활용하면 더 간결하고 읽기 쉬운 코드를 작성할 수 있습니다.
이렇게 하면 answer 집합에서 각 조합(array<int, MAX_N>)을 하나씩 꺼내와 a에 저장하고, 내부 루프에서 각 값을 출력할 수 있습니다.
2. 정답이 자동으로 정렬되어 출력됨
std::set의 특성상 내부적으로 값들이 자동 정렬되어 저장되기 때문에, 따로 정렬을 하지 않아도 사전 순으로 결과가 출력됩니다. 이는 출력 조건이 엄격한 문제에서 매우 유리합니다.
3. printf를 이용한 빠른 출력
C++에서는 std::cout보다 printf가 더 빠른 경우가 많습니다. 특히 많은 양의 출력을 다룰 때 printf는 성능상 이점을 줄 수 있어, 저는 이를 활용해 정답을 출력했습니다.
마무리
이렇게 해서 'N과 M' 시리즈 문제 풀이를 모두 마무리했습니다. 이 문제들을 풀면서 특히 느낀 점은 C++ 언어에 점점 익숙해졌다는 점입니다. 처음엔 낯설게 느껴졌던 문법이나 입출력 처리 방식도, 반복적인 구현을 통해 자연스럽게 손에 익게 되었고, C++ 특유의 자료구조와 알고리즘 활용법을 실제 문제에 적용해보는 좋은 계기가 되었습니다.
그래서 저는 이 시리즈를 강력히 추천하고 싶습니다. 단순히 알고리즘 문제를 푸는 것을 넘어서, C++ 언어에 대한 감각을 키우고 백준에서의 전형적인 사용 패턴을 익히기에도 매우 좋은 문제들이기 때문입니다.
이제 다음으로는 시뮬레이션 문제들을 풀어볼 예정입니다. 보다 복잡한 상황을 코드로 구현하면서 한 단계 더 도약할 수 있는 기회가 될 것 같아 기대하고 있습니다.
긴 글 읽어주셔서 감사합니다. 이 글이 문제 풀이에 조금이나마 도움이 되었기를 바라며, 언제나 여러분이 하시는 일에 좋은 결과가 함께하길 진심으로 응원하겠습니다.
