2022.04.29 - [이코테] 구현

구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 말한다.

 

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점 자리까지 출력해야하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야 하는 문제
• 2차원 배열에서의 이동, 회전 등 까다로운 문제

이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다.

 

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

시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형

 

1️⃣  Python에서 리스트의 크기

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

 

2️⃣  채점 환경

문제에서 요구하는 메모리 제한과 실행 시간은 코딩 테스트를 출제하는 기관마다, 문제마다 조금씩 다르다.

일반적인 코딩 테스트 환경에는 다음과 같은 채점 시스템의 시간 제한 및 메모리 제한 정보가 적혀있다.

 - 시간 제한 : 1초

 - 메모리 제한 : 128MB

 

파이썬은 C/C++에 비해 동작 속도가 느리므로, 파이썬을 선택했을 때 C/C++에 비해 2배의 수행 시간 제한을 적용하기도 함.

2020년 기준 파이썬 3.7로 코드를 작성할 때, 코드가 1초에 2000만 번 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다.

 

시간 제한이 1초이고, 데이터 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어햐 한다.

 - N = 1,000,000일 때 NlogN은 약 20,000,000이기 때문이다.

 - 즉, 알고리즘 문제를 풀 때 시간 제한과 데이터 개수를 먼저 확인한 뒤 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

 

3️⃣  구현 관련 꿀팁

 

1) 탐색해야 할 전체 데이터 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절

2) 좌표평면에서 '상하좌우'로 이동해야 하는 경우 dx, dy 리스트를 선언해 이동할 방향을 기록한다

    이 외에 '상하좌우+대각선 4방향'으로 이동한다면 steps = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2)]로 표현

 

출처 : 

이것이 코딩 테스트다 with 파이썬 (나동빈 지음)

https://blackon29.tistory.com/62

https://scshim.tistory.com/431