자주 틀리는 이유

BOJ에서 문제를 풀다보면, 틀렸습니다, 시간 초과, 메모리 초과, 런타임 에러, 출력 초과와 같은 결과를 받게 된다. 맞았습니다!!로 바꿀 수 있는 방법에 대해서 알아보자.

틀렸습니다

틀렸습니다는 문제에서 요구하는 정답을 구하지 못했을 때 받는 결과이다.

여러가지 데이터를 입력해보고 틀린 답을 구하는지, 의도한 답을 구하는지 비교해봐야 한다. 하지만, 데이터를 만들어보는 것이 쉬운 일은 아니고, 데이터를 만들었다고 해도 그것의 정답이 무엇인지 구하는 것도 쉬운 일은 아니다.

시간 초과

시간 초과는 프로그램의 수행 시간이 문제의 시간 제한을 넘어갈 때 발생한다.

런타임 에러

C++의 경우 런타임 에러는 주로 Segmentation fault이고, 가끔 Floating point exception, std::bad_alloc 등이 있다.

Java와 Python은 실행하다가 발생할 수 있는 각종 에러가 런타임 에러이다.

출력 초과

출력 초과는 너무 많은 출력을 하는 경우에 발생한다. 틀렸습니다와 같은 의미를 갖는다. 미리 구해놓은 정답 파일 크기의 2배를 넘어가면 이 결과를 받는다. 무한 루프에 빠진 경우 무한 루프에서 출력을 한다면 시간 초과 전에 출력 초과를 받을 수 있다.


오버플로

오버플로(Overflow)는 잘못된 자료형을 선택했을 때 주로 발생한다. Python은 정수형에 크기 제한이 없어서, C++과 Java의 경우에 주로 발생한다.

주로 N이 큰 경우를 입력해보는 것으로 찾을 수 있다.

2748번: 피보나치 수 2

2748번 문제는 정수 N(1 ≤ N ≤ 90)이 주어졌을 때, N번째 피보나치 수를 구하는 문제이다.

#include <iostream>
using namespace std;
int fibo[100] = {0,1};
int main() {
    int n;
    cin >> n;
    for (int i=2; i<=n; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2];
    }
    cout << fibo[n] << '\n';
    return 0;
}

이렇게 구현하고 예제를 넣어보면 정답이 나온다. 1 ≤ N ≤ 90 이니 3, 4, 5와 같이 입력을 넣어도 정답이 나온다. 하지만 제출하면 틀렸습니다를 받게 된다. 이유는 문제의 정답이 int 범위를 넘어가기 때문이다.

제한이 1 ≤ N ≤ 90 인데 가장 큰 값인 90을 넣어보면 오버플로가 발생해 정답으로 -1581614984을 출력하는 것을 발견할 수 있다. (환경에 따라 다르며, 오버플로가 발생했을 때 행동에 대해 정의되어 있지 않기 때문에 무슨 값이 나올지 알 수 없음, Java는 오버플로가 발생했을 때가 정의되어 있음)

보통 오버플로가 발생하면 음수가 나온다. N번째 피보나치 수는 절대로 음수가 나오지 않기 때문에, 여기서 잘못되었다는 것을 알 수 있다.

올바르게 구현을 수정하려면 int fibo[100]long long fibo[100]으로 변경하면 된다.


메시지 확인

2430번: 거울대칭트리 그래프

그래프가 거울대칭트리 그래프이면 YES를 아니면 NO를 출력해야 한다.

15900번: 나무 탈출

게임을 이길 수 있으면 Yes를, 아니면 No를 출력해야 한다.

1876번: 튕기는 볼링공

볼링공이 핀을 맞추면 yes를, 아니면 no를 출력해야 한다.

이런 문제를 풀 때는 YES/NO를 출력해야 하는지, Yes/No를 출력해야 하는지, yes/no를 출력해야 하는지 확인해야 한다. 보통 채점은 대/소문자를 구분하기 때문이다.

폴란드 문제는 TAK/NIE, 크로아티아 문제는 DA/NE를 출력하기도 한다.


의도와 다른 표현

2562번: 최댓값

9개의 자연수가 입력으로 주어졌을때, 최댓값과 그 위치를 찾는 문제이다. Python으로는 다음과 같이 구현할 수 있다. 잘못된 부분을 찾아보자.

n = 9
a = [int(input()) for _ in range(n)]
ans = max(a)
print(ans)
for i in range(n):
    if a[i] == ans:
        print(i+1)
        break

