[코딩테스트] 구현 알고리즘

구현 알고리즘

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

 

풀이를 떠올리기 쉽지만 소스코드로 옮기기 어려운 문제

코드가 길어지는 문제, 특정 소수점까지 출력하는 문제, 파싱 문제 등

완전 탐색, 시뮬레이션 등을 포함

 

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

시뮬레이션 : 문제에서 제시한 알고리즘을 하나씩 차례대로 직접 수행

 

 

예제) 상하좌우

NxN 크기의 정사각형 공간에서 (1,1)에서 시작하여 L, R, U, D를 통해 이동할 때 최종 목적지의 좌표 구하기

정사각형 공간을 벗어나면 무시

-> 명령에 따라서 개체를 이동시키기 때문에 시뮬레이션 문제로 분류

 

방향을 설정하여 이동하는 문제 -> x의 이동 방향, y의 이동 방향, 이동 타입 등을 명시하는 리스트를 각각 생성 

이동방향을 명시하는 dx, dy는 리스트 내 튜플 방식으로도 작성 가능함

# L R U D의 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']


# 리스트 내 튜플 방식
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (-1, 2), (-2, 1), (1, 2), (2, 1)]

 

 

예제) 이동 거리 계산

출발 위치에서 상하좌우로 이동 가능한 칸의 개수를 출력

시뮬레이션 문제 : 문제에서 제시하는 방법을 정확히 구현하기만 하면 됨

 

이동 가능한 칸의 개수를 구하는 것이기 때문에,

이동한 위치를 저장하는 리스트와, 맵 정보를 저장하는 리스트를 별도로 만들어야 함

 

왼쪽으로 회전 후 회전 방향에 길이 있으면 앞으로 전진하면서 회전 횟수 초기화, 없으면 왼쪽으로 회전

회전 횟수가 4회(상하좌우)가 되면 뒤로 한칸 물러나서 반복

뒤로 물러날 길이 없는 경우 모든 길이 막혔다는 뜻이므로 종료

 

 

 

 

※ 해당 포스트는 이것이 "코딩 테스트다 with 파이썬(나동빈 저)"를 통해 학습한 내용을 정리한 것입니다.