[이코테] 왕실의 나이트

문제 풀면서 작성한 메모

풀이 과정

---

우선 이 문제는 시간제한이 20분인데 20분 안에 풀지 못했다. 시간도 초과되고 풀다가 막히니까 하기가 싫어졌다. 상하좌우 문제와 굉장히 비슷해서 똑같이 풀면 된다고 생각했는데 막상 적용하기가 어려웠다. 머리를 좀 더 써야 했는데 더 이상 생각하기가 싫었다. 그래서 일단 모로 가도 서울만 가면 된다고, 그냥 일일이 case를 나눠 작성해서 통과했다. 1시간 6분 만이었다. 생각하기가 싫을 땐 어떻게 해야 할까? ㅋㅋㅋ 하.. 연습이라 마음이 풀어진 건가.. 실전에서는 보통 괜찮은 해결책이 떠오르지 않을 때 일단 다른 문제로 넘어갔다 다시 온다. 처음 생각나는 풀이가 너무 노가다인 것 같을 때 어떤 규칙이 있는지를 생각해보자. 최대한 규칙을 찾아보려 노력하지만 마땅히 떠오르지 않을 때는 차라리 노가다로라도 풀어서 통과하는 게 나을 것 같다. 

1. 문제를 정독하면서 메모한다. 주의해야 할 것은 ※으로 표시한다.

8 x 8 좌표평면이 있고 나이트의 위치가 입력 첫째 줄에 주어진다. 행은 1부터 8까지, 열은 특이하게 a부터 h까지이다. 나이트가 이동할 수 있는 경우의 수를 출력하면 된다. 사례로 든 a1과 c2를 작성하고 이 둘을 시뮬레이션해봤다. 나이트는 아래 2가지 경우로만 이동할 수 있다.

 

1. 수평2 수직1: 수평(왼쪽, 오른쪽)으로 2번 갈 수 있는지 * 수직(위, 아래)으로 1번 갈 수 있는지 = 2 * 2

2. 수직2 수평1: 수직(위, 아래)으로 2번 갈 수 있는지 * 수평(왼쪽, 오른쪽)으로 1번 갈 수 있는지 = 2 * 2

 

따라서 나올 수 있는 총 경우의 수는 2*2 + 2*2 = 8가지이다. 이 말은 즉슨, 나이트가 이동할 수 있는 경우의 수가 최대 8이라는 말이다. 최대 8밖에 안되니 모든 경우의 수를 일일이 계산해도 문제없다.

2. 알고리즘을 떠올리고 적용하려고 노력한다.

구현 문제이다. 경우의 수를 계산해보라는 말에 완전 탐색이라 생각했고 문제에서 제시하는 알고리즘을 한 단계씩 차례대로 직접 수행해봐야 하므로 시뮬레이션 유형도 된다. 상하좌우 문제와 굉장히 유사하다고 생각은 했으나 어떻게 적용할지를 모르겠어서 일일이 8가지 케이스를 나눠 작성했다,, 또르르,, 

[이코테] 상하좌우

3. 필요한 변수에 대해서는 변수명을 작성한다.

나이트의 위치를 location으로, 행은 row, 열은 col, 나이트가 이동할 수 있는 경우의 수는 cnt로 이름 지었다. 

4. 바로 문제 풀지 말고 주석을 달며 의사 코드를 작성한다.

# 나이트의 위치 location 저장

# location을 row와 col로 분리

# rows와 cols 선언

# 나이트가 이동할 수 있는 경우의 수 cnt 선언

# rowIndex와 colIndex 찾기

# 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동
# 왼쪽으로 2번
  ## 위로 1 번
  ## 아래로 1번

# 오른쪽으로 2번
  ## 위로 1번
  ## 아래로 1번

# 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동
# 위로 2번
  ## 왼쪽으로 1 번
  ## 오른쪽으로 1번

# 아래로 2번
  ## 왼쪽으로 1 번
  ## 오른쪽으로 1번

# cnt 출력

의사 코드를 작성하다 보니 문제점이 생겼다. 열이 숫자가 아닌 문자라는 것이다. 경우의 수를 세려면 직접 이동해가며 그 위치가 정원 밖이 아닌지 확인해야 하는데 열이 숫자가 아닌 문자라면 +1을 해도 다음 문자가 되지 않는다. 따라서 index로 접근해야 했다. 나올 수 있는 모든 행을 rows, 나올 수 있는 모든 열을 cols라 선언했다. 그리고 입력받은 row와 col이 이 rows와 cols에서 어떤 index인지를 나타내는 rowIndex와 colIndex도 추가로 선언했다. 

