[ps] 코딩 테스트 문제 풀이 유의사항

효율성

알고리즘 문제를 해결하는 어떤 코드를 작성했을 때, 얼마나 효율적인지 판단할 수 있는 기준이다. 수행 시간과 사용 메모리순으로 중요하다. 성능과는 관계 없지만 가독성이 좋은 코드를 작성하는 것도 중요하다.

• 부족한 메모리는 메모리 추가를 통해 해결할 수 있지만 부족한 시간은 해결할 수 없다. 문제에 따라 수행 시간보다 사용 메모리가 더 중요한 상황이 있을 수 있지만 대부분의 경우 수행시간이 더 중요하다.
• 수행 시간은 문제의 크기와 연결되기 때문에 문제를 해결할 때는 문제의 크기를 먼저 파악하고 적합한 해결 방법을 생각해야 한다.

수행 시간

입력의 크기 N에 대해서 수행 시간을 대략적으로 표현한다. 어떤 해결 방식을 적용하기 전에 미리 시간 복잡도를 계산해보고 적합한 수행 시간이라고 판단되면 적용한다. Big O 표기법을 사용한다. 즉, 최악의 경우에 시간이 얼마나 걸릴지 알 수 있다.

O(100000000)의 경우 수행 시간은 대략적으로 1초 정도라고 생각할 수 있다. 시간 제한이 있는 문제의 경우 대략적인 대입을 통해 문제 해결에 적합하지 않은 수행 시간의 해결 방법을 제외할 수 있다.

대략 1초가 걸리는 시간 복잡도

시간 복잡도	N
O(1)	-
O(log$^{N}$)	-
O(N)	100000000
O(N log$^{N}$)	5000000
O(N$^{2}$)	10000
O(N$^{3}$)	500
O(2$^{N}$)	20
O(N!)	10

문제를 통해 시간 복잡도를 파악

총 N명의 사람이 식당에 방문했다. 식당에는 메뉴판 1개가 있고 메뉴는 M개 있다. 주문한 모든 메뉴는 동시에 나오며 각 사람 I가 식사를 하는데 걸리는 시간은 ${A_i}$이다. 각 사람이 계산을 하는데 걸리는 시간은 O(P)이다.

• 한 명의 사람이 메뉴판을 읽는데 걸리는 시간은 O(M)이다.
• 모든 사람이 하나의 메뉴판을 읽는데 걸리는 시간은 O(NM)이다.
• 모든 사람이 식사를 마치는데 걸리는 시간은 O(max(${A_i}$))이다.
• 식사를 마친 후, 모든 사람이 한 줄로 서서 계산을 하는데 걸리는 시간은 O(NP)이다.

코드를 통해 시간 복잡도를 파악

int sum = 0;
for (int i = 1; i <= N; i++) {
	sum += i;
}

1부터 N까지의 합을 구하는 코드이다. 반복문으로 코드를 N번 수행한다. 시간 복잡도는 O(N)이다.

int sum = 0;
for (int i = 1; i <= N; i++) {
	for (int j = 1; j <= N; j++) {
    		if (i == j) {
        		sum += j;
    		}
	}
}

1부터 N까지의 합을 구하는 코드이다. 외부의 반복문으로 코드를 N번 수행한다. 내부의 반복문이 N번 수행되고 코드를 N번 수행한다. 시간 복잡도는 O(N$^2$)이다.

int sum = 0;
sum = N * (N + 1) / 2;

등차수열의 합 공식을 이용한 1부터 N까지의 합을 구하는 코드이다. 시간 복잡도는 O(1)이다.

사용 메모리

문제 해결에 사용된 메모리를 대략적으로 표현한다.

• 메모리 제한은 보통 여유롭게 주어지기 때문에 메모리 제한을 초과하는 경우는 문제 해결에 대한 접근이 잘못된 경우가 많다.
• 중복되는 값을 계속 저장하는 등 불필요한 메모리 낭비를 하지 않으면 대부분 사용 메모리 제한은 지켜진다.
• 보통 가장 많은 메모리를 사용하는 곳은 배열이다. (배열의 크기 * 자료형의 크기)

입출력

문제 해결에 사용되는 소스 코드에 입출력 코드가 포함되어 있는 경우이다.

Java 기준

• 입력이 적은 경우는 느리지만 간단하고 편리한 Scanner를 사용한다.
• 출력이 적은 경우는 느리지만 간단하고 편리한 System.out을 사용한다.
• 입력이 많은 경우는 BufferedReader를 사용한다.
• 출력이 많은 경우는 BufferedWriter를 사용한다.
• 출력 대상이 문자열인 경우 StringBuilder를 통해 하나의 문자열로 연결하여 출력한다.