PS (Problem Solving)/개념

PS를 할 때, 유의할 점!

공대사람 2016. 10. 17. 17:05

PS를 배우기 전에 미리 알아두면 좋은 사항들이 있습니다.

PS를 해본 사람들에겐 당연하지만, 처음 접하는 사람들에겐 전혀 당연하지 않은 사항들이라고 생각해 따로 글을 쓰게 되었습니다. 저 또한 처음엔 이런 점들을 잘 몰랐구요! PS를 처음 접하시는 분들에게 조금이라도 도움이 되길 바랍니다.



1. 전역변수


여태까지는 전역변수를 사용하면 코드 재사용시 프로그램의 안정성에 좋지 않다는 등의 이유로, 전역변수를 가급적이면 사용하지 않는 것이 좋다고 배워왔습니다. 하지만, PS를 할 때는 전역변수를 적극적으로 사용하는 것이 좋습니다. 예를 들어 보겠습니다.


어떤 배열(arr)이 있을 때, s번째 칸부터 e번째 칸까지의 합을 구하는 함수 sumOfArray가 있다고 해보겠습니다.


<문제상황>



그러면, 함수 sumOfArray는 어떤 변수들을 함수의 파라미터로 받아야 할까요?


① 시작칸 s

② 끝칸 e

③ 합을 구하는 대상이 되는 배열 arr


총 세 가지의 변수를 파라미터로 받아줘야겠죠?

아래가 함수 sumOfArray를 C++로 구현한 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <stdio.h>
#include <vector>
 
using namespace std;
 
int sumOfArray(int s, int e, int arr[])
{
    int ret = 0;
 
    for(int i=s; i<=e; i++)
        ret += arr[i];
 
    return ret;
}
cs

<전역변수를 사용하지 않은 sumOfArray의 구현>



하지만, 이러한 구현에는 문제점이 있습니다. PS에서는 시간이 가장 큰 제약조건입니다. 그런데, 이 함수에선 쓸데없는 작업에 많은 시간을 할애하고 있습니다. 함수 sumOfArray가 실행될 때, 일어나는 동작들은 다음과 같습니다.


① s, e, arr값 모두 복사(Call by value의 특성상 값을 모두 복사해옵니다.)

② arr[s] 부터 arr[e]까지를 ret값에 더함

③ ret값을 리턴


그런데,  ①번을 잘 보면 할 필요 없는 작업들을 하고 있다는 것을 알 수 있습니다. arr의 값을 모두 복사해오는 작업은 사실상 필요없는 작업이겠죠? 처음부터 arr자체를 참조하면 되니까요. 

만약 arr가 1000000000칸이었으면 어떻게 될까요? 혹은 sumOfArray함수를 10000번 호출하면 어떻게 될까요? 

쓸데없는 작업에 너무 많은 시간을 할애하게 될 것입니다. 

그래서 이러한 상황을 방지하기 위해, PS를 할 땐 전역변수를 적극적으로 활용하게 됩니다. 


전역변수를 활용해서 sumOfArray함수를 작성해보겠습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <stdio.h>
#include <vector>
 
using namespace std;
 
int s, e, arr[1000];
 
int sumOfArray()
{
    int ret = 0;
 
    for(int i=s; i<=e; i++)
        ret += arr[i];
 
    return ret;
}
cs

<전역변수를 사용한 sumOfArray의 구현>



s, e, arr[]가 모두 전역변수이기 때문에 함수 sumOfArray 내부에서 (파라미터로 넘겨주지 않아도) 참조가 가능하게 됩니다. 즉, 전역변수를 사용하면 값들을 복사해오는데 드는 쓸데없는 시간을 절약해주는 것 뿐만 아니라 파라미터로 변수들을 넘겨주는 수고스러움도 덜 수가 있습니다. 만약 함수에 넘겨줘야 하는 파라미터의 개수가 5개 이상만 되더라도 굉장히 귀찮은 작업이 될 것입니다. 


만약, 전역변수보다 함수의 파라미터로 변수를 넘겨주는 것이 더 의미가 명확한 경우 C++의 참조자(reference)를 이용하여 넘겨주면, 값을 복사해오는 쓸데없는 시간을 없앨 수 있습니다. 


의미가 명확하다는 것은 무슨 뜻일까요? 함수 sumOfArray의 경우에 대해 생각해봅시다. 함수 sumOfArray의 경우, 함수의 이름만 봐도 어떤 배열 내의 원소들의 합을 구하는 함수라는 것을 알 수 있습니다. 따라서, 해당 배열을 함수 내부에서 참조한다는 것이 자명함과 동시에, 해당 배열이 함수의 작동에 주된 영향을 끼치는 변수라는 것도 알 수 있습니다. 이러한 경우, 해당 변수를 전역 변수가 아닌 파라미터로 넘겨주는 것이 후에 오류를 잡아내는 것을 훨씬 수월하게 해줄 수 있습니다. (물론, 참조자로 넘겨주는 것이 좋겠죠??) 여기서, C++의 참조자는 C의 포인터와 같이 Call by reference와 비슷한 개념으로 이해하면 편합니다. 참조자를 이용하면 함수 sumOfArray를 다음과 같이 작성할 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <stdio.h>
#include <vector>
 
