[알고리즘 대비 - 이코테] 3. 구현

구현(Implementation)

• 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
• 사소한 조건 설정이 많을 경우 구현하기가 까다로움

1. 알고리즘은 간단한데 코드가 지나칠 만큼 길어니는 문제
2. 실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는 문제
3. 문자열을 특정한 기준에 따라서 끊어 처리(파싱)해야하는 문제
4. 적절한 라이브러리를 찾아서 사용해야하는 문제
5. Ex. Itertools 라이브러리 : 모든 순열이나 조합을 찾는 라이브러리

완전 탐색

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

시뮬레이션

: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형

변수의 표현 범위

: 파이썬에서는 기본적으로 큰 수의 연산을 지원해주기 때문에 변수의 표현 범위를 명시적으로 지정해주지 않아도 된다.

 

💡 C/C++/Java에서의 표현 범위

• int 자료형 이상의 수를 표현하기 위해선 BigInteger 라이브러리(자바의 경우만 해당) 또는 long long 자료형을 이용하면 된다.

파이썬에서 리스트 크기

int 자료형 데이터의 개수에 따른 메모리 사용량

1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

• 데이터 처리량이 많을 경우에는 메모리 제한을 반드시 고려해야한다.

⭐ 일반적인 코딩 테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야한다!

2차원 행렬(Matrix)

📢 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.

# 남, 서, 북, 동
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

# 현재 위치
x, y = 2, 2

for i in range(4):
    # 다음 위치
    nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny)

---

Q1. 상하좌우

문제 설명

여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.

이때, 여행가 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.

입력 조건

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 ≤ N ≤ 100)
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다. (1 ≤ 이동 횟수 ≤ 100)

출력 조건

• 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표(X, Y)를 공백으로 구분하여 출력한다.

풀이

from sys import stdin
N = int(stdin.readline())
plan = stdin.readline().split()

# 상좌하우 방향 벡터 사용
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]

# 입력 문자에 따른 방향 인덱스
plan_char = {'U':0, 'L':1, 'D':2, 'R':3}

# 현재(now) 위치
nx, ny = 1, 1

for p in plan:
    j = plan_char[p]
    # 임시(temporary) 위치
    tx = nx + dx[j]
    ty = ny + dy[j]

    # 좌표 밖을 벗어났을 경우
    if tx < 1 or tx > N or ty < 1 or ty > N:
        continue
    # 현재 위치 갱신
    else:
        nx, ny = tx, ty
print(ny, nx)

• 시간복잡도 : O(N)
• 일련의 명령에 따라 개체를 차례로 이동시키는 시뮬레이션 유형 문제

---

Q2. 시각

문제 설명

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력 조건

• 첫째 줄에 정수 N이 입력된다. (0 ≤ N ≤ 23)

출력 조건

• 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포하모디는 모든 경우의 수를 출력한다.

풀이

TRY 1

from sys import stdin
N = int(stdin.readline())
nm, ns = 0, 0
cnt = 0

# 시간에 '3'이 포함되지 않는 경우
# 3이 등장하는 횟수를 셈
while nm < 60:
    if ns == 60:
        ns = 0
        nm += 1
    else:
        if '3' in str(nm) or '3' in str(ns):
            cnt += 1
        ns += 1
# 시간에 '3'이 포함되는 경우
if N < 3:
    three_cnt = 0
elif N < 13:
    three_cnt = 1
elif N < 23:
    three_cnt = 2
else:
    three_cnt = 3
print((cnt * (N - three_cnt + 1)) + (60 * 60 * three_cnt))

• 시간복잡도 : O(N)
• 경우를 시간(nh)에 '3'이 포함되는 경우와 그렇지 않은 경우를 나눠서 생각했다.
  • 시간에 '3'이 포함되는 경우 : 모든 분, 초의 횟수를 세야하므로 단순 60 * 60 * (횟수) 연산을 수행한다.
  • 시간에 '3'이 포함되지 않는 경우 : 분 또는 초에 '3'이 포함되는 경우를 반복문을 이용하여 구하고 마지막에 해당 시간들을 곱해준다.

 

TRY 2

💯 str(h) + str(m) + str(s) : 문자열을 하나로 합쳐서 코드 반복을 줄일 수 있다!