잘못된 부분은 없다.

2566번: 최댓값

9×9 격자판에 81개의 자연수가 있을때, 최댓값과 그 위치를 찾는 문제이다.

이 문제는 2562번 문제의 2차원 버전이라고 볼 수 있고, 다음과 같이 구현했다.

import sys
n = 9
a = [list(map(int,input().split())) for _ in range(n)]
ans = max(max(a))
print(ans)
for i in range(n):
    for j in range(n):
        if a[i][j] == ans:
            print(i+1,j+1)
            sys.exit(0)

잘못된 부분은 ans = max(max(a))이다.

max(a)는 리스트에서 가장 큰 값 또는 사전 순으로 마지막에 오는 값을 찾는 함수이다.

a가 리스트의 리스트이기 때문에, max(max(a))a[0], a[1], …, a[n-1]에서 사전 순으로 가장 뒤에가는 리스트를 찾고, 거기서 최댓값을 찾는 것과 같은 의미이다.

예를 들어, d = [[1, 2, 3], [0, 9, 9]]인 경우 max(d)[1, 2, 3]이고, max(max(d))는 3과 같다.

이 문제에서는 ans = max(max(row) for row in a)로 변경해야 한다.


비효율적인 함수 호출

1157번: 단어 공부

길이가 100만 이하인 문자열 S가 주어졌을 때, 가장 많이 사용된 문자를 찾는 문제이다.

이 문제를 C/C++에서 char * 자료형을 이용해 푼다면, 보통 다음과 같이 계산한다. cnt[i]i번째 알파벳이 사용된 개수이다.

for (int i=0; i<strlen(s); i++) {
    if (s[i] >= 'a') {
        cnt[s[i]-'a'] += 1;
    } else {
        cnt[s[i]-'A'] += 1;
    }
}

여기서 문제가 되는 부분은 strlen(s)이다. N을 문자열 S의 길이라고 했을때, 위의 소스는 시간 복잡도 O(N)을 의도하고 만든 코드이다. 하지만, 실제로는 O(N2)에 수행된다.

for에서 i<strlen(s)는 종료되기 전까지 계속 수행된다. strlen(s)은 O(N)이고, for의 반복 횟수는 N번이니, 총 O(N2)이다.

문자열 S는 변하지 않으니 S의 길이도 변하지 않는다. 변하지 않는 값을 매번 계산하는 것은 비효율적이기 때문에, 문자열의 길이를 다른 변수에 저장해야 한다.

int len = strlen(s);
for (int i=0; i<len; i++) {
    if (s[i] >= 'a') {
        cnt[s[i]-'a'] += 1;
    } else {
        cnt[s[i]-'A'] += 1;
    }
}

컴파일러의 최적화로 인해 strlen(s)를 소스 코드에서 계속 호출하게 구현해도, 실행될 때는 알아서 최적화가 되는 경우가 있기도 하다.

9324번: 진짜 메시지

이 문제에서 진짜 메시지인지 아닌지 검사하는 부분을 다음과 같이 구현하면 O(N2)이다. 하지만, 실제로 수행 실행은 O(N) 소스와 같다.

bool valid() {
    vector<int> cnt(256);
    for (int i=0; i<strlen(s); i++) {
        char ch = s[i]-'A';
        cnt[ch] += 1;
        if (cnt[ch] % 3 == 0) {
            i += 1;
            if (i >= strlen(s) || s[i]-'A' != ch) {
                return false;
            }
        }
    }
    return true;
}

컴파일러 최적화를 믿기보다는 소스 코드를 작성할때 불필요한 함수의 반복된 호출을 줄이는 것이 더 좋다.


C++의 std::string과 Java의 String

C++ std::string에서 .length() 또는 .size()의 시간 복잡도는 O(1)이다.

Java String에서 .length()의 시간 복잡도는 O(1)이다.

따라서, 두 경우에는 i < s.length()와 같이 사용해도 된다.

N = 1,000,000이라고 했을때, 다음 C++ 소스는 O(N)이다.

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    int n = 1000000;
    for (int i=0; i<n; i++) {
        s += "A";
    }
    return 0;
}

std::stringoperator+=는 보통 std::vector::insert와 비슷하게 구현하기 때문에, 추가하려는 문자열의 길이만큼 시간이 걸린다.

다음 C++ 소스는 O(N2)이다.

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    int n = 1000000;
    for (int i=0; i<n; i++) {
        s = s + "A";
    }
    return 0;
}