using namespace std;
 
int s, e, arr[1000];
 
int sumOfArray(vector<int> &arr)
{
    int ret = 0;
 
    for(int i=s; i<=e; i++)
        ret += arr[i];
 
    return ret;
}
cs

<참조자를 사용한 sumOfArray의 구현>



따라서, 이렇게 정리할 수 있습니다.


① 함수의 동작과 의미상 별로 관련이 없는 변수 -> 전역변수

② 함수의 동작과 의미상 관련이 있는 변수 -> 파라미터로 넘겨주되, 참조자로!



2. 동적 할당


배열의 크기를 입력받아 정하고 싶은 경우, malloc을 이용한동적 할당을 통해 구현하게 됩니다. 하지만, PS를 할 때 동적할당을 이용하면 시간 초과가 날 수도 있습니다. 테스트 케이스가 여러 개인 문제의 경우, 각 테스트 케이스마다 사용하는 모든 배열을 동적할당한다면 사소한 시간 차이가 무시 못할 시간차이가 될 수도 있기 때문입니다.


따라서, PS를 할 땐 입력으로 들어올 수 있는 최대 크기만큼 배열을 넉넉하게 잡아놓고 문제를 푸는 것이 좋습니다. 예시를 통해 이해해보도록 하겠습니다.


다음은 DP(Dynamic Programming, 동적 계획법)의 기본 문제라고 할 수 있는 RGB거리 문제입니다.


(출처 : https://www.acmicpc.net/problem/1149)



이 문제에서 입력으로 들어올 수 있는 집의 수는 최대 1000입니다. 하지만, 아래의 코드를 보면 1001행으로 배열을 선언한 것을 알 수 있습니다. 그 이유는, 배열을 0번째 칸부터가 아니라 1번째 칸부터 사용하기 위해서입니다. PS를 하다보면, 알고리즘 구현의 용이성을 위해, 배열의 0번째가 아닌 1번째부터 사용하는 경우가 자주 생깁니다. 


이 문제의 경우, d[i][]에 값을 채울 때, d[i-1][]을 참조해서 채우게 됩니다. 따라서, 0번째 행부터 채우면 -1번째 행을 참조하게 되어 오류가 나겠죠?? 이 외에도 여러 가지 경우가 있겠지만, 이러한 이유 때문에 이 문제에선 배열을 0번째 행이 아닌 1번째 행부터 채우게 되고, 그래서 1001행 짜리 배열을 선언하게 된 것입니다.  


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
  
using namespace std;
  
int d[1001][3];
int w[1001][3];
  
int main()
{
    int n;
    cin >> n;
  
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 3; j++)
            cin >> w[i][j];
    }
  
    for (int i = 1; i <= n; i++)
    {
        d[i][0] = min(d[i - 1][1], d[i - 1][2]) + w[i][0];
        d[i][1] = min(d[i - 1][0], d[i - 1][2]) + w[i][1];
        d[i][2] = min(d[i - 1][0], d[i - 1][1]) + w[i][2];
    }
  
    int ans = min(min(d[n][0], d[n][1]), d[n][2]);
  
    cout << ans << '\n';
}
cs



덧붙이자면, 위 문제 경우 입력의 개수가 1000개, 출력의 개수가 1개이기 때문에 입력 및 출력을 하는 개수가 많지 않아 괜찮지만, 만약 입출력을 해야 하는 개수가 많다면, cin이나 cout을 사용하지 않는 것이 좋습니다. cin, cout는 scanf, printf에 비해 느리기 때문입니다. 따라서, 특별한 경우가 아니라면 scanf, printf를 사용하는 것이 좋습니다. 


특히, 출력 데이터가 많은 경우 cout과 endl을 같이 사용하게 되는데, endl이 굉장히 느립니다. 따라서, endl 대신 '\n'을 사용하는 것을 권장합니다.



3. 언어


PS를 할 땐, 특수한 몇 가지 상황을 제외하고는 주로 C++을 사용합니다. 


(특수한 몇 가지 상황 중 하나에는 long long int 범위를 벗어나는 수에 대한 사칙연산을 해야 하는 경우가 있습니다. 이러한 문제의 경우, Python의 bigint를 이용해 문제를 풀기도 합니다.) 


여러가지 이유가 있겠지만 일단, Java나 Python보다 빠릅니다. 또, PS를 하다보면 코드 작성의 직관성 때문에 재귀함수를 자주 이용하게 되는데, Python의 경우 Recursion depth limit(재귀함수 호출 깊이에 제한이 있다는 뜻)이 있어 맞는 알고리즘의 코드라도 런타임 에러가 날 수도 있습니다. 


또한, PS를 할 때 STL이라는 C++의 라이브러리를 굉.장.히 자주 사용하게 됩니다. STL에는 기본적인 자료구조들(queue, stack, pair, vector, map)이 구현되어 있을 뿐만 아니라, 정렬 함수도 모든 경우의 자료구조에 대해 정렬을 할 수 있도록 구현되어 있습니다. 이러한 장점들 때문에 PS를 할 땐, 주로 C++을 사용하게 됩니다. 


정리하자면, 전역변수를 적극적으로 활용하고 동적할당을 자제하되 언어는 C++을 사용하는 것이 좋다고 할 수 있습니다.