[Python] 코딩테스트 '구현' 문제에 접근하는 방법

이코테 책에서 풀다가 복습할 내용들만 정리해본다.

자세한 문제는 '이것이 코딩테스트다 with 파이썬 (나동빈)' 책에서 확인하기

 

구현 문제란 특별한 알고리즘 기법은 필요 없는 정확한 풀이가 핵심이 되는 문제를 말한다.

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미하며 나는 이런 부분에 많이 취약한 것 같다.

- 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제

- 특정 소수점 자리까지 출력해야 하는 문제

- 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제

- 2차원 배열에서의 이동, 회전 등 까다로운 문제

 

특히 완전탐색과 시뮬레이션 유형은 모두 구현 유형으로 볼 수 있다.

완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 

시뮬레이션은 문제에서 제시한 알고리즘들을 한 단계씩 차례대로 직접 수행해야 하는 문제(삼성 공채 빈출 유형)이다.

 

1️⃣ python에서 리스트 크기

대체로 코딩테스트에서는 128 ~ 512MB로 메모리를 제한한다. 리스트의 길이가 1000일때 메모리 사용량은 약 4KB, 100만 일 때 약 4MB, 1000만 일 때 약 40MB가 차지한다. 특히 리스트를 여러 개 선언하고 그중에서 크기가 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다. 일반적인 코테 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야 한다는 것 정도만 기억하자.

 

2️⃣ 기타 구현 관련 꿀팁들

• 탐색해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.
• 좌표평면에서 '상하좌우'로 이동해야 하는 경우 dx, dy 리스트를 선언해 이동할 방향을 기록한다. 
  이 외에 '상하좌우+대각선4방향'으로 이동한다면 steps = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)] 로 표현하는 것이 좋다. 
• 2차원 리스트를 선언할 때는 리스트 컴프리헨션 문법을 사용하는 것이 효율적이다.
  

  d = [[0] * m for _ in range(n)]

   

3️⃣ 헷갈리는 문제들 기록

이코테 4-4. 게임개발 (시뮬레이션)

이코테 Q09. 문자열 압축 (2020 카카오 신입공채, 완전탐색)

이코테 Q10. 자물쇠와 열쇠 (2020 카카오 신입공채, 완전탐색)

이코테 Q12. 기둥과 보 설치 (2020 카카오 신입공채, 시뮬레이션)

 

(계속 추가해나갈 예정)