코딩테스트 기초
1. 코딩테스트 접근법
알고리즘(Algorithm)은 문제를 해결하기 위한 절차나 방법을 말한다. 코딩 테스트나 인터뷰를 통과하기 위해서 알고리즘 공부를 어떻게 해야할까? 몇 가지 기준을 세우고 진행하는 게 좋다.
초급자: 2~3일
중급자: 2~3시간
고급자: 20~30분
자신이 초급자일 때는 2일 간 고민해보는 것도 좋지만, 고급자인데도 2일을 고민하는 건 시간 낭비일 수 있다. 문제를 풀기 위해 적절한 알고리즘을 찾아내는 능력을 기르는 게 핵심이다. 알고리즘 문제 풀이 능력을 기르기 위해선 다양한 알고리즘의 특징을 알고 문제 풀이를 통해 그 알고리즘으로 문제를 풀 수 있는 이유를 생각해봐야 한다.
2. 효율성과 최적화
무한대의 메모리와 시간이 있으면 어떤 풀이 방법이든 정답이 될 수 있다. 그러나 현실에서 자원은 유한하므로 효율성을 고려해서 풀이를 작성해야 한다. 일반적으로 프로그램 성능을 위해 가장 먼저 살펴보는 건 수행 시간이다.
2.1. 시간 복잡도
시간 복잡도(Time Complexity)는 문제의 크기를 측정하기 위한 방법이다. 시간 복잡도는 빅 오 표기법(Big-O notation)으로 표현한다. 예를 들어 입력값을 받아 1부터 N까지의 합을 계산한다고 생각해보자.
class BigONotation {
public static void main(String[] args) {
int n;
int sum = 0;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
sc.close();
for (int i=1; i<=n; i++) {
sum += i;
}
System.out.println(sum);
}
}더하기를 N번 반복하므로 시간 복잡도는 이다. 만일 1부터 N까지의 합을 구하는 계산을 N번 반복하면 어떻게 될까?
class BigONotation2 {
public static void main(String[] args) {
int n;
int sum = 0;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
sc.close();
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
sum += j;
}
}
System.out.println(sum);
}
}을 N번 반복하므로 시간 복잡도는 이 된다. 빅 오 표기법에서 상수는 복잡도에 미치는 영향이 미미하므로 표기하지 않는다.
실제 수행 시간?
1억의 데이터를 처리하는데 걸리는 시간은 대략 1초이다.
2.2. 메모리
일반적으로 메모리에서 많은 공간을 차지하는 건 배열이다. 배열은 배열의 크기*자료형의 크기만큼 공간을 사용한다.
class ArraySize {
public static void main(String[] args) {
int arr[10000]; // 10000*4B = 40000B = 39.06KB
int arr[10000][10000]; // 10000*10000*4B = 400000000B = 381.47MB
}
}
3. 입출력
프로그래밍 언어는 다양한 입력 방법을 제공한다. 입력 방법에 따라 속도 차이가 발생하므로 이를 감안해서 적절한 입출력 방식으로 풀이를 작성하는게 좋다.
3.1. 입력 속도 비교
1
C11
mmap
0.043
2
C11
fread
0.0799
3
C11
getchar
0.3496
4
C++17
ios_base::sync_with_stdio(false); cin.tie(NULL);
0.5938
5
C++17
ios_base::sync_with_stdio(false);
0.6348
6
java
BufferedReader, Integer.parseInt
0.6585
7
C11
scanf
0.9206
8
PyPy
int(sys.stdin.readline())
0.9229
9
PyPy
map(int,os.read(0, 100000000).split('\n'))
1.1169
10
PyPy3
map(int,os.read(0, 100000000).decode('utf-8').split('\n'))
1.5408
11
PyPy
int(raw_input())
1.925
12
C++17
cin.tie(NULL);
2.059
13
C++17
cin
2.1742
14
C# 6.0
int.Parse(Console.ReadLine())
2.9635
15
Python 3
map(int,os.read(0, 100000000).decode('utf-8').split('\n'))
4.4033
16
Python 3
int(sys.stdin.readline())
4.4394
17
Java
Scanner
4.8448
18
Python 2
map(int,os.read(0, 100000000).split('\n'))
4.8553
19
Python 2
int(sys.stdin.readline())
5.7471
20
PyPy3
int(sys.stdin.readline())
6.6291
21
Python 2
int(raw_input())
8.9765
22
Python 3
int(input())
12.4443
23
PyPy3
int(input())
17.3772
24
Python 2
input()
37.7823
25
PyPy
input()
110.3676
3.2. 출력 속도 비교
1
C11
fwrite
0.4423
2
C++17
ios_base::sync_with_stdio(false); cout << i << '\n';
0.827
3
C++17
ios_base::sync_with_stdio(false); cout.tie(NULL); cout << i << '\n';
0.8272
4
C++17
printf("%d\n",i);
0.8614
5
C11
printf("%d\n",i);
0.9118
6
C++17
cout << i << '\n';
0.9229
7
Java
BufferedWriter, bf.write(i + "\n");
0.9581
8
PyPy
for i in xrange(1,n+1): sys.stdout.write(str(i)+'\n')
0.9847
9
C++17
s += to_string(i) + '\n';를 이용해 문자열 하나로 만든 다음, 마지막에 cout << s << '\n';
1.1507
10
Java
StringBuilder를 이용해 문자열 하나로 만든 다음, System.out.println(sb);
1.1881
11
Java
BufferedWriter, bf.write(Integer.toString(i)); bf.newLine();
1.2556
12
PyPy3
for i in range(1,n+1): sys.stdout.write(str(i)+'\n')
1.3722
13
PyPy
print '\n'.join(map(str,xrange(1,n+1)))
1.3738
14
PyPy
sys.stdout.write('\n'.join(map(str,xrange(1,n+1))))
1.3772
15
PyPy
for i in xrange(1,n+1): print i
1.4968
16
Python 2
print '\n'.join(map(str,xrange(1,n+1)))
1.7621
17
Python 2
sys.stdout.write('\n'.join(map(str,xrange(1,n+1))))
1.7658
18
Java
PrintWriter
1.954
19
Python 3
print('\n'.join(map(str,range(1,n+1))))
2.3312
20
Python 3
sys.stdout.write('\n'.join(map(str,range(1,n+1))))
2.337
21
PyPy
sys.stdout.write(''.join(str(i)+'\n' for i in xrange(1,n+1)))
2.3935
22
PyPy
print ''.join(str(i)+'\n' for i in xrange(1,n+1))
2.3974
23
Python 2
sys.stdout.write(''.join(str(i)+'\n' for i in xrange(1,n+1)))
2.536
24
Python 2
print ''.join(str(i)+'\n' for i in xrange(1,n+1))
2.5372
25
PyPy3
for i in range(1,n+1): print(i)
3.051
26
Python 2
for i in xrange(1,n+1): print i
3.069
27
C# 6.0
StreamWriter
3.0959
28
PyPy3
sys.stdout.write('\n'.join(map(str,range(1,n+1))))
3.5625
29
PyPy3
print('\n'.join(map(str,range(1,n+1))))
3.566
30
Python 3
sys.stdout.write(''.join(str(i)+'\n' for i in range(1,n+1)))
3.6766
31
Python 3
print(''.join(str(i)+'\n' for i in range(1,n+1)))
3.6836
32
PyPy3
print(''.join(str(i)+'\n' for i in range(1,n+1)))
3.8326
33
PyPy3
sys.stdout.write(''.join(str(i)+'\n' for i in range(1,n+1)))
3.8339
34
C# 6.0
StringBuilder를 이용해 문자열 하나로 만든 다음, Console.Write(sb);
3.8562
35
Python 2
for i in xrange(1,n+1): sys.stdout.write(str(i)+'\n')
4.3475
36
Python 3
for i in range(1,n+1): sys.stdout.write(str(i)+'\n')
5.3699
37
Python 3
for i in range(1,n+1): print(i)
5.8186
38
PyPy
for i in xrange(1,n+1): os.write(1,str(i)+'\n')
10.4553
39
C++17
cout << i << endl;
11.5322
40
PyPy3
for i in range(1,n+1): os.write(1,(str(i)+'\n').encode('utf-8'))
12.0509
41
Python 2
for i in xrange(1,n+1): os.write(1,str(i)+'\n')
14.8269
42
Python 3
for i in range(1,n+1): os.write(1,(str(i)+'\n').encode('utf-8'))
18.2189
43
Java
System.out.println(i);
30.013
44
C# 6.0
Console.WriteLine(i);
30.1438
3.3. 입력 속도 향상
C++의 cin/cout은 scanf/prinf보다 느리다. 이 경우에 아래 코드를 추가하면 성능을 향상시킬 수 있다.
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}다만 이 방법은 편법이므로 주의사항을 지켜야 한다.
scanf/prinf와 섞어서 사용하지 말 것
싱글 스레드 환경에서만 사용할 것
자바의 경우 입력이 많을 때 Scanner 대신 BufferReader를 사용해서 속도를 높일 수 있다. 출력이 많은 경우에는 BufferWriter를 사용하거나 StringBuilder를 사용해서 한 번만 출력할 수 있다.
참고 자료
Last updated