[BOJ/C++] 백준 15655번: N과 M(6)

Introduction

---

15655번: N과 M (6)

 

오늘 풀어볼 문제는 백준 15655번, N과 M (6)입니다. 입력과 출력은 아래 표와 같으며, 중요 포인트는 고른 수열이 오름차순이어야 하는 점입니다. 이를 통해 sorting 된 입력값들을 가지고 시작점만 증가시키며 정답을 구할 수 있습니다. 즉, visited(or selected) 배열을 따로 생성할 이유가 없습니다.

 

입력	→ 첫째 줄에 N과 M이 주어진다. $(1 \leq N \leq M \leq 8)$ → 둘째 줄에 N개의 수가 주어진다. $(input num \leq 10,000)$
출력	→ 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다 → 중복되는 수열을 여러 번 출력하면 안된다 → 각 수열은 공백으로 구분해서 출력해야 한다 → 수열은 사전 순으로 증가하는 순서로 출력해야 한다

 

이제 본격적으로 문제를 풀어보도록 하겠습니다. 글의 순서는 이번에는 source code를 먼저 보고, 어떤 사고의 흐름으로 계획을 짰는지 Pseudo code를 통해 살펴보겠습니다. 그리고 ChatGPT에게 이번 문제를 풀어보게 할 예정입니다. Source code를 보고 싶어서 들어오신 분들을 위해서 순서를 조금 바꾸었습니다.

 

Source Code

---

/**
 * @file q15655.cpp
 * @author YoungJ-Baek (qordudwls1@gmail.com)
 * @brief solution for BOJ #15655, https://www.acmicpc.net/problem/15655
 * @version 0.1
 * @date 2023-03-10
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <algorithm>
#include <iostream>
#include <vector>

#define MAX 9

using namespace std;

int N, M;
int input[MAX];
vector<int> result;

void dfs(int count, int start);

int main() {
  cin >> N >> M;
  for (int index = 0; index < N; index++) cin >> input[index];
  sort(input, input + N);
  dfs(0, 0);
}

void dfs(int count, int start) {
  if (count == M) {
    for (int index = 0; index < M; index++) cout << result[index] << ' ';
    cout << '\n';
    return;
  } else {
    for (int index = start; index < N; index++) {
      result.push_back(input[index]);
      dfs(count + 1, index + 1);
      result.pop_back();
    }
  }
}

 

Planning

---

720

 

ChatGPT

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void generate_combinations(vector<int>& nums, vector<int>& comb, int M, int index) {
    if (M == 0) {
        // Print combination
        for (int num : comb) {
            cout << num << " ";
        }
        cout << endl;
        return;
    }
    for (int i = index; i < nums.size(); i++) {
        comb.push_back(nums[i]);
        generate_combinations(nums, comb, M-1, i+1);
        comb.pop_back();
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> nums(N);
    for (int i = 0; i < N; i++) {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end()); // Ensure numbers are in ascending order

    vector<int> comb;
    generate_combinations(nums, comb, M, 0);

    return 0;
}

 

흥미롭게도 ChatGPT가 생성한 코드의 경우 총 4ms의 runtime이 소요된 반면에, 제 source code는 0ms의 runtime이 소요되었습니다. Code를 유심히 살펴보면 몇 가지 차이점을 발견할 수 있는데요.

1. Array vs Vector
   • ChatGPT는 입력값들을 모두 vector를 통해 받았습니다. 반면에 제 코드는 입력값의 경우 크기를 사전에 정할 수 있어 array로, 출력값은 편의성을 위해 vector를 사용했습니다. 당연히 동적으로 메모리를 할당하는 vector가 runtime을 늘리는데 영향을 줄 수 있지만, 4ms를 줄 거라고는 생각하지 않는데요. 계속 동적으로 할당되는 출력값의 경우 두 코드 모두 vector를 사용했고, 최초 1회만 영향을 주는 입력값에만 차이가 있으니까 더욱더 그렇습니다.
2. 전역 변수 vs 로컬 변수
   • ChatGPT는 로컬 변수를, 저는 전역 변수를 통해 N, M, input, output을 관리한 차이가 존재했습니다. 그러나 이 부분은 엄밀히 따지면 memory 사용량에 차이가 생겨야 하는 부분이기에 runtime 차이에서는 크게 중요하지 않습니다. 실제로 모든 function call에서 변수들을 호출하고, 재귀적으로 구현됨에 따라 hold하고 있어야 하는 ChatGPT의 코드는 제 코드보다 memory 사용량이 2KB 큼을 확인할 수 있었습니다. 해당 내용은 아래 이미지에서 확인하실 수 있습니다.
3. endl vs \n
   • 잡았다, 요놈!! 범인은 여기에 있었습니다. 이전에도 언급한 적이 있는데요. C++에서 개행을 위해 'endl'을 쓰는 것과 '\n'을 사용하는 것에는 성능적으로 큰 차이가 있습니다. 이는 나중에 자세히 다루도록 하겠습니다. 간단히만 언급하면, buffer flush 동작 병행 여부에 차이가 있는데요. 'endl'은 매번 buffer flush를 같이 해주어 추가적인 overhead를 갖고 있습니다. 그래서 안정성에 자신이 있는 경우 성능적으로는 '\n'이 유리하게 됩니다. 실제로 ChatGPT가 생성해 준 코드에서 'endl' → '\n'만 변경했더니 0ms로 runtime이 크게 줄었습니다.

 

위부터 ChatGPT w/ '\n', ChatGPT w/ 'endl', my source code

 

Reference

---

GitHub - YoungJ-Baek/algorithm-study