BOJ: 코딩 테스트를 위한 길라잡이 (미완성)

들어가기에 앞서

미완성인 길라잡이입니다!!!!!
링크 지금 거의 다 깨져서 조만간 수정 예정입니다

최근 많은 기업들이 코딩테스트를 진행한다고 들었습니다. 왜 코딩 테스트를 진행할까요? 아직 기업 코딩 테스트에 목숨을 걸 나이는 아니지만, 아무래도 기업에서는 대학에서 커리큘럼을 모두 소화했다면 이 정도는 코딩해서 풀 수 있지 않을까라고 생각하기 때문 아닐까 합니다. 실제로 회사에서 해결하기를 원하는 과제가 엄청 대단한 수준을 요구하는 것 또한 아니고요. 하지만 많은 분들이 이를 굉장히 힘들어 합니다. 또 왜 이런 생고생을 해야 하냐고 물으시는 분들도 있습니다. 하지만 이런 간단한 과제조차 효율적으로 해결하지 못하고 또 버그를 내서 제대로 잡지 못한다면, 실무에서 코드가 훨씬 길어졌을 때도 마찬가지로 수렁에 빠질 것이라는 것이 제 생각입니다.

그럼에도 불구하고 제가 이런 글을 쓰는 이유는, 이 내용을 공부하면서 기초적인 프로그램의 기능 분할과 효율적으로 코딩하기, 시간 복잡도 계산하기 등의 다양한 기초적인 능력을 향상시킬 수 있기를 바라기 때문입니다. 대학에서 이렇게 100줄 남짓하면서도 컴팩트한 코드를 작성할 기회가 많지 않다고 들었습니다. 이번 기회에 뽑아 놓은 문제들을 차례차례 해결해 보면서, 내가 너무 눈 앞에 있는 시험에만 매달려 기초적인 부분들을 소홀히 했는지 되돌아보는 시간이 되었으면 합니다. 항상 생각하지만, 끝까지 시험에 합격하지 못하는 사람들은 지금 당장 5줄짜리 별 찍기도 못하는 사람이 아니라, 어떻게 하면 1주일만에 시험에 붙을 수 있냐면서 이리저리 공부 팁만 찾아다니고 문제 질문할 때 "그냥 풀이 알려주시면 안돼요?" 하는 사람들이었습니다. 자신이 과제를 할 때 그런 부류였다면... 어쩌겠어요. 처음부터 다시 해야죠.

왜 당신이 문제를 해결하지 못하는가?

두괄식으로 작성하겠습니다. 만약 당신이 제목을 보고 공감했다면 그 이유에 대한 매우 가능성 높은 해답은, 문제를 많이 안 풀었고, 그 결과 구현에 익숙하지 않기 때문입니다. 이 말에는 여러분이 C언어 문법에 미숙한 것, 이런 코딩 테스트에서 자주 사용되는 테크닉에 익숙하지 않은 것, 또는 프로그램을 어떤 구조로 작성해야 하는지에 대한 모든 것들이 함축되어 있습니다. 아마 제 생각에는 이러한 과정을 거치실 것 같습니다.

1. 아, 이렇게 이렇게 해서 이런 구현을 해야 하는구나.
2. 그런데 이걸 대체 어떻게 짜지? 엄청 복잡한데... 하나도 모르겠다
3. 일단 여기부터 코딩해 보자. 여기를 이렇게 저렇게 코딩하고...
4. 아 뭔가 꼬였는데? 그럼 이걸 풀기 위해서 여기를 고치고... 여기 고치는 거 맞긴 해??
5. ???????
6. 뭐야 시간 벌써 끝났어!

여기에 추가적으로 양념을 하자면 문제 이해를 잘못 해서 코딩을 다 하고 예제가 제대로 나오지 않는 시점에서 깨닫거나, 아니면 문제 이해를 제대로 했음에도 불구하고 그냥 맞왜틀을 외치거나... 하여튼 변수는 많고도 또 많습니다.

해결책은 간단합니다. 문제를 많이 푸시면 됩니다. 인터넷에서 코딩 테스트 준비를 하는 데 뭐가 필요하고... 학원을 어디를 다녀야 하고... 프로그래머스 몇 레벨 풀어야 해요? 다 필요없고 그냥 자신에게 맞는 레벨 문제를 순서대로 다 푸시면 됩니다. 공부에는 왕도가 없듯이 코딩 테스트 문제들에도 왕도가 없습니다. 하지만 초보 분들은 자신에게 맞는 레벨 문제가 대체 무엇인지 잘 모를 것이라고 생각하기 때문에, 조금의 도움을 드리고자 이렇게 문제를 조금 뽑아 놓으려고 합니다.

잡소리

