Introduction
15650번: N과 M (2)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
오늘 풀어볼 문제는 백준 15650번, N과 M (2)입니다. 자연수 N과 M이 주어질 때, 1부터 N까지의 자연수 중 중복 없이 오름차순으로 M개를 고른 수열을 모두 구하는 코드를 짜는 게 오늘의 목표입니다. 입력과 출력은 아래와 같습니다.
| 입력 | 자연수 N, M (1 ≤ M ≤ N ≤ 8) |
| 출력 | 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. (오름차순) 중복되는 수열을 여러 번 출력해서는 안된다. 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. |
이제 본격적으로 문제를 풀어보도록 하겠습니다. 글의 순서는 어떤 사고의 흐름으로 계획을 짰는지 서술하고, 이번 포스트에서는 ChatGPT에 이번 문제를 풀어보게 할 예정입니다. 마지막으로는 source code를 통해 마무리할 것입니다. 정답지가 궁금하신 분들은 마지막 항목으로 바로 가셔도 무방합니다.
Planning
이번 문제는 14649번 문제의 변형, 혹은 업그레이드 버전이라는 인상을 받았습니다. 그래서 바로 재귀함수, 그중에서도 DFS를 활용해 문제를 풀기로 결정했습니다. 14649번 문제 풀이는 아래 링크에서 보실 수 있습니다.
[BOJ/C++] 백준 15649번: N과 M (1)
Introduction 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으
searching-fundamental.tistory.com
14649번 문제와 한 가지 다른 점은 모든 수열은 오름차순으로 구성되어야 한다는 점입니다. 우선 14649번 문제 해답에 최소한의 변형을 주어 문제를 해결하는 게 목표였습니다. 곰곰이 생각하니 두 가지 정도로 풀이가 떠오르더군요.
- 수열을 저장할 vector 생성 → algorithm.sort() 이용해 오름차순으로 정렬 후 중복 검사 후 push_back() → 최종 결과 출력
- DFS 과정 중 leaf node를 자신보다 큰 숫자에 한정하도록 설정
1번의 경우 변수 1개와 약 3줄의 코드를 추가하면 문제를 해결할 수 있습니다. 그러나 탐색을 할 필요가 없는 영역을 (자식 노드가 현재 자신보다 작은 경우) 탐색하게 되어 시간적 손해를 보게 됩니다. 그래서 귀찮음을 무릅쓰고 2번 방법을 통해 문제를 해결하기로 했습니다.
기존에 DFS 탐색을 위한 for문이 1(최솟값)부터 loop를 돌았다면, 현재 index를 저장할 변수가 필요합니다. 그래서 해당 변수를 함수 parameter로 전달해 DFS 탐색할 때마다 1씩 증가해 전달해 주도록 했습니다. 아래는 채점에 통과한 소스 코드입니다.
Source Code
/**
* @file q15650.cpp
* @author YoungJ-Baek (qordudwls1@gmail.com)
* @brief solution for BOJ #15650, https://www.acmicpc.net/problem/15650
* @version 0.1
* @date 2023-01-25
*
* @copyright Copyright (c) 2023
*
*/
#include <iostream>
#define MAX 9 // considering usage, 0~8 -> 1~9
int N, M; // input N(range), M(size)
int sequence[MAX]; // result sequence
bool visited[MAX]; // to filter repeated elements
void dfs(int index, int cnt);
int main() {
std::cin >> N >> M;
dfs(1, 0);
return 0;
}
void dfs(int index, int cnt) {
if (cnt == M) {
for (int iter = 0; iter < M; iter++) std::cout << sequence[iter] << ' ';
std::cout << '\n';
return;
} else {
for (int iter = index; iter <= N; iter++) {
if (visited[iter] == false) {
visited[iter] = true;
sequence[cnt] = iter;
dfs(iter + 1, cnt + 1);
visited[iter] = false;
}
}
}
}ChatGPT
사실 무엇보다 흥미로운 부분은 ChatGPT를 활용한 경험이었습니다. 문제를 푼 이후 문득 궁금해졌습니다. 과연 ChatGPT는 코딩 테스트 문제를 잘 풀 수 있을까? 최근에 로스쿨, 의사 라이센스, MBA 시험 등 다양한 직군의 시험을 ChatGPT가 통과했다는 소식을 들으며 개발자의 시험인 코딩 테스트 역시 수행시켜보고 싶었습니다. 그래서 짧은 영어를 통해 ChatGPT에게 질문을 던졌고, 결과는 저 스스로는 충격적이었습니다. 인용구로 대화 내용을 보여드리도록 하겠습니다. 대화 구분을 위해 제 말과 ChatGPT의 말은 다르게 표현하도록 하겠습니다.
YoungJ-Baek
ChatGPT
Please generate the code with C++ according to the following description.
[Description]
Given the natural numbers N and M, write a program to find all sequences with lengths M that satisfy the following conditions.
A sequence of M selected from natural numbers from 1 to N without duplication.
The even sequence must be in ascending order.
[Input]
The first line is given the natural numbers N and M. (1 ≤ M ≤ N ≤ 8)
[Output]
It outputs a sequence that satisfies the conditions of the problem, one per line. Duplicate sequences should not be printed multiple times, each sequence should be separated by a space.
The sequence shall be printed in order of increasing in dictionary order.
Here is a code in C++ that generates all sequences of length 'M' from '1' to 'N' without duplication and in ascending order:
#include <iostream>
#include <vector>
using namespace std;
vector<int> sequence;
void search(int n, int m) {
if (sequence.size() == m) {
for (int i = 0; i < m; i++) {
cout << sequence[i] << " ";
}
cout << endl;
return;
}
for (int i = 1; i <= n; i++) {
if (sequence.empty() || sequence.back() <= i) {
sequence.push_back(i);
search(n, m);
sequence.pop_back();
}
}
}
int main() {
int n, m;
cin >> n >> m;
search(n, m);
return 0;
}사실 여기까지만 해도 나름 안심(?)했습니다. 코드를 봤을 때 생각보다 너무 잘 짜서 놀랐지만, 시간제한에서 걸릴 것으로 생각했기 때문이었죠. 실제로 돌려보면 시간 초과로 실패하게 됩니다. 훗, 여기까지인가? 이런 오만한 생각이 들었지만 10초 뒤에 후회하게 됩니다. 생각해 보니 제약 조건을 주지 않았기 때문이죠. 그래서 조건을 아래와 같이 추가해 주게 됩니다.
[Limitation]
- Time limit: 1 sec
- Memory limit: 512MB
The code provided above will likely exceed the given time and memory limits, as it uses a brute-force approach to generate all combinations. To optimize the code to meet the given constraints, you can consider using an efficient algorithm such as backtracking. The following is an example code for the optimized version:
#include <iostream>
#include <vector>
using namespace std;
vector<int> sequence;
void search(int n, int m, int last) {
if (sequence.size() == m) {
for (int i = 0; i < m; i++) {
cout << sequence[i] << " ";
}
cout << endl;
return;
}
for (int i = last + 1; i <= n; i++) {
sequence.push_back(i);
search(n, m, i);
sequence.pop_back();
}
}
int main() {
int n, m;
cin >> n >> m;
search(n, m, 0);
return 0;
}놀랍게도 ChatGPT는 백트래킹 기법을 사용해 정확히 문제가 원하는 답을 구했습니다. 심지어 기존 자신의 코드가 무엇이 문제였는지 정의 내리고 수정하는 모습은 저에게 큰 충격을 주었습니다. 그리고 이 방법이 오히려 제가 사용한 방법보다 직관적일 수 있겠다는 생각을 했습니다. 물론 단순 list 기반보다 느리기는 하겠지만요. 둘 다 충분히 테스트를 통과할 수 있는 코드라면 직관적인 코드를 선호하는 제게는 이게 좀 더 좋은 코드처럼 보였습니다.
이렇듯 ChatGPT는 제 기대치를 상회하는 결과물을 만들어 냈습니다. 그래서 앞으로도 제 풀이와 더불어 ChatGPT의 풀이법을 같이 공유드릴까 합니다. 저 스스로도 ChatGPT와 친숙해질 수 있겠죠.
Appendix
이번 문제는 사실 계속 언급했듯이 14649번 문제의 후속 편이었습니다. 그래서 문제 자체는 꽤나 수월하게 풀었으나, 오히려 장난 반 기대 반으로 테스트한 ChatGPT가 굉장히 큰 충격으로 다가왔습니다. 이와 관련해 제 스스로 깊은 고찰을 했는데, 이는 좀 더 생각을 정리한 후 포스트로 남기도록 하겠습니다. 과연 ChatGPT를 비롯해 더욱더 발전된 AI가 등장할 미래에 개발자, 아니 인간의 역할은 무엇일까요?