s"A"를 뒤에 추가한 문자열을 operator=를 이용해 s로 복사하고 있다. operator=는 복사하려는 문자열의 길이와 같기 때문에, 매번 s의 길이가 길어져 O(N2)이 걸린다.

다음 Java 소스는 O(N2)이다.

import java.util.*;
public class Main {
    public static void main(String args[]) {
        String s = "";
        int n = 1000000;
        for (int i=0; i<n; i++) {
            s += "A";
        }
    }
}

C++의 std::string은 mutable이지만, Java의 String은 그렇지 않다. 따라서, 모든 s += "A";s의 뒤에 "A"를 추가하는 것이 아니고, 새로운 문자열 s + "A"를 만들고, 그것을 s라고 하는 것이다.

Java String st가 있고, 두 문자열의 길이를 각각 n, m이라고 했을때, s.concat(t), s + t 모두 O(n+m)이 걸린다.

따라서, 위의 소스는 O(N2)이 된다.

Java의 경우 문자열을 여러 번 합쳐야 하면 StringBuilder를 쓰는 것이 좋다.


Python과 시간 복잡도

a는 크기가 N인 리스트, b는 크기가 M인 리스트이다.

  • a = a + [1000001]
  • a.append(1000001)
  • a = a + b
  • a.extend(b)
  • a += b
  • 10 in a
  • len(a)

a + b의 시간 복잡도는 O(N+M)이다. 따라서, a = a + [1000001]는 O(N), a = a + b는 O(N+M)이다.

a.append(1000001)는 O(1)이고, a.extend(b)는 O(M)이다.

a += ba.extend(b)와 같기 때문에, O(M)이다.

10 in aa 전체를 순회해야 하기 때문에, O(N), len(a)는 O(1)이다.

Python의 시간 복잡도는 다음을 참고하는 것이 좋다.

https://wiki.python.org/moin/TimeComplexity


테스트 케이스 방식

테스트 케이스 방식의 문제에서 주로 시간 초과를 받는 이유 중 하나는 변하지 않는 값을 여러 번 계산하는 것이다.

15988번: 1, 2, 3 더하기 3

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다. (1 ≤ n ≤ 1,000,000)

D[n] = 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수

라고 정의했을 때

정수 n을 합으로 나타내는 방법은 ? + ? + … + ? = n 이라고 볼 수 있다.

여기서 가장 마지막 ?에 올 수 있는 값은 1, 2, 3 중 하나이다.

따라서, 정수 n을 1, 2, 3의 합으로 나타내는 방법은 다음 3가지 밖에 없다고 볼 수 있다.

? + ? + … + 1 = n 인 경우는 합이 n – 1인 방법 뒤에 1을 더했다고 볼 수 있고,

? + ? + … + 2 = n는 합이 n – 2인 방법 뒤에 2를 더했다고 볼 수 있다. 3도 마찬가지로 구할 수 있다.

따라서, 1이 가장 뒤에 오는 방법의 개수는 D[n-1], 2가 가장 뒤에 오는 방법의 개수는 D[n-2], 3이 가장 뒤에 오는 방법의 개수는 D[n-3]이라고 볼 수 있다.

따라서, D[n] = D[n-1] + D[n-2] + D[n-3]으로 식을 완성할 수 있다.

#include <iostream>
using namespace std;
long long d[1000001];
const long long mod = 1000000009LL;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        d[0] = 1;
        for (int i=1; i<=n; i++) {
            d[i] = 0;
            if (i-1 >= 0) {
                d[i] += d[i-1];
            }
            if (i-2 >= 0) {
                d[i] += d[i-2];
            }
            if (i-3 >= 0) {
                d[i] += d[i-3];
            }
            d[i] %= mod;
        }
        cout << d[n] << '\n';
    }
    return 0;
}

위의 소스를 제출하면 맞았습니다!!를 받게 되고, 수행 시간은 376ms이다. 이 소스의 일부를 수정하면 수행 시간을 16ms로 줄일 수 있다.

테스트 케이스 방식의 문제는 답을 하나만 구하면 되는 문제를 테스트 케이스의 개수 T번 반복하면 되는 것이다.

이때 변하지 않는 값은 여러 번 구할 필요가 없다.

다이나믹 프로그래밍은 Optimal Substructure를 만족하고, 그렇기 때문에 어떤 한 문제의 정답은 언제 구해도 변하지 않는다.

