구현 (Implementation) 알고리즘
특징
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 → 소위 피지컬이라고도 한다.
사소한 조건 설정이 많은 문제일수록 코드로 구현하기 까다롭다.
이 책에서는 완전 탐색, 시뮬레이션 유형을 구현 유형으로 묶어 다룬다.
- 완전 탐색 - 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
- 시뮬레이션 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수
파이썬에서는 별도의 자료형을 선언하지는 않지만 리스트에 정수가 들어간다고 가정했을 때 위와 같은 메모리 사용량을 가진다.
하지만 일반적으로 크기가 1000만 이상인 리스트를 요구하는 문제는 드물다.
파이썬 → 1초에 2000만 번의 연산 을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다.
Pypy3 는 파이썬과 동일한 문법을 사용하지만 파이썬보다 실행시간이 빠르기 때문에 코딩 테스트 환경에서 Pypy3를 지원하면 이를 활용해보자.
👿 예제 - 상하좌우 (하)
- 아이디어 1,1 에서 시작해서 오른쪽은 (0, +1) 하고 왼쪽은 (0, -1) 하고 위는 (-1, 0) 하고 아래는 (+1, 0) 한다. 이 때 만약 상화좌우를 한 값이 지도를 나가지 않도록 1,1 또는 N, N 의 범위를 넘어가는지 체크한다. 만약 나갔다면 continue 한다.
- 나의 풀이
def travel(N, plans): x, y = 1, 1 dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] move_types = ['L', 'R', 'U', 'D'] for move in plans: for i in range(len(move_types)): if move == move_types[i]: nx = x + dx[i] ny = y + dy[i] if nx < 1 or ny < 1 or nx > N or ny > N: continue x, y = nx, ny print(x, y) def main(): N = int(input()) plans = input().split() travel(N, plans) if __name__ == "__main__": main()
👿 예제 - 시각 (하)
- 아이디어 24시간은 결국 0 ~ 23 0 ~ 59 0 ~ 59, 즉 최대 246060의 경우의 수를 가지기 때문에 그냥 완전 탐색을 사용한다.
- 나의 풀이
def solution(N): ans = 0 for hour in range(N+1): for minute in range(60): for second in range(60): time = str(hour) + ':' + str(minute) + ':' + str(second) if '3' in time: ans += 1 print(ans) def main(): N = int(input()) solution(N) if __name__ == "__main__": main()
👿 실전 문제 - 왕실의 나이트 (하)
- 아이디어 예제의 상하좌우 문제와 유사한 것 같다. 0,0 을 시작으로 해서 총 움직일 수 있는 경우의 수는 8가지 이다. 모든 경우의 수를 움직여보고 안되면 패스, 가능하면 cnt + 1 해줘서 cnt 를 리턴해보자.
- 나의 풀이
def solution(N): x, y = ord(N[0]) - 96, int(N[1]) # x 좌표는 a,b,c... y 좌표는 1,2,3.. dx = [2, 2, -2, -2, -1, 1, -1, 1] dy = [-1, 1, -1, -1, 2, 2, -2, -2] move_types = [ 'RU', 'RD', 'LU', 'LD','DL', 'DR', 'UL', 'UR'] ans = 0 for i in range(len(move_types)): nx = x + dx[i] ny = y + dy[i] if nx < 1 or ny < 1 or nx > 8 or ny > 8: continue ans += 1 def main(): N = input() solution(N) if __name__ == "__main__": main()
👿 실전 문제 - 게임 개발 (중)
- 아이디어 기존의 지도 문제에서 바라보는 방향이 추가된 문제이다. 현재 방향을 기준으로 왼쪽을 바라보도록 만들고 왼쪽 방향에 가보지 않은 칸이 있으면 전진, 없으면 다시 90도 돌려서 해당 칸 확인 … 을 진행하고 4칸 모두 확인한 결과 모두 가본 칸이거나 바다라면 바라보는 방향을 유지하고 뒤로 한칸 간다. 이 때 뒤가 바다라면 움직임을 멈추게 한다. 그냥 조건 그대로 구현하면 될 것 같다..?
- 나의 풀이
처음에는 회전하는 횟수를 어떻게 카운트 해야 할지 헷갈렸다. 4번 다 돌았을 때의 경우를 처리하는게 가장 까다로웠던 것 같다. 결국 turn_cnt 변수를 선언해 회전을 성공했을 때 +1 을 해주도록 해서 4번이 되었다면 그 방향에서 뒤로 한 칸 이동 후 그 칸이 육지인지만 확인해서 이동할지를 결정하게 해주었다.def solution(sx, sy, direction, gameMap, visited): x, y = sx, sy steps = [(-1, 0), (0, -1), (1, 0), (0, 1)] ans = 0 turn_cnt = 0 while True: # 반시계 방향 90도 회전 direction -= 1 direction %= 4 step = steps[direction] nx = x + step[0] ny = y + step[1] # 바라보는 방향이 안가봤고 육지라면 이동 if visited[nx][ny] == 0 and gameMap[nx][ny] == 0: visited[nx][ny] = 1 x, y = nx, ny ans += 1 turn_cnt = 0 continue else: turn_cnt += 1 # 4방향 다 못간다면 일단 nx, ny를 뒤로 이동 if turn_cnt== 4: nx = x - step[0] ny = y - step[1] # 육지여서 뒤로 갈 수 있으면 이동 확정 if gameMap[nx][ny] == 0: x = nx y = ny else: break turn_cnt = 0 print(ans) def main(): N, M = map(int, input().split()) sx, sy, direction = map(int, input().split()) gameMap, visited = [], [] for _ in range(M): arr = list(map(int, input().split())) gameMap.append(arr) visited = [[0] * M for _ in range(N)] solution(sx, sy, direction, gameMap, visited) if __name__ == "__main__": main()
회고
머리가 굳어서 어렵지 않은 알고리즘 문제도 헤매면서 풀고 있다…… 최대한 해설을 안보려고 하지만 알고리즘이 머리에 떠올라도 풀이 방법 자체가 뭔가 구현이 잘 되지 않아 해설을 조금씩 참고했는데 다 옛날에 직접 해봤던 방법들이었다. 확실히 알고리즘은 꾸준히 하지 않으면 머리에 남아있던 풀이 방식이 휘발되어 버린다.
