[이코테] 상하좌우

문제 풀면서 작성한 메모

풀이 과정

---

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

N x N 크기의 정사각형 공간이 주어진다. 시작 좌표는 항상 (1,1)이며, 최대 좌표는 (N, N)이다. 주의할 점은 정사각형 공간을 벗어나는 움직임은 무시된다는 점이다. 입력 첫째 줄에 공간의 크기를 나타내는 N이 주어지고, 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. 입력 조건을 메모했고, 최종적으로 도착하는 지점의 좌표를 출력하면 된다.

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

구현 문제이므로 알고리즘을 떠올리기는 쉬웠으나 막상 소스코드로 구현하는 데는 어려움이 있었다. 주의할 점이 없었다면 바로 코딩할 수 있는 문제였으나 주의할 점으로 인해 문제가 조금 까다로워졌다. 

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

N은 n, x 좌표는 x, y 좌표는 y, 여행가 A가 이동할 계획서 내용은 plan, plan에 있는 이동방향 하나하나는 direction이라 이름 지었다. 

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

# N 저장

# plan 저장

# x, y 초기화

# direction에 따라 좌표 움직이기
# 단, 정사각형 공간을 벗어나는 움직임은 무시

# 최종 x, y 출력

가장 머리를 써야 하는 부분은 8번째 줄이었다. 정사각형 공간 안에서만 움직일 수 있도록 하려면 어떻게 해야 할까 하다가 while문이 생각났다. 그런데 문제를 다 풀고 나니 while문을 왜 생각했는지 모르겠다. 아마 while True 해놓고 정사각형 공간 밖으로 벗어나면 break를 하고 싶었던 것 같은데 이 문제는 정사각형 공간 밖으로 벗어나면 연산을 멈추는 게 아니라 연산을 하지 않고 다음 연산을 해야 한다. 어떻게 구현할지 좀 더 생각해보고 의사 코드를 작성해야 했는데 시간제한 때문에 마음이 급해져 바로 코딩을 했다. 그러다 보니 더 오래 걸렸다. 꼼꼼히 생각해보지 않고 실행만 반복하다 보니 주어진 15분을 초과해서 총 33분이나 걸려서 아쉬웠던 문제다. 

 

L인 경우 x-=1, R인 경우 x+=1, U인 경우 y+=1, D인 경우 y-=1라고 적었는데 이것도 틀렸다. 사례로 든 케이스를 잘 살펴봤어야 하는데 내가 아는 x, y 좌표로 생각해버렸다. 이 문제는 L인 경우 y-=1, R인 경우 y+=1, U인 경우 x-=1, D인 경우 x+=1이다. 코딩 테스트 문제에서 내 선입견이 들어가면 안 된다는 것을 깨달았다. 내가 아는 x, y 좌표평면이 아닐 수 있고 내가 아는 큰 수의 법칙이 아닐 수 있다. 선입견 없이 문제에서 주어지는 그대로 받아들여야 한다.

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

# N 저장
n = int(input())

# plan 저장
plan = input().split()

# x, y 초기화
x, y = 1, 1

# direction에 따라 좌표 움직이기
# 단, 정사각형 공간을 벗어나는 움직임은 무시
for direction in plan:
  if direction == 'L':
    y -= 1
    if y < 1 or y > n:
      y += 1
  elif direction == 'R':
    y += 1
    if y < 1 or y > n:
      y -= 1
  elif direction == 'U':
    x -= 1
    if x < 1 or x > n:
      x += 1
  elif direction == 'D':
    x += 1
    if x < 1 or x > n:
      x -= 1

# 최종 x, y 출력
print(x, y)

direction은 L, R, U, D 중 하나이기 때문에 elif문을 사용했다. 그리고 일단 이동을 했다. 왜냐하면 이동을 한 위치를 계산을 해야 그 위치가 정사각형에서 벗어났는지 확인할 수 있기 때문이다. 결국 정사각형 밖을 벗어나더라도 해당 위치는 계산을 해야 한다. 따라서 일단 이동하고 정사각형 밖을 벗어나면 다시 back 했다. if문이 많아 조금 지저분해 보이긴 했지만 반복문을 사용하기에는 연산할 내용이 각자 다르기 때문에 어쩔 수 없다고 생각했다.

답안 예시

---

4-1.py

# N 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()

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

# 이동 계획을 하나씩 확인
for plan in plans:
    # 이동 후 좌표 구하기
    for i in range(len(move_types)):
        if plan == 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)

내가 작성한 코드와 달랐던 점은 두 가지이다.

 

먼저, 6번째 줄부터 9번째 줄까지 보면 L, R, U, D에 따른 이동 방향을 아예 리스트로 만들어서 for문을 돌았다. 훨씬 깔끔한 코드였다. 각 case마다 다르게 연산을 해야 해서 for문은 불가능하다 생각했는데 아예 더해줄 값과 빼줄 값마저 리스트로 만드니 가능했다.

 

두 번째로 달랐던 점은 나는 일단 이동하고 정사각형 밖을 벗어나면 back 했는데 여기서는 아예 임시 값으로 nx, ny를 선언해 공간을 벗어나지 않는 경우에만 이동했다. 이동 횟수가 많아질수록 이 방식이 더 효율적이라는 생각이 들었다.

개념 정리

---

구현

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

 

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

 

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

 

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

완전 탐색

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

시뮬레이션

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

 

이 문제는 시뮬레이션 유형으로 분류했지만 알고리즘 교재나 문제 풀이 사이트에 따라서 다르게 일컬을 수 있으니 코딩 테스트에서의 시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 서로 유사한 점이 많다는 정도로만 기억하자.

코드

---

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

출처

---

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