4. 이코테 구현 알고리즘

아이디어를 코드로 바꾸는 구현

코딩 테스트에서 구현(implementation)이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다.

그런 의미에서 알고리즘 교재에서는 구현을 별도의 유형으로 다루지 않지만 코테에서는 구현이 중심이 되는 문제가 자주 출제되기에 먼저 다루고자 한다.

우리는 알고리즘 문제를 해결할 때, 문제를 읽고 풀이방법을 고민한다. 우리는 정확한 방법이 떠오르면 바로 정답 처리를 받을 수 있을까?? 그렇지 않다. 생각해낸 문제를 파이썬으로 정확히 구현했을 때 비로소 정답처리를 받는다.

구현 유형의 문제는 문법이 능숙하고 코드 작성 속도가 빠른 사람인 피지컬이 좋은 사람이 유리하다. 참고로 나는 뇌지컬보단 리얼 피지컬이 더 나은 것 같다. 개발자 실패하면 트레이너라도 해야지...

예를 들어 파이썬으로 코테에 응시했는데, N개의 원소가 들어있는 리스트에서 R개의 원소를 뽑아 한 줄로 세우는 모든 경우를 구해야 하는 문제를 만나면 어떻게 할까? 무작정 짜는 것도 되지만, itertools와 같은 표준 라이브러리로 쉽게 짜는 방법도 있다. 이는 언어의 문법을 잘이해하고 경험이 있어야만 생각해낼 수 있다.

이코테에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다. 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다. 둘 다 구현이 핵심이 경우가 많기 때문에 이 두 유형을 모두 묶어서 구현 장에서 다루고 있다.

파이썬은 정수형 변수의 연산 때문에 머리 아프게 고민해야 할 일은 거의 없다.
하지만 c++이나 java에서는 고민해야한다 -추후에 고민해보자

파이썬의 리스트 크기)
리스트의 크기 제약에 대해서 알아보자. 대체로 코테에서는 128~512MB로 메모리를 제한하는데 알고리즘 문제 중 때때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다. 이럴 때는 메모리 제한을 염두에 두고 코딩해야한다.

int 자료형 데이터의 개수에 따른 메모리 사용량)
1,000개 - 약 4KB
1,000,000 - 약 4MB
10,000,00 - 약 40MB

파이썬은 구현상 다른 언어에 비해 복잡함이 적은 편이지만 데이터 처리량이 많을 때는 메모리 제한을 고려해야한다. 리스트를 여러 개 선언하고, 그 중에서 크기가 1000만 이상인 리스트가 있다면 메모리 제한으로 풀 수 없게 되는 경우도 존재한다.하지만 이러한 문제는 출제자들도 출제하기 번거롭기 때문에 잘 나오지 않는다.

채점환경)
기관마다 다르다. 출제자가 매우 빠르게 동작하는 프로그램을 원한다면 시간 제한은 더욱 짧을 것이다. 보통 코테는 시간, 메모리 제한을 제시해준다.

파이썬은 다른 언어에 비해 동작 속도가 느리다. 자신의 코드가 1초에 2000만 번의 연산을 수행한다고 가정하고 문제를 풀면 안정적이다. 일반적인 코테에서는 크게 무리가 없다.

시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(N log N)이 내의 알고리즘을 이용해야한다. 데이터 개수가 100만개라면 위의 시간복잡도로는 2천만이기 때문이다. 따라서 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

구현문제에 접근하는 방법)
파이썬으로 구현난이도는 다소 쉬운 편이지만 프로그램 실행 시간은 긴 편이다.
자동 채점 방식을 이용하는 코테 환경에서는 pypy3을 지원하는 곳이 많다. pypy3은 파이썬3의 문법을 그대로 지원하고 c++의 속도와 별차이가 없다. 그러므로 pypy3을 지원한다면 이용하도록 하자.

API 개발 문제 또한 구현 유형과 상당히 맞닿아 있다. 파이썬은 다른 언어에 비해 매우 간결하고 직관적인 코드의 라이브러리를 사용할 수 있어 더 유리하다.

