구현
-
코딩 테스트에서 구현(Implementation)이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제들 풀든 소스코드를 작성하는 과정은 필수이므로 구현 문제는 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.
-
여기서는 완전탐색, 시뮬레이션 유형을 모두 ‘구현’ 유형으로 묶어서 다룬다. 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 의미한다.
-
완전탐색 문제는 모든 경우의 수를 다 계산해야 하기 때문에 반복문 혹은 재귀 함수를 적절히 사용하며 예외 케이스를 모두 확인해야 하는 경우가 많다. 그러므로 일반적으로 DFS/BFS 알고리즘을 이용해서 문제를 해결한다.
메모리 제약 사항(리스트 크기)
주로 코테에서는 128 ~ 512MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다. 이럴 때는 메모리 제한을 염두에 두고 코딩해야 한다. 리스트를 여러 개 선언하고, 그중에서 크기가 1,000만 이상인 리스트가 있다면 메모리 제한을 초과할 수도 있다는 점을 기억하자.
데이터의 개수(리스트의 길이)|메모리 사용량
1,000|약 4KB
1,000,000|약 4MB
10,000,000|약 40MB
## 이코테 유형별 기출문제
- Q7. [럭키 스트레이트](https://www.acmicpc.net/problem/18406)
- Q8. 문자열 재정렬
- Q9. [문자열 압축](https://programmers.co.kr/learn/courses/30/lessons/60057) - [풀이](https://summerlunaa.github.io/notes/2021/06/25/Notes-Q9-%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%95%95%EC%B6%95.html)
- Q10. [자물쇠와 열쇠](https://programmers.co.kr/learn/courses/30/lessons/60059) - [풀이](https://summerlunaa.github.io/notes/2021/06/25/Notes-Q10-%EC%9E%90%EB%AC%BC%EC%87%A0%EC%99%80-%EC%97%B4%EC%87%A0.html)
- Q11. [뱀](https://www.acmicpc.net/problem/3190)
- Q12. [기둥과 보 설치](https://programmers.co.kr/learn/courses/30/lessons/60061) - [풀이](https://summerlunaa.github.io/notes/2021/06/25/Notes-Q12-%EA%B8%B0%EB%91%A5%EA%B3%BC-%EB%B3%B4-%EC%84%A4%EC%B9%98.html)
- Q13. [치킨 배달](https://www.acmicpc.net/problem/15686)
- Q14. [외벽점검](https://programmers.co.kr/learn/courses/30/lessons/60062)
## 백준
[백준에서 푼 구현 문제](https://www.acmicpc.net/problemset?sort=solvedac_desc&submit=ac&algo=102&algo_if=and)
[백준에서 푼 완전탐색 문제](https://www.acmicpc.net/problemset?sort=solvedac_desc&submit=ac&algo=125&algo_if=and)
[백준에서 푼 시뮬레이션 문제](https://www.acmicpc.net/problemset?sort=solvedac_desc&submit=ac&algo=141&algo_if=and)