D[8]을 구하려면 D[8] = D[7] + D[6] + D[5]이고, D[7] = D[6] + D[5] + D[4], D[6] = D[5] + D[4] + D[3], … 이다. D[8]을 구하려면 D[4]의 값이 필요하다.

D[8]을 구하기 위해서 구하는 D[4], D[7]을 구하기 위해서 구하는 D[4], D[6]을 구하기 위해서 구하는 D[4], …에서 D[4]는 항상 같은 값을 가진다.

따라서, 이 경우 각 테스트 케이스마다 정답을 구하는 것 보다, n의 최댓값인 1,000,000까지 답을 미리 구해놓고, 출력만 하는 것이 훨씬 시간이 빠르다.

테스트 케이스의 개수를 T, n의 최댓값을 N이라고 한다면

위에 나온 것처럼 매번 답을 구하는 방식의 소스는 O(TN)이고, 아래와 같이 답을 미리 구해놓는 방식은 O(N+T)라 볼 수 있다.

#include <iostream>
using namespace std;
long long d[1000001];
const long long mod = 1000000009LL;
int main() {
    d[0] = 1;
    for (int i=1; i<=1000000; i++) {
        if (i-1 >= 0) {
            d[i] += d[i-1];
        }
        if (i-2 >= 0) {
            d[i] += d[i-2];
        }
        if (i-3 >= 0) {
            d[i] += d[i-3];
        }
        d[i] %= mod;
    }
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << d[n] << '\n';
    }
    return 0;
}

이 문제와 같이 테스트 케이스 문제 이면서, 답을 미리 구해놓을 수 있는 경우에는 미리 구하는 것이 시간이 적게 걸린다.

또다른 예시로 소수가 있다. 테스트 케이스 방식의 문제이고, 1,000,000 이하의 모든 소수가 필요한 경우, 이 소수를 미리 구해놓으면 시간을 크게 향상시킬 수 있다.

다른 예시로 다음을 살펴보자.

다음 C++ 함수는 숫자로 이루어진 문자열 S를 정수로 변환하는 함수이다. 문자열의 길이가 길어 오버플로가 발생하는 경우는 없다고 가정한다.

int str_to_int(string s) {
    int num = 0;
    for (int i=0; i<s.length(); i++) {
        num += (s[i] - '0') * pow(10, s.length()-1-i);
    }
    return num;
}

문자열 S의 길이를 N이라고 한다면, str_to_int의 시간 복잡도는 어떻게 될까?

O(N)으로 볼 수 있지만, 실제로는 O(N2)이다. 그 이유는 pow 함수 때문이다.

pow(a, b)는 a의 b제곱을 구하는 함수로 시간 복잡도는 O(b)일 수도 있고, O(lgb)일 수도 있다. 라이브러리나 언어에 따라서 다르고, 직접 구현한 경우도 어떻게 구현했는지에 따라 다르다.

소스 코드를 보면 항상 pow(10, x)의 꼴만 사용하고 있다. 10x도 변하지 않는 값이기 때문에, ten[i] = 10i를 미리 계산해놓았다고 한다면, 시간을 크게 향상시킬 수 있다.

str_to_int 함수를 M번 호출한 경우 위의 소스는 O(MN2), 미리 계산해놓고 다음과 같은 소스를 이용한 경우 O(MN)으로 볼 수 있다.

int str_to_int(string s) {
    int num = 0;
    for (int i=0; i<s.length(); i++) {
        num += (s[i] - '0') * ten[s.length()-1-i];
    }
    return num;
}

지역 변수와 전역 변수

15988번: 1, 2, 3 더하기 3를 다음과 같이 구현하면 틀렸습니다를 받게 된다.

#include <iostream>
using namespace std;
const long long mod = 1000000009LL;
int main() {
    long long d[1000001];
    d[0] = 1;
    for (int i=1; i<=1000000; i++) {
        d[i] = 0;
        if (i-1 >= 0) {
            d[i] += d[i-1];
        }
        if (i-2 >= 0) {
            d[i] += d[i-2];
        }
        if (i-3 >= 0) {
            d[i] += d[i-3];
        }
        d[i] %= mod;
    }
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << d[n] << '\n';
    }
    return 0;
}

차이점은 long long d[1000001];의 위치이다.

d를 지역 변수로 선언했는데, 지역 변수는 변수의 초기값이 무엇일지 알 수 없다. 따라서, d[0]을 제외한 나머지 d[i]에는 어떤 값이 들어있을지 알 수 없다.

