[코테 알고리즘] 구현 / 관련 문제

본 글은 "나동빈"님의 [이것이 코딩 테스트다]를 참고하여 작성하였으며, 필자가 직접 문제를 풀며 관련된 문제들을 찾아 정리하였습니다.

시리즈 보기
[코테 알고리즘] 파이썬 기본 / 관련 문제
[코테 알고리즘] 파이썬 주요 라이브러리 / 관련 문제
[코테 알고리즘] 그리디 / 관련 문제
[코테 알고리즘] 구현 / 관련 문제
[코테 알고리즘] DFS, BFS / 관련 문제
[코테 알고리즘] 정렬 / 관련 문제
[코테 알고리즘] 다이나믹 프로그래밍 / 관련 문제
[코테 알고리즘] 최단 경로 / 관련 문제
[코테 알고리즘] 그래프 이론 / 관련 문제

 

구현

• 머릿속에 있는 알고리즘을 소스 코드로 바꾸는 과정
• 구현하기 어려운 문제
  • 알고리즘은 간단하지만 코드가 길어지는 문제
  • 실수 연산을 다루고, 특정 소수점까지 출력해야하는 문제
  • 문자열을 특정한 기준에 따라서 끊어서 처리해야하는 문제
  • 적절한 라이브러리를 찾아서 사용하는 문제
• 사소한 입력 조건 등을 문제에서 명시하며 문제의 길이가 긴 경우가 많음

 

행렬 이용

• 2차원 공간은 행렬로 사용
  • 방향 백터로 위치를 옮김

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

# 이동
for i in range(4):
	nx = x + dx[i]
	ny = y + dy[i]

 

유형

• 시뮬레이션 유형, 구현 유형, 완전 탐색 유형(Brute Forcing)은 유사도가 높음

 

완전탐색

• 모든 경우의 수를 주저없이 다 계산하는 방법
• 반복문 혹은 재귀 함수 사용
• 예외 케이스 모두 확인
• DFS / BFS 알고리즘을 이용해 문제를 해결

 

시뮬레이션

• 복잡한 구현 모두 코드로 옮기기
• 문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행

 

문제

치킨 배달

15686번: 치킨 배달

import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())
city = list(list(map(int, input().split())) for _ in range(n))
result = int(1e9)
house = []
chick = []

for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            house.append([i, j])
        elif city[i][j] == 2:
            chick.append([i, j])

for chi in combinations(chick, m):
    temp = 0
    for h in house: 
        chi_len = int(1e9)
        for j in range(m):
            chi_len = min(chi_len, abs(h[0] - chi[j][0]) + abs(h[1] - chi[j][1]))
        temp += chi_len
    result = min(result, temp)

print(result)

• 조합 / 순열 라이브러리 적절히 사용

 

ZOAC 3

20436번: ZOAC 3

left, right = input().split()
strings = list(input())

keyboard = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']
mo = 'yuiophjklbnm'

xl, yl, xr, yr = None, None, None, None

for i in range(len(keyboard)):
    if left in keyboard[i]:
        xl = i
        yl = keyboard[i].index(left)

    if right in keyboard[i]:
        xr = i
        yr = keyboard[i].index(right)

time = 0
for string in strings:
    time += 1
    if string in mo:
        for i in range(len(keyboard)):
            if string in keyboard[i]:
                nx = i
                ny = keyboard[i].index(string)

                time += abs(nx - xr) + abs(ny - yr)
                xr = nx
                yr = ny
                break
    else:
        for i in range(len(keyboard)):
            if string in keyboard[i]:
                nx = i
                ny = keyboard[i].index(string)

                time += abs(nx - xl) + abs(ny - yl)
                xl = nx
                yl = ny
                break

print(time)

 

• 쫄지말고 구현하는 것이 핵심