5. 의사 코드에 맞춰 구현한다.

# 나이트의 위치 location 저장
location = input()

# location을 row와 col로 분리
col = location[0]
row = location[1]

# rows와 cols 선언
cols = "abcdefgh"
rows = "12345678"

# 나이트가 이동할 수 있는 경우의 수 cnt 선언
cnt = 0

# rowIndex와 colIndex 찾기
colIndex = cols.index(col)
rowIndex = rows.index(row)

# 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동
# 왼쪽으로 2번
newColIndex = colIndex - 2
if newColIndex >= 0:
  ## 위로 1 번
  newRowIndex = rowIndex - 1
  if newRowIndex >= 0:
    cnt += 1
  ## 아래로 1번
  newRowIndex = rowIndex + 1
  if newRowIndex < len(rows):
    cnt += 1

# 오른쪽으로 2번
newColIndex = colIndex + 2
if newColIndex < len(cols):
  ## 위로 1번
  newRowIndex = rowIndex - 1
  if newRowIndex >= 0:
    cnt += 1
  ## 아래로 1번
  newRowIndex = rowIndex + 1
  if newRowIndex < len(rows):
    cnt += 1

# 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동
# 위로 2번
newRowIndex = rowIndex - 2
if newRowIndex >= 0:
  ## 왼쪽으로 1 번
  newColIndex = colIndex - 1
  if newColIndex >= 0:
    cnt += 1
  ## 오른쪽으로 1번
  newColIndex = colIndex + 1
  if newColIndex < len(cols):
    cnt += 1

# 아래로 2번
newRowIndex = rowIndex + 2
if newRowIndex < len(rows):
  ## 왼쪽으로 1 번
  newColIndex = colIndex - 1
  if newColIndex >= 0:
    cnt += 1
  ## 오른쪽으로 1번
  newColIndex = colIndex + 1
  if newColIndex < len(cols):
    cnt += 1

# cnt 출력
print(cnt)

문제는 통과했지만 정말 소스코드 업로드하기 민망했던 게 내가 봐도 복잡하고 헷갈리는 코드였기 때문이다. 보통은 케이스 하나하나 생각해보면서 일일이 다 적어놓고 그 안에서 규칙성을 찾으려 하는데 여기서는 도무지 찾기가 힘들었다.

답안 예시

---

4-3.py 답안 예시

# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
    # 이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_column = column + step[1]
    # 해당 위치로 이동이 가능하다면 카운트 증가
    if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
        result += 1

print(result)

 

먼저, 문자라면 유니코드 값으로 바꿔서 숫자로 처리해줄 수 있다는 점을 생각 못했다. 이렇게 하면 rows, cols, rowIndex, colIndex를 선언할 필요도 없이 더 쉬워진다. ord 함수는 문자의 유니코드 값을 돌려주는 함수이다. 배우긴 했는데 써먹은 적이 없어서 잊혀졌다.. 기억해놔야지! 아래 링크는 ord 함수에 대한 설명과 소스코드이다. 

 

05-5 내장 함수

 

그리고 역시나 상하좌우 문제와 마찬가지로 규칙성이 있었다. 바뀌는 부분만 리스트 안에 넣어주면 되는데 나는 크게 보지 못하고 너무 세세하게 나눠서 생각했던 것 같다. steps 리스트나 이전 상하좌우 문제에서 dx, dy 리스트와 같은 형태는 자주 사용된다 하니 앞으로 이 문제가 나오면 꼭 맞추도록 하자! 

개념 정리

---

구현

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

 

취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제된다. 구현 유형은 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제다. 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다. 구현 유형의 문제는 문제의 길이가 꽤 긴 편이지만 고차원적 사고력을 요구하는 문제는 나오지 않는 편이라 오히려 쉽게 풀 수 있다.

 

혹시 코팅 테스트 환경에서 파이썬3 뿐만 아니라 Pypy3도 지원한다면 Pypy3의 실행 속도가 때로는 C/C++과 견줄 만큼 빠르므로 Pypy3을 이용하도록 하자. 특히 반복문이 많을수록 Pypy3와 파이썬3의 속도가 차이가 난다.

 

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

완전 탐색

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

시뮬레이션

문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

코드

---

GitHub - leeejihyun/algorithm: 알고리즘 문제 풀이

출처

---

나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2021), p115-117