지역 변수를 사용할 경우에는 초기값이 필수이다.

환경에 따라서는 정답이 나올 수 있다. 어떤 환경에서는 지역 변수가 0으로 초기화 되어 있을 수도 있다.

지역 변수는 메모리의 스택 영역에 저장되는데, 이 스택의 크기는 환경에 따라 다르다. 보통은 8MB 정도라서, 지역 변수의 크기가 너무 크면 스택 오버 플로가 발생한다. 스택 오버 플로는 재귀 함수를 호출할 때도 생길 수 있다.

이때는

  • 스택의 크기를 늘리거나 (ulimit 사용)
  • 재귀 함수 때문에 발생한 경우 비재귀 방식으로 바꾸거나
  • 지역 변수를 동적 할당이나 전역 변수로 바꾸는

방법을 사용하는 것이 좋다.

참고로 Python은 재귀의 깊이가 제한되어 있어, 재귀 함수 때문에 런타임 에러가 발생한 경우 sys.setrecursionlimit로 재귀 제한을 변경해야 한다.


나머지 연산

15988번: 1, 2, 3 더하기 3를 다음과 같이 구현한 경우에도 틀렸습니다를 받게 된다.

#include <iostream>
using namespace std;
int d[1000001];
const int mod = 1000000009;
int main() {
    d[0] = 1; d[1] = 1; d[2] = 2; d[3] = 4;
    for (int i=4; i<=1000000; i++) {
        d[i] = (d[i-1] + d[i-2] + d[i-3]) % mod;
    }
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << d[n] << '\n';
    }
}

이 문제는 방법의 수를 10억 9로 나눈 나머지를 구해야 한다. 따라서, d[i] = (d[i-1] + d[i-2] + d[i-3]) % mod;와 같이 구현해 나머지 값을 저장하게 했다.

int에는 -231보다 크거나 같고, 231-1보다 작거나 같은 값만 저장할 수 있다.

0 ≤ d[i] < mod 이고, d[i]를 3개 더하면 0 ≤ d[i-1] + d[i-2] + d[i-3] < 3×mod 이다.

3×mod는 약 30억이고, int의 최댓값은 약 21억이니 오버플로가 발생해 틀리게 된다.

이 경우에는

  • dmodlong long으로 바꾸거나
  • d[i] = ((d[i-1] + d[i-2]) % mod + d[i-3]) % mod;로 바꾸는 방법이 있다.

Python과 나머지 연산

Python은 int의 크기가 제한이 없기 때문에, 15988번: 1, 2, 3 더하기 3를 다음과 같이 구현해도 된다. (제한이 없는 것은 아니고 사용할 수 있는 메모리와 관련이 있다)

d = [0]*1000001
mod = 1000000009
d[0] = 1
for i in range(1, 1000000+1):
    if i-1 >= 0:
        d[i] += d[i-1]
    if i-2 >= 0:
        d[i] += d[i-2]
    if i-3 >= 0:
        d[i] += d[i-3]
t = int(input())
for _ in range(t):
    n = int(input())
    print(d[n]%mod)

C++, Java는 위와 같이 구현하면 오버 플로 때문에 틀렸습니다를 받지만, Python은 시간 초과를 받는다.

바로 그 이유는 나머지 연산을 출력하기 전에만 했기 때문이다.

C++, Java, Python에서 두 정수의 덧셈은 시간 복잡도가 O(1)이 맞다. Python의 경우 정수의 크기가 커지면 시간이 오래 걸린다. 따라서, 이 문제의 가장 큰 정답은 264,650자리이기 때문에, 시간 안에 정답을 구할 수 없다.

Python의 내부 정수 구현은 http://www.secmem.org/blog/2019/07/21/python-biginteger2/ 또는 https://rushter.com/blog/python-integer-implementation/ 글을 참고하면 된다.


함수의 리턴

C++의 경우 리턴을 해야 하는 함수가 리턴을 하지 않으면 런타임 에러가 발생할 수 있다.

예시를 위해 다음과 같은 함수를 만들었다.

int sum(int n) {
    for (int i=1; i<=n; i++) {
        if (n == i) {
            return n*(n+1)/2;
        }
    }
}

sum(n)은 1부터 n까지 합을 구하는 함수이다.

n ≥ 1인 경우에는 답을 구할 수 있다. 오버 플로로 인해 이상한 답이 리턴되는 경우, n이 너무 커서 시간이 오래 걸리는 경우도 있지만, 예시를 위해 작성한 이상한 함수이기 때문에, 그런 경우는 생각하지 않기로 한다.