- 코딩 테스트를 쳐야 하는데 언어를 무엇을 쓸 지 고민하신다면, C++을 사용하라고 우선 권해드리고 싶습니다. 그 다음은 JAVA입니다. 파이썬이 코드가 짧고 편함에도 불구하고 추천드리지 않는 이유는, 파이썬을 쓰다 보면 많은 초보분들이 시간복잡도를 계산하는 데 무감각해지시기 때문입니다. 학교에서 푸는 짧은 예제들로는 거대한 테스트 케이스에서 사용해도 되는 함수들과 그렇지 않은 함수들을 구분하기 힘듭니다.

- 코드를 가능한 짧게 유지하려고 노력하세요. 코딩 테스트는 개발이 아닙니다. 변수명, 함수, 인덴팅, 괄호, 최대한 짧고 간결하게 하는 것이 나중에 코드를 볼 때도 편합니다. 한 줄 짜리 if, for 최대한 괄호 생략하세요. 중괄호가 대여섯번씩 중첩되지 않도록 하세요. 쓸데없는 빈 줄 두세개씩 넣지 마세요. 학교에서 스택 배웠다고 직접 스택 짜지 마세요. 동적 할당은 코딩 테스트에서 할 필요가 없습니다(뭐 B/C형이면 모르겠는데, 그 정도 준비하시는 분들이면 이 글 볼 이유가 없겠죠)
저는 코테 문제 푸는 코드 중에서 700줄이 넘는 코드를 본 적이 있습니다. 당연히 틀려도 어디가 틀렸는지 알 수 없고, 맞더라도 시간을 무지막지하게 많이 소모할 겁니다. 정상적으로 코딩했을 때 아무리 복잡한 문제라도 200줄을 넘어가기 쉽지 않습니다. 쉬운 문제의 경우 100줄을 넘어가기도 쉽지 않습니다. 짧게 짜세요.

- 시간복잡도를 계산 못하시겠다고요? 간단한 방법이 있습니다. 반복문이 중첩되는 경우, 반복문의 수행 횟수를 모두 곱하세요. 반복문이 따로따로 존재하는 경우, 수행 횟수를 더하세요. 함수를 수행하는 경우 그 함수의 시간복잡도를 마찬가지로 계산하세요. BFS/DFS를 수행하는 경우 총 시간복잡도는 일반적으로 정점 개수+간선 개수입니다. DP를 수행하는 경우 총 시간복잡도는 일반적으로 상태 공간(메모이제이션 하기 위해 잡는 배열 크기)에 한 dp 함수에서 호출하는 dp 함수의 횟수입니다. 내장 정렬과 힙, set, map 등의 모든 구조는 일반적으로 nlgn에 동작합니다.
시간복잡도를 문자에 대해서 계산하고, 각 문자에 대한 최고차항만 남겼을 때 그 문자에 제한의 최댓값을 넣어봅시다. 일반적으로 1억 이내의 값이 나온다면 1초 내에 충분히 돌아간다고 판단합니다.

- 항상 그렇듯이, 키보드에 손을 올리는 시점은 모든 준비가 끝난 이후입니다. (1) 문제를 어떻게 풀 지 확실하게 정하고; 이는 시간복잡도 계산 등을 포함합니다, (2) 해결 방법을 손으로 예제에 대해서 해 봤을 때 정상적으로 동작하는 지 확인하고, (3) 그 해결 방안을 어떻게 함수로 분할해서 구현할 지 정합니다. 물론 코드포스 같이 짧은 시간에 문제를 많이 풀어야 한다면 이 과정이 어느 정도 생략되겠지만, 여러분은 경진대회에 출전하는 게 아닙니다.

- 어? 왜 생각한대로 예제가 안 나오지? 하면 여러분은 코드를 훑어서 오타가 없는지 확인한 후 즉시 디버거나 printf문을 사용할 준비를 해야 합니다. 예제에서 계산하게 되는 핵심적인 값들을 미리 적어둔 후, 실제로 프로그램이 그 값을 똑같이 구하는지를 확인하고 어디에서 삑사리가 나는지를 확인하셔야 합니다.

- 함수를 어떻게 쓰는지 가물가물할 때는 쓰지 마세요. 틀리면 함수를 잘못 쓴 건지 로직이 틀린 건지 구분 절대 못합니다.

BOJ 길라잡이

<Set 0>

APPENDIX. 별 찍기

정말 생초보 분들은 건너뛰시고 뒤에서부터 푸시는 것을 권장합니다.
생각보다 짜증납니다. 이거 초보용 아님? 하지 말고 한 번 풀어 보세요.
요구 지식: 재귀함수에 관한 이해

