썸네일 출처: The Sims

구현

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

어떻게 풀 지를 생각하는 것까지는 쉬운데, 코드로 옮기기 어려운 문제.
대체로, 사소한 입력 조건 등으로 인해 문제의 길이가 꽤 긴 편.

• 알고리즘은 간단한데, 코드가 지나치게 길어지는 문제
• 특정 소수점까지 출력해야 하는 문제
• 문자열이 입력으로 주어졌을 때, 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제

'이코테'에서는 모든 경우의 수를 전부 계산하는 완전탐색과 문제에서 제시하는 알고리즘을 한 단계씩 수행하는 시뮬레이션을 다루고 있다. 문제에서 요구하는 내용을 오류 없이 성실하게 구현만 할 수 있다면 풀 수 있기에, 문법을 정확하게 숙지하고 라이브러리 경험을 쌓는 것이 도움이 된다.

알아두면 좋은데 잘 몰랐던 문법

리스트

• 크기가 N인 1차원 리스트 초기화: [0] * n
• 크기가 N인 2차원 리스트 초기화: [[0] * m for i in range(n)]
• 리스트 관련 기타 메서드
  • 리스트.sort(): 기본 오름차순 정렬, reverse=True로 내림차순 설정
  • 리스트.insert(삽입할 위치 인덱스, 삽입할 값): 특정 인덱스 위치에 원소 삽입
  • 리스트.count(특정 값): 특정한 값을 갖는 데이터 개수
  • 리스트.remove(특정 값): 특정한 값을 갖는 원소 하나 제거
  • insert(), count(), remove()의 시간 복잡도: $O(N)$

튜플

• 한 번 선언하고 나면 원소의 값을 변경할 수 없음
• 우선순위 큐에 들어가는 데이터를 작성할 때, 흔히 (비용, 노드 번호), (가치, 상품)의 형태로 사용

사전(Dictionary) & 집합(Set)

• 리스트와 달리, 순서가 없기 때문에 인덱싱 불가능
• 검색 및 수정에 있어서 $O(1)$의 시간에 처리할 수 있고, 이는 리스트보다 훨씬 빠름
• 집합에 하나의 데이터를 추가할 때는 add(), 여러 개를 추가할 때는 update(), 제거할 때는 remove()를 이용하고, 시간 복잡도는 모두 $O(1)$.

함수

• 간단한 함수를 정의해야 할 때 사용할 수 있는 람다 표현식
  • lambda 매개변수: 반환 값 -> 하나의 함수
  • (lambda a, b: a + b)(3, 7)

입출력

• input(): 콘솔을 통해 한 줄의 문자열을 입력받아 반환
• map(반복하는 함수 객체, 반복 가능한 객체): 반복 가능한 객체의 각 원소마다 함수를 적용

주요 라이브러리

• heapq
  • 우선순위 큐 기능을 구현할 때 사용
  • 리스트로 구현하는 것보다 시간 복잡도 측면에서 매우 유리함
  • 최소 힙으로 구성되어 있으므로, 최상단 원소는 항상 가장 작은 원소 (튜플이라면 첫 번째 원소가 기준)
  • import heapq로 임포트
  • heapq.heappush(리스트, 데이터): 힙에 원소를 삽입
  • heapq.heappop(리스트, 데이터): 힙에서 원소를 꺼냄
• collections.deque
  • 인덱싱, 슬라이싱은 불가능하지만 시작 부분이나 끝부분에 데이터를 삽입하거나 삭제할 때 매우 효과적 -> 스택, 큐의 기능을 모두 포함
  • popleft(): 첫 번째 원소를 꺼냄
  • pop(): 마지막 원소를 꺼냄
  • appendleft(): 첫 번째 인덱스에 원소 삽입
  • append(): 마지막 인덱스에 원소 삽입

왕실의 나이트

• 8 $\times$ 8 좌표 평면 상에서 L자 형태로만 이동할 수 있는 나이트
• 행은 1부터 8로, 열은 a부터 h로 표현됨
• 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 찾는 문제

0. 나이트의 위치를 입력받을 때 문자열이 포함되므로 ord()를 사용해 숫자로 변경
   ('a' -> 97, 'b' -> 98, ...)
1. 나이트가 움직일 수 있는 방법에 따라 좌표 값이 변화하는 패턴을 변수로 선언
2. 주어진 위치에서 나이트가 움직인 후의 좌표를 하나씩 확인
3. 움직인 후의 좌표가 좌표 평면 안에 위치하는 경우만 카운팅

게임 개발

• $N\times M$ 크기의 직사각형 맵 안에서 움직이는 게임 캐릭터
• 맵의 각 칸은 (북쪽으로부터 떨어진 칸의 개수, 서쪽으로부터 떨어진 칸의 개수)
• 상하좌우로 움직일 수 있는 캐릭터는 육지로만 갈 수 있고, 바다로는 못 감

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 갈 지 말지 결정
   1-1. 그 칸을 아직 가보지 않았다면 한 칸 전진
   1-2. 가본 칸이거나 바다로 되어 있다면 왼쪽 방향으로 회전만 함
2. 네 방향 모두 이미 가봤거나 바다로 되어있으면, 바라보는 방향을 기준으로 한 칸 후진
   2-1. 이 때, 뒤로 갈 수 없으면 스탑

0. 문제가 일단 길다.
   0-1. 한 줄씩 맵의 정보가 입력되므로 맵에 해당하는 배열을 선언해야 함.
   0-2. 가본 적 있는지에 따라 갈지 말지가 결정되므로 맵 크기랑 동일하게 방문 여부를 저장할 배열이 필요.
   0-3. 방향에 따라 이동했을 때 좌표 변화 dx, dy 선언
1. 캐릭터의 처음 위치를 입력 받고, 그 칸을 방문 처리
2. 왼쪽 방향으로 회전하는 행동 구현
3. 시뮬레이션 시작
   3-1. 왼쪽으로 회전
   3-2. 바라보는 방향으로 이동한 후의 좌표 계산
   3-3. 그 좌표에 해당하는 칸으로 갈지 말지 판단
   3-4. 가지 않는다면 다시 왼쪽으로 회전
   3-5. 4번 회전해서 처음 바라보는 방향으로 돌아왔다면, 후진할지 말지 판단

격자 기반의 시뮬레이션 문제에서 어디가 (1, 1)과 (N, M)인지에 따라 x, y를 설정할 것.