sum(0)인 경우에 런타임 에러가 발생한다.

n ≤ 0이면 return되는 부분이 없어서 런타임 에러가 발생할 수 있다.

return이 없어도 런타임 에러가 발생하지 않으면서 쓰레기 값이 리턴될 수도 있고, 함수 내의 어떤 변수의 값이 리턴될 수도 있지만, 이런 경우는 이 글이 너무 길어지니 생략한다. void가 아닌 모든 함수는 리턴을 해야한다.

참고로 위의 소스를 컴파일 하면 다음과 같은 경고 메시지를 받을 수 있다.

Main.cc: In function ‘int sum(int)’:
Main.cc:11:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

경고 메시지를 무시하지 않는다면, 이 문제를 미리 발견할 수 있다.


Exit code

Exit code는 프로그램이 종료될때 리턴되는 값이다. 0은 프로그램의 정상 종료, 0이 아닌 값은 정상 종료가 아닌 것이다. 따라서, 0이 아닌 값으로 종료되면 오류의 발생으로 생각해 런타임 에러를 받을 수 있다.

C++ main 함수가 0을 리턴하면서 종료하거나, exit(0);을 호출해 종료해야하고, Java에서는 System.exit(0);, Python은 sys.exit(0)으로 종료해야 한다.

exit 함수는 항상 호출해야 하는 것은 아니고, 프로그램 중간에 종료할 때이다. 별도의 처리가 없어도 모두 0을 리턴하면서 프로그램이 종료되었다고 본다.


배열의 인덱스 범위

배열에서 존재하지 않는 인덱스를 접근했을 때, 발생하는 에러이며 가장 많이 런타임 에러를 받는 이유 중 하나이다.

C++의 경우는 존재하지 않는 인덱스를 접근해도 별 문제없이 넘어가는 경우도 있지만, Java와 Python은 접근하는 순간 바로 에러를 발생시킨다.

11726번 문제: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 크기의 타일로 채우는 방법의 수를 구하는 문제이다. (1 ≤ n ≤ 1,000)

D[n]을 2×n 크기의 직사각형을 채우는 방법의 수라고 정의하면, n번째 열을 채우는 방법은 다음 두 가지 밖에 없다.

왼쪽의 경우는 크기가 2×(n-1)인 직사각형을 만든 다음 세로 타일을 놓아서 2×n을 만든 것이라고 볼 수 있고, 오른쪽의 경우는 크기가 2×(n-2)인 직사각형에 가로 타일 두 개를 놓아서 2×n을 만든 것이라 볼 수 있다.

따라서, 왼쪽 방법의 수는 D[n-1], 오른쪽 방법의 수는 D[n-2]이고, 이 두 방법만이 2×n을 만드는 방법이다.

따라서, D[n] = D[n-1] + D[n-2]이고, 다음과 같이 코드를 작성할 수 있다.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> d(n+1);
    d[1] = 1;
    d[2] = 2;
    for (int i=3; i<=n; i++) {
        d[i] = d[i-1] + d[i-2];
        d[i] %= 10007;
    }
    cout << d[n] << endl;
    return 0;
}
import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n+1];
        d[1] = 1;
        d[2] = 2;
        for (int i=3; i<=n; i++) {
            d[i] = d[i-1] + d[i-2];
            d[i] %= 10007;
        }
        System.out.println(d[n]);
    }
}
n = int(input())
d = [0]*(n+1)
d[1] = 1
d[2] = 2
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]
    d[i] %= 10007
print(d[n])

C++은 맞았습니다!!를 받을 수 있지만, Java와 Python은 런타임 에러를 받게 된다. 그 이유는 무엇일까?

대부분의 경우에 에러 없이 문제의 정답을 구할 수 있지만, 반례가 하나 있다.

그 반례는 바로 n = 1일때이다.

n = 1인 경우 n+1은 2이고, Java와 Python에서 d의 크기는 2가 된다. 여기서 d[2]는 존재하지 않는다.

존재하지 않는 인덱스에 접근하면 Java는 java.lang.ArrayIndexOutOfBoundsException, Python은 IndexError: list assignment index out of range가 발생하게 된다. 따라서, 런타임 에러가 발생한다.