• 2442번 별 찍기 - 5 | https://www.acmicpc.net/problem/2442
• 2445번 별 찍기 - 8 | https://www.acmicpc.net/problem/2445
• 10994번 별 찍기 - 19 | https://www.acmicpc.net/problem/10994
• 2448번 별 찍기 - 11 | https://www.acmicpc.net/problem/2448
• 10993번 별 찍기 - 18 | https://www.acmicpc.net/problem/10993

<Set 1>

A. 기초 구현 (1)

정말 초보적인 문제들을 모았습니다. 빠르게 풀고 다음으로 넘어갑시다.
요구 지식 : 언어에 대한 기초적인 이해, O(n^2) 정렬, 매우 간단한 수학

• 5522번 카드 게임 | https://www.acmicpc.net/problem/5522
• 1392번 노래 악보 | https://www.acmicpc.net/problem/1392
• 2469번 사다리 타기 | https://www.acmicpc.net/problem/2469
• 18110번 solved.ac | https://www.acmicpc.net/problem/18110
• 1049번 기타줄 | https://www.acmicpc.net/problem/1049

B. 정렬과 이분 탐색 (1)

수를 정렬하고, 이를 통해 빠르게 탐색하는 방법입니다.
요구 지식 : O(nlgn) 정렬, 이분 탐색

• 1920번 수 찾기 | https://www.acmicpc.net/problem/1920
• 2750번 수 정렬하기 | https://www.acmicpc.net/problem/2750
• 2751번 수 정렬하기 2 | https://www.acmicpc.net/problem/2751
• 10989번 수 정렬하기 3 | https://www.acmicpc.net/problem/10989
• 10815번 숫자 카드 | https://www.acmicpc.net/problem/10815

C. 기초 수학 (1)

중학교 수준 내에서 요구되는 수학 문제들을 해결하며 사고력을 길러봅시다.
요구 지식 : 중학교 수준의 수학 실력

• 11966번 2의 제곱인가? | https://www.acmicpc.net/problem/11966
• 17466번 N! mod P (1) | https://www.acmicpc.net/problem/17466
• 9506번 약수들의 합 | https://www.acmicpc.net/problem/9506
• 2417번 정수 제곱근 | https://www.acmicpc.net/problem/2417
• 2609번 최대공약수와 최소공배수 | https://www.acmicpc.net/problem/2609
• [ADD1] 17356번 욱 제 | https://www.acmicpc.net/problem/17356

ADD1) 실제 코딩 테스트에서 실수의 제곱 연산은 거의 등장하지 않습니다. 만약 정수를 제곱해야 한다면, 반드시 pow 함수가 아닌 반복문을 사용해서 계산하시는 것을 권장합니다. 실수 연산을 가능한 사용하지 마세요. 초보자가 실수할 구석이 너무나도 많습니다.

<Set 2>

A. 브루트 포스 (1)

다 해보면 되죠!
요구 지식 : 백트래킹(전탐색)

• 18111번 마인크래프트 | https://www.acmicpc.net/problem/18111
• 17521번 Byte Coin | https://www.acmicpc.net/problem/17521
• 14889번 스타트와 링크 | https://www.acmicpc.net/problem/14889
• 1057번 토너먼트 | https://www.acmicpc.net/problem/1057
• 10819번 차이를 최대로 | https://www.acmicpc.net/problem/10819

cf) Byte Coin을 비롯한 몇 문제들은 의도된 더 빠른 별해가 있습니다. 쉽고 직관적이에요!

B. 기초 자료구조 (1)

선형 자료구조의 기초를 훑어보는 문제들입니다. 다 까먹은 교과서를 복습할 시간이 왔습니다.
요구 지식: 스택, 큐, 덱, 리스트

• 10828번 스택 | https://www.acmicpc.net/problem/10828
• 10845번 큐 | https://www.acmicpc.net/problem/10845
• 10866번 덱 | https://www.acmicpc.net/problem/10866
• 1406번 에디터 | https://www.acmicpc.net/problem/1406

C. 기초 구현 (2)

항상 말하지만, 문제를 못 푸는 이유는 절반이 풀이를 몰라서고 절반이 주는 풀이도 제대로 못 받아먹어서입니다. 구현력을 올릴 수 있도록 노력합시다.

• 4539번 반올림 | https://www.acmicpc.net/problem/4539
• 9547번 대통령 선거 | https://www.acmicpc.net/problem/9547
• 1640번 동전 뒤집기 | https://www.acmicpc.net/problem/1640
• 14891번 톱니바퀴 | https://www.acmicpc.net/problem/14891
• 15671번 오델로 | https://www.acmicpc.net/problem/15671

<Set 3>

A. 그리디 알고리즘 (1)

