책의 2부에서 처음으로 등장하는 구현에 대해 공부하는 시간이다.
1. 구현
- 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
- 특징
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 특정 소수점 자리까지 출력해야하는 문제
- 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야하는) 문제
- 라이브러리 사용 경험이 많다면 유리(ex. 순열 문제의 경우 itertools로 쉽게 짜기 가능)
- 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형
- 메모리 제약 사항 고려하기!(with Python)
- 대체로 코딩 테스트에서는 128 ~ 512 MB로 메모리 제한 BUT 때로는 수백만 개 이상의 데이터 처리하는 문제 출제됨
- int 자료형 데이터 개수에 따른 메모리 사용량
| 데이터의 개수(리스트의 길이) |
메모리 사용량 |
| 1,000 |
약 4KB |
| 1,000,000 |
약 4MB |
| 10,000,000 |
약 40MB |
- 시간 제한 1초/ 데이터 개수 100만개 => 시간 복잡도O(NlogN)이내의 알고리즘을 이용해 문제를 풀어야함.
- 문제 파악법
- 사소한 입력 조건 등을 문제에 명시해주어 문제의 길이가 꽤 긴 편
- 출력 기준이 까다로운 문제인가?
2. 구현 유형의 알고리즘 문제
- 예제 4-1 상하좌우
- 실전문제 왕실의 나이트
- 실전문제 게임개발
- Q 07 럭키 스트레이트
- Q 08 문자열 재정렬
- Q 09 문자열 압축
- Q 10 자물쇠와 열쇠
- Q 11 뱀
- Q 12 기둥과 보 설치
- Q 13 치킨 배달
- Q 14 외벽 점검