해결하는 방법은 여러가지가 있는데

  • d의 크기를 n+2로 바꾸거나
  • d[2]를 채우기 전에 조건문을 추가하거나
  • 초기값을 d[0] = 1, d[1] = 1로 바꾸는 방법

등이 있다.


최솟값, 최댓값 그리고 초기값

1912번: 연속합

n개의 정수로 이루어진 수열 A가 있을 때, 연속된 몇 개의 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제이다. 수는 한 개 이상 선택해야 한다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

예를 들어 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열에서 정답은 12+21인 33이다.

다이나믹 프로그래밍으로 이 문제를 해결한다면,

D[i] = i번째 수에서 끝나는 연속합의 최댓값

으로 정의하고

D[i] = max(A[i], D[i-1] + A[i])

로 식을 세울 수 있다.

문제의 정답은 모든 D[i]의 값 중 최댓값이다.

따라서, 다음과 같은 소스로 해결할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    vector<int> d(n);
    for (int i=0; i<n; i++) {
        d[i] = a[i];
        if (i == 0) continue;
        if (d[i] < d[i-1] + a[i]) {
            d[i] = d[i-1] + a[i];
        }
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        if (ans < d[i]) {
            ans = d[i];
        }
    }
    cout << ans << '\n';
    return 0;
}

소스는 입력받고, d[i]의 값을 구한 다음, 최댓값은 ans에 저장하고 출력하는 것으로 구성되어 있다.

반례는 모든 수열의 값이 음수인 경우이다. 모든 수가 음수면 모든 d[i]의 값이 음수이고, 최댓값의 초기값을 0으로 했기 때문에, 문제의 정답으로 0을 구하게 된다.

ans의 초기값을 가능한 문제 정답의 최솟값인 -1000이나 그 이하의 정수로 변경해서 해결할 수 있다.

또다른 방법으로는 정답은 d[0], d[1], …, d[n-1]중 하나이기 때문에, 초기값으로 d[0]을 넣는 방법도 있다.

반례는 문제에 따라 다르고, 소스 코드의 구현, 상황에 따라 다르지만, 매우 작거나 큰 경우, 또는 데이터가 극단적으로 치우쳐있는 경우를 입력해서 찾기도 한다.

이 문제의 경우 반례를 찾기 위한 데이터로 다음을 생각해볼 수 있다.

  • n = 1, A = [0]
  • n = 1, A = [1]
  • n = 1, A = [-1]
  • n = 2, A = [-1000, 1000]
  • n = 100,000, A = [1000] * n
  • n = 100,000, A = [0] * n
  • n = 100,000, A = [-1000] * n

[i] * nin개 들어있는 수열을 의미한다.


테스트 케이스의 순서

테스트 케이스 방식의 문제를 풀 때는 각 테스트 케이스를 수행하기 전에 사용될 배열을 모두 초기화 해야 한다.

20053번: 최소, 최대 2

이 문제는 N개의 정수 중에 최솟값과 최댓값을 구하는 문제이고, 테스트 케이스 방식이다.

다음과 같은 소스로 해결할 수 있다.

#include <iostream>
using namespace std;
int a[1000000]; 
int main() {
    int t, n;
    int ans_min = 1000000, ans_max = -1000000;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i=0; i<n; i++) {
            cin >> a[i];
        }
        for (int i=0; i<n; i++) {
            if (ans_min > a[i]) {
                ans_min = a[i];
            }
            if (ans_max < a[i]) {
                ans_max = a[i];
            }
        }
        cout << ans_min << ' ' << ans_max << '\n';
    }
    return 0;
}

이 소스의 놀라운 점은 예제의 정답은 나온다는 것이다. 하지만, 제출하면 틀렸습니다를 받게 된다.

그 이유는 테스트 케이스의 수행 전에 초기화를 하지 않았기 때문이다.

문제의 예제는 초기화를 하지 않은 경우를 의도하고 최솟값은 내림차순, 최댓값은 오름차순을 이루게 만들었다.

이런 경우에는 문제 테스트 케이스의 순서를 바꿔서 실행해보는 것으로 찾을 수 있다. 문제의 예제를 순서만 바꾼

3
5
30 21 17 25 29
5
20 28 22 25 21
5
20 10 35 30 7

를 입력해보면, 틀린 답을 출력하는 것을 찾을 수 있다.


&&와 ||

2차원 배열에서 BFS를 하는 경우 다음과 같은 표현을 많이 사용하게 된다.

if (0 <= nx && nx < n && 0 <= ny && ny < m && a[nx][ny] == 0)

이동하려는 칸 (nx, ny)가 2차원 배열의 범위 안에 있고, a[nx][ny]의 값이 0이면 이라는 뜻이다.

이 표현을 아래와 같이 순서를 바꿔서 사용하면 안된다.

if (a[nx][ny] == 0 && 0 <= nx && nx < n && 0 <= ny && ny < m)

C++, Java, Python 모두 조건 A && B 에서 Afalse이면 b는 검사하지 않고, 조건 A || B에서 Atrue이면 B는 검사하지 않기 때문이다.


가능한 답이 여러가지인 경우

2580번: 스도쿠

이 문제는 스도쿠 퍼즐을 해결하는 문제이고, 출력 부분을 보면 “스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.” 라는 말이 써있다.

이런 문제의 경우 하나를 출력하고 프로그램을 종료하지 않으면 틀렸습니다 또는 출력 초과를 받게 된다.


불가능한 경우 -1

1153번: 네 개의 소수

이 문제의 출력 부분에는 “불가능한 경우는 -1을 출력한다.” 라는 말이 적혀있다.

어떻게 구현을 했는지에 따라 다르지만, 불가능한 경우를 정답을 구하기 전에 찾을 수 있는 경우에 -1을 출력하고 프로그램을 종료하지 않으면 틀렸습니다 또는 출력 초과를 받게 된다.

10453번: 문자열 변환

이 문제는 테스트 케이스 방식의 문제이고, 불가능한 경우에는 -1을 출력해야 한다.

테스트 케이스 방식이 아니면 프로그램을 종료해도 되지만, 테스트 케이스 방식일때는 종료하면 안된다.

예를 들어, 문제 예제에서 -1을 출력하는 부분이 가장 마지막 테스트 케이스였다면, 예제의 정답은 구하지만, 제출하면 틀리는 상황이 된다.

종료하지 않게 수정하는 것으로 해결할 수 있고, 위에서 언급한 것 처럼 테스트 케이스의 순서를 바꾸는 것으로 디버깅해볼 수 있다.


자료형 (unsigned)

C++ STL의 .size()는 자료형이 unsigned이기 때문에 다음 소스를 실행하면 “!”가 출력된다.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> a;
    for (int i=0; i<a.size()-1; i++) {
        cout << "!";
    }
    return 0;
}

a.size()는 0이고, 여기서 1을 빼면 -1이 아니기 때문이다. 이 소스를 컴파일 하면 다음과 같은 경고 메시지가 나오고, 이를 보고 고칠 수 있다.

Main.cc: In function ‘int main()’:
Main.cc:7:20: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
     for (int i=0; i<a.size()-1; i++) {
                   ~^~~~~~~~~~~

(int)a.size()로 자료형을 바꿔서 해결할 수 있다.


자료형 (int, long long)

또, 260을 출력하기 위해 1 << 60를 출력한 경우 0을 출력하게 된다.

#include <iostream>
using namespace std;
int main() {
    cout << (1 << 60) << endl;
    return 0;
}

이유는 1 << 60에서 1이 int이기 때문이다. 1LL << 60으로 바꿔서 해결할 수 있다. 컴파일러의 경고 메시지는 다음과 같다.

Main.cc: In function ‘int main()’:
Main.cc:5:19: warning: left shift count >= width of type [-Wshift-count-overflow]
     cout << (1 << 60) << endl;
                   ^~

경고 메시지를 보고 눈치챌 수 있다.


기타

  • 입력 또는 출력 속도 때문에 시간 초과를 받는 것 같은 경우 다음을 참고한다.
  • Python에서 어떤 값이 같은지 비교할 때 == 대신에 is를 사용하면 안된다.
  • Java에서 객체의 비교는 ==이 아니고 .equals이다.
  • Java에서 Arrays.sort를 사용하는 경우 수열을 섞고 사용해야 한다.
  • C++에서 endl은 느리기 때문에, '\n'을 사용한다.
  • 입력의 크기가 너무 큰 경우 작게 만들어서 디버깅 해본다.
    • 16928번: 뱀과 사다리 게임의 경우 항상 지도의 크기가 100으로 고정되어 있어 디버깅하기 어렵다. 10, 20 정도의 작은 값으로 변경해서 디버깅할 수 있다.
  • Java나 Python을 사용하는 경우 깊은 복사(Deep copy)와 얕은 복사(Shallow copy)에 대해서 꼭 공부한다.

읽어보면 좋은 글