그리디한 접근은 모든 문제에서 가장 기본이 되는 접근입니다. 이 단원에서는 그 중에서도 그리디한 접근이 핵심이 되어 해결할 수 있는 문제들을 모았습니다. 그리디가 특별한 알고리즘이라고 생각하지 마세요! 구현과 동급입니다.
요구 지식: 없음!!!

• 11256번 사탕 | https://www.acmicpc.net/problem/11256
• 2138번 전구와 스위치 | https://www.acmicpc.net/problem/2138
• 13305번 주유소 | https://www.acmicpc.net/problem/13305
• 14247번 나무 자르기 | https://www.acmicpc.net/problem/14247
• 11508번 2+1 세일 | https://www.acmicpc.net/problem/11508

B. 브루트 포스 (2)

백트래킹과 같이 놀아봅시다.

• 6603번 로또 | https://www.acmicpc.net/problem/6603
• 1182번 부분집합의 합 | https://www.acmicpc.net/problem/1182
• 9095번 1, 2, 3 더하기 | https://www.acmicpc.net/problem/9095
• 9663번 N-queen | https://www.acmicpc.net/problem/9663

C. 기초 수학 (2)

알고리즘 잘하면서 수학 못하는 사람은 본 적 없지만, 수학 잘하면서 알고리즘 못 하는 사람은 본 적이 없습니다.

• 1978번 소수 찾기 | https://www.acmicpc.net/problem/1978
• 1929번 소수 구하기 | https://www.acmicpc.net/problem/1929
• 2485번 가로수 | https://www.acmicpc.net/problem/2458
• 1644번 소수의 연속합 | https://www.acmicpc.net/problem/1644
• 1016번 제곱 ㄴㄴ 수 | https://www.acmicpc.net/problem/1016

<Set 4>

A. DFS와 BFS

가장 기초적인 그래프 알고리즘의 시작입니다. DFS와 BFS는 다양한 탐색 알고리즘의 기초이자 수많은 문제들을 모델링해서 풀어나갈 수 있는 대표적인 기법으로서, 눈 감고 코딩해서 3분 안에 정답을 낼 수 있어야 하는 알고리즘입니다. 구라같다고요? 진짠데요;
요구 지식: DFS와 BFS

• 1260번 DFS와 BFS | https://www.acmicpc.net/problem/1260
• 2667번 단지번호붙이기 | https://www.acmicpc.net/problem/2667
• 1697번 숨바꼭질 | https://www.acmicpc.net/problem/1697
• 2178 미로 탐색 | https://www.acmicpc.net/problem/2178

B. 동적 계획법 (1)

동적 계획법이 어렵다고 말하시는 분들이 많습니다. 점화식을 어떻게 세워야 될지 모르겠다고 하시는 분들이 있습니다. 고치는 방법은 하나입니다. DP 200문제를 풀면 저절로 고쳐지실 겁니다. 여기서는 200문제 DP의 시발점을 제시해 드립니다.
요구 지식: 동적 계획법(다이나믹 프로그래밍, DP)

• 1003번 피보나치 함수 | https://www.acmicpc.net/problem/1003
• 1463번 1로 만들기 | https://www.acmicpc.net/problem/1463
• 2579번 계단 오르기 | https://www.acmicpc.net/problem/2579
• 1932번 정수 삼각형 | https://www.acmicpc.net/problem/1932

C. 구현 (1)

우리 문제 많이 풀었잖아요? 이제 시간을 많이 두고 복잡한 구현을 해봅시다. 복잡할 수 있습니다. 제일 중요한 것은, 한 문제를 풀더라도 이 문제를 작은 여러 문제로 분할하는 겁니다. 모든 부분 문제에 대한 코딩을 종이와 펜으로 미리 해두고 그것을 그대로 베끼듯이 컴퓨터에 코드로 옮기세요. 시간복잡도, 당연히 먼저 계산해둬야 합니다. 한번 꼬이는 순간, 망하는 겁니다. 모두 지우고 처음부터 다시 코딩하세요.
갑자기 난이도가 오른 것 알고 있습니다! 보스전이라고 생각하세요. 화이팅!

cf) 제가 자주 쓰는 기법인데, 듣기로는 윤지학 메소드라고 부른다고 합니다. 코딩이 막혔을 때 애용합니다.
Ctrl-A, Delete, Ctrl-S, Alt-F4를 차례대로 빠르게 누르시면 됩니다.

• 7682번 틱택토 | https://www.acmicpc.net/problem/7682
• 15684번 사다리 조작 | https://www.acmicpc.net/problem/15684
• 15868번 치킨 배달 | https://www.acmicpc.net/problem/15868
• 16235번 나무 재테크 | https://www.acmicpc.net/problem/16235
• 16236번 아기 상어 | https://www.acmicpc.net/problem/16236