from sys import stdin
N = int(stdin.readline())
cnt = 0

for h in range(N + 1):
    for m in range(60):
        for s in range(60):
            if '3' in str(h) + str(m) + str(s):
                cnt += 1
print(cnt)

• 하루는 86,400초로 총 경우의 수가 100,000개도 되지 않으므로 시간복잡도 O(N^3)의 알고리즘으로 풀어도 무방하다!
• 완전 탐색 유형(Brute Forcing) : 가능한 모든 경우의 수를 검사하는 탐색 방법
  • 비효율적인 시간 복잡도를 가지고 있으므로 데이터의 개수가 100만 개 이하일 때 적절하다!

---

Q3. 왕실의 나이트

문제 설명

행복 왕국의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

1. 수평으로 두 칸 이동한 뒤 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤 수평으로 한 칸 이동하기

이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.

입력 조건

• 첫째 줄에 8 x 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다.

출력 조건

• 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

풀이

from sys import stdin
P = stdin.readline().rstrip()
cnt = 0

nx = ord(P[0]) - ord('a') + 1
ny = int(P[1])

# horizontal to vertical, vertical to horizontal
dx = [-1, -1, 1, 1, -2, -2, 2, 2]
dy = [2, -2, 2, -2, 1, -1, 1, -1]

# 좌표 이동 다른 표현
# steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), 
# (2, 1), (1, 2), (-1, 2), (-2, 1)]

for i in range(8):
    if nx + dx[i] < 1 or nx + dx[i] > 8 or ny + dy[i] < 1 or ny + dy[i] > 8:
        continue
    cnt += 1
print(cnt)

• 시뮬레이션 문제
• dx, dy 와 같은 좌표 리스트 형태도 많이 사용되지만 튜플 리스트 형태도 많이 사용된다.

---

Q4. 게임 개발

문제 설명

현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.

캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해놓은 매뉴얼에 따라 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

입력 조건

• 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3 ≤ N, M ≤ 50)
• 둘째 줄에 게임 캐릭터가 있는 칸의 좌표(A, B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지가 존재한다.
• 0 : 북쪽 / 1 : 동쪽 / 2: 남쪽 / 3 : 서쪽
• 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어 있다.
• 0 : 육지 / 1 : 바다

출력 조건

• 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

풀이

from sys import stdin
N, M = map(int, stdin.readline().split())
nx, ny, nd = map(int, stdin.readline().split())
maps = []
cnt, flag = 0, 0

# 맵을 차례로 받아옴
for _ in range(N):
    maps.append(list(map(int, stdin.readline().split())))

# 현재 위치 방문 처리
maps[nx][ny] = 1

# 북, 동, 남, 서
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

while 1:
    move_x, move_y = nx+dx[(nd + 3) % 4], ny+dy[(nd + 3) % 4]

    # 왼쪽으로 회전한 방향이 갈 수 있는 칸이면 전진 후 현재 위치 갱신
    if maps[move_x][move_y] == 0:
        nx, ny = move_x, move_y
        maps[move_x][move_y] = 1 # 방문 처리
        cnt += 1
    # 네 방향 모두 가본 칸 또는 바다인 경우    
    else:
        if flag > 4:
            # 뒤로 이동
            move_x, move_y = nx + dx[(nd + 2) % 4], ny+dy[(nd + 2) % 4]
            # 뒤도 막힌 경우
            if maps[move_x][move_y] == 1:
                break
            nx, ny = move_x, move_y
            cnt += 1
            flag = 0
        # 방향 전환만 한 경우
        else:
            nd = (nd + 3) % 4
            flag += 1
print(cnt)

• 시뮬레이션
• 회전을 어떻게 구현할 지가 가장 관건
  • Try : 현재 바라보는 방향으로 부터 왼쪽 회전이니까 -1을 생각 → 인덱스 0인 경우 음수를 가리키게 됨
  • Solving : (nd + 3) % 4 로 음수 인덱스 처리

 

---

해당 포스팅의 내용은

저)나동빈님의 『이것이 취업을 위한 코딩 테스트다 with 파이썬』을

통해 공부한 내용을 토대로 작성하였습니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬

저자 | 나동빈

출판 | 한빛미디어

발매 | 2020.08.05.