예제 4-1 상하좌우 p.110

comment) 오늘은 컨디션 난조여서 머리가 돌아가지 않아 책을 보면서 했다. 피곤에 쌓여 아이디어가 생각이 나질 않는다. 뒷 예제 중 똑같은 유형의 예제문제가 있었다. 한번더 풀어보고 그 문제에 집중해야겠다.

기억해야 할 것은 continue와 문제에 대한 접근 방법이다. continue는 조건 성립시 아래 코드를 읽지 않고 for문으로 돌아간다. while문도 동일하다.

예제 4-2 시각 p.113

comment) 초코과자도 피곤은 못이긴다. 이 문제의 경우의 수는 86400가지 밖에 존재하지 않는다. 10만개 이하이므로, 3중 반복문을 사용한다고 해도 2초 이하이다.

여기서 기억해야할 것은 in 이다. in string 해도 string 안에 문자열이 있는지 확인할 수 있다.

실전 문제- 왕실의 나이트 p. 115

comment) 이 문제는 4-1의 풀이 방법을 응용하여 풀었던 것 같다. 여기서 책을 참고하고 썼던 것은 바로 ord 이다. ord()는 문자를 입력받고 유니코드 정수를 출력하는 함수이고, chr()은 정수를 입력받고 유니코드 문자를 출력하는 내장 함수이다. 다른 부분은 책에서 구현 부분을 설명하듯이 오류없이 코드를 실행할 수 있도록 코드를 작성하는 것이 중요한 것 같다.

이번 예제를 통해서 한번 더 복습할 수 있었던 것은 continue, in, ord(), chr()이다. 간단한 문법이지만 애매하게 알고있는 것 같다. 특히나 문자열이나 in 같은 경우는 한번 더 파이썬 기본서로 복습해야할 것 같다.

실전 문제 - 게임 개발 p.118

나의 코드)

comment) 앞의 문제들을 복습한 후에 게임 개발문제에 들어갔다. 결국엔 난 40분 내에 문제를 풀 수 없었다.... 이런 시뮬레이션 문제들은 계속 풀어보는 연습이 필요한 것 같다

책의 코드)

n, m = map(int,input().split())

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

x,y,direction = map(int, input().split())

array = []
for  i in range(n):
  array.append(list(map(int,input().split())))


dx = [-1,0,1,0]
dy = [0,1,0,-1]

def turn_left():
  global direction 
  direction -=1
  if direction == -1:
    direction = 3

count = 1
turn_time = 0

while True:

  turn_left()
  nx = x + dx[direction]
  ny = y + dy[direction]

  if d[nx][ny] == 0 and array[nx][ny]:
    d[nx][ny] = 1:
    x = nx
    y = ny
    count +=1
    turn_time = 0
    countinue

  else:
    turn_time += 1

  if turn_time == 4:
    nx = x-dx[direction]
    ny = y-dy[direction]

    if array[nx][ny] == 0:
      x = nx
      y = ny

    else :
      break

    turn_time = 0

print(count)

comment) 약간 비슷한 생각을 했던 것 같다.
1. 이중 리스트로 맵을 저장한 점
2. 왼쪽으로 회전하기위한 방향을 리스트로 저장한 점
3. 4번 회전하여 실패시 뒤로 가는 것을 만들기 위해 fail을 지정한 것
=>(turn_time)

turn_left() 함수를 만든 것이 신의 한 수 같았다. 나는 함수 없이 main에서만 끝내려니 코드가 복잡해지다가 실패한 것 같다. 이러한 센스를 연습을 해야할 것같다. 그리고 알고리즘 계획을 짜는 것을 연습해야 할 것 같다.

이로써 구현파트가 끝났다. 복습만이 살 길이다.

복습 1번
복습 2번

시뮬레이션은 다른 문제도 계속 풀어 봐야할 것 같다 ㅋㅋㅋㅋ 그래도 이젠 여기 있는 문제는 마스터 한 것 같다