블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.또한 본 글의 모든 내용은 한빛미디어 출판사에서 출판한 나동빈의 이것이 취업을 위한 코딩 테스트다 with 파이썬 : 구현를 참고했음을 알립니다.
도입
구현(Implementation) 알고리즘의 개념에 대해 학습하고 관련된 문제를 풀이한다.
개념
구현(Implementation)은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정을 의미한다. 이는 곧 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이기도 하다.
해당 책에서는 완전 탐색과 시뮬레이션 알고리즘을 구현 유형으로 묶어서 다루고 있는데 완전 탐색의 경우 모든 경우의 수에 대해 계산해야 하는 알고리즘이고 시뮬레이션의 경우 문제에 제시된 알고리즘을 단계 별로 하나씩 수행해야 하기 때문이다.
구현에서는 결국 문제에서의 조건을 잘 해석하고 시간 복잡도에 대한 부분을 고민하는 게 중요한데 파이썬의 경우 C/C++과 같이 정적으로 자료형을 선언하지 않기 때문에 자료형의 크기에 대한 재설정 부분은 고민하지 않아도 좋고 대신 리스트의 크기만 생각해보면 좋다.
대부분의 코딩 테스트는 메모리를 128MB부터 512MB까지로 제한하는데 1,000만 이하의 데이터를 리스트로 다루는 게 약 40MB 정도의 메모리를 사용하기 때문에 리스트에 담기는 데이터의 수를 대략 계산해서 생각해보면 좋다.
추가로 2020년 파이썬 3.7을 기준으로 1초에 2,000만 번의 연산을 수행한다고 가정하면 대략적으로 시간과 메모리를 계산할 수 있다. 따라서 시간 제한이 1초이고 데이터의 개수가 100만 개인 문제가 있다면 시간 복잡도를 O(NlogN) 이내의 알고리즘을 이용하여 풀어야 한다. N의 값이 100만일 때 NlogN의 값이 곧 2,000만이기 때문이다.
실전문제
01. 왕실의 나이트
접근법
처음에 상하좌우 모두 두 칸씩 움직이고 그 다음에는 상하로 움직인 경우 좌우 한 칸, 좌우로 움직인 경우 상하 한 칸을 움직이게 된다.
결국 딱 한번의 움직임에 대한 이동 가능여부를 구하면 되기 때문에 상하좌우로 두 칸씩 이동 가능한 경우인지 먼저 조건을 따지고 이후 그곳에서 한 칸 이동 가능한 경우인지 조건을 따지면 된다.
소스 코드
point: str = input()
answer: int = 0
moves = ['U', 'R', 'D', 'L']
for move in moves:
if move == 'U':
if int(point[1]) > 2:
if (point[0] != 'a') and (point[0] != 'h'):
answer += 2
else:
answer += 1
elif move == 'R':
if point[0] < 'g':
if (int(point[1]) != 1) and (int(point[1]) != 8):
answer += 2
else:
answer += 1
elif move == 'D':
if int(point[1]) < 7:
if (point[0] != 'a') and (point[0] != 'h'):
answer += 2
else:
answer += 1
elif move == 'L':
if point[0] > 'b':
if (int(point[1]) != 1) and (int(point[1]) != 8):
answer += 2
else:
answer += 1
print(answer)시간 복잡도
상하좌우 네 번에 대한 경우의 수만 구하면 되기 때문에 시간 복잡도는 상수 시간으로 O(4)이다. 내부적으로 조건문을 따지는 게 사실 반복문의 수보다 더 많이 들어서 해당 상수시간보다는 크지만 그렇게 유의미한 결과를 내지는 않을 것 같아 반복문으로만 따졌다.
기타
조금 더 까다롭게 문제를 출제할 경우 입력 문자가 열과 행이 아닌 행과 열 형태로 들어왔을 경우에 대한 예외 처리를 요구할 수 있다고 적혀 있었다. 라이브 코딩으로 문제를 풀 경우 이러한 입력이 완전히 잘못된 경우에 대한 예외 케이스를 항상 생각해야겠다.
02. 게임 개발
접근법
이런 문제의 경우 방문했던 곳에 대한 정보를 저장해두는 게 좋기 때문에 방문한 좌표를 저장할 2차원 배열을 선언한다.
다음으로는 반복을 멈추게 되는 경우에 대한 조건을 확실히 판단하는 게 좋다.
따라서 한 바퀴를 다 돌아서 뒤로 한칸 움직이려 할 때 해당 부분이 바다가 아니면 이미 가봤던 곳이더라도 이동할 수 있지만 만약 바다일 경우 반복문을 빠져 나와야 한다.
소스코드
N, M = list(map(int, input().split()))
x, y, direction = list(map(int, input().split()))
map_info: list[list[int]] = [ list(map(int, input().split())) for _ in range(N) ]
visited_info: list[list[int]] = [ [0] * M for _ in range(N) ]
answer: int = 1
visited_info[x][y] = 1
circle: int = 0
move_measures: list[tuple(int, int)] = [ (-1, 0), (0, 1), (1, 0), (0, -1) ]
while True:
if circle == 4:
x_destination = x - move_measures[direction][0]
y_destination = y - move_measures[direction][1]
if map_info[x_destination][y_destination] == 1:
break
else:
circle = 0
x, y = x_destination, y_destination
else:
direction -= 1
if direction == -1:
direction = 3
x_destination = x + move_measures[direction][0]
y_destination = y + move_measures[direction][1]
if visited_info[x_destination][y_destination] == 0 and \
map_info[x_destination][y_destination] == 0:
circle = 0
visited_info[x_destination][y_destination] = 1
answer += 1
x, y = x_destination, y_destination
else:
circle += 1
print(answer)시간 복잡도
이런 시뮬레이션 유형의 구현 문제는 시간 복잡도를 어떻게 구해야할지 감이 잘 안 온다.
최악의 경우를 생각했을 때 주어진 N,M 크기에서 모든 가변을 제외하고 가운데를 전부 도는 경우라 생각되어 O((N-2) * (M-2)) 정도로 예측했는데 정확한 측정 방법인지 잘 모르겠다.
기출문제
01. 럭키 스트레이트
접근법
좌측과 우측을 나누어 각각 합하고 그 결괏값을 비교하면 된다.
소스 코드
소스 코드는 01. 럭키 스트레이트.py 파일에서 확인 가능하다.
N: list[int] = [ int(number) for number in input() ]
left_sum: int = 0
right_sum: int = 0
for idx in range(len(N) // 2):
left_sum += N[idx]
right_sum += N[len(N) - idx - 1]
if left_sum == right_sum:
print("LUCKY")
else:
print("READY")시간 복잡도
주어진 N의 길이의 절반 만큼만 반복문을 작동하면 되기 때문에 시간 복잡도는 결국 O(N/2)이다.
그런데 상수 등은 전부 제외하니까 단순하게 O(N)으로 생각해도 될 것 같다.
02. 문자열 재정렬
접근법
반복문을 문자열 S의 길이 N만큼 작동하며 isnumeric() 내장함수를 통해 만약 숫자일 경우 누적합을 구하고 아닐 경우 문자이기 때문에 새로운 문자에 이어 붙인다.
이후 sorted() 내장함수를 사용하 문자열을 오름차순 정렬하고 그 뒤에 누적합을 str() 내장함수를 사용해 문자열로 변경하여 이어 붙이면 된다.
이때 유의할 점은 sorted() 내장함수의 반환 자료형이 리스트이기 때문에 join() 내장함수를 사용하여 그 반환값을 문자열로 만들어줘야 한다는 것이다.
소스 코드
소스 코드는 02. 문자열 재정렬.py 파일에서 확인 가능하다.
S: str = input()
only_characters: str = ""
cumulative_number: int = 0
for character in S:
if character.isnumeric():
cumulative_number += int(character)
else:
only_characters += character
answer = "".join(sorted(only_characters)) + str(cumulative_number)
print(answer)시간 복잡도
sorted() 내장함수의 시간 복잡도가 O(NlogN)이기 때문에 결국 시간 복잡도는 O(NlogN)이다.
03. 문자열 압축
접근법
처음에는 그리디를 풀듯 접근했다. 그래서 첫 문자와 동일한 문자를 만나기 바로 직전까지로 생각했었는데 이 경우 "aababa" 같은 테스트 케이스를 통과하지 못한다.
그래서 단순히 완전 탐색으로 문자열 길이의 절반까지 반복문을 돌며 내부에 중첩 반복문으로 문자열 길이의 절반 이하까지의 정수를 range() 내장함수의 건너뛰기 값으로 사용했다.
이때 이전 문자열과 현재 문자열이 같은 경우 개수를 늘리고 다른 경우 새로운 문자열이 등장한 것이기 때문에 이전 문자열과 함께 그 개수가 2 이상이면 문자열에 함께 더해준다.
마지막에 남은 문자열과 그 개수가 2 이상이면 더해주고 이때 그 길이가 이전 압축에 대한 길이보다 작을 경우 그것을 사용하여 가장 작은 값을 반환하면 된다.
소스 코드
소스 코드는 03. 문자열 압축.py 파일에서 확인 가능하다.
s: str = input()
answer: int = len(s)
for jump_idx in range(1, (len(s) // 2) + 1):
count: int = 0
result_string: str = ""
previous_string: str = s[:jump_idx]
for idx in range(0, len(s), jump_idx):
target_string: str = s[idx:idx+jump_idx]
if target_string == previous_string:
count += 1
else:
result_string += previous_string
if count != 1:
result_string += str(count)
count = 1
previous_string = target_string
result_string += previous_string
if count != 1:
result_string += str(count)
if answer > len(result_string):
answer = len(result_string)
print(answer)시간 복잡도
시간 복잡도는 O(N^2)이다.
04. 자물쇠와 열쇠
접근법
기본적으로 key[M-1][M-1] 요소의 값과 lock[0][0] 값을 비교하면서 반복문을 수행해야 하기 때문에 상하좌우에 M-1개 만큼의 배열이 추가된 새로운 자물쇠 배열을 만들어서 문제를 풀 수 있다.
이렇게 새로운 배열이 만들어졌을 때 서로 다른 크기의 2차원 배열에 대한 비교를 어떻게 반복문을 통해 가능할지 구현하는데 쉽지 않았으며 추가로 최종적으로 자물쇠가 전부 요구사항에 맞게 열렸는지 확인할 때 돌기와 돌기가 만난 경우에 대한 처리를 해주지 못해서 몇 개의 테스트 케이스를 통과하지 못했었다.
2차원 배열을 90도로 회전할 때 기존 array[x][y] 값은 array[y][length-1-x] 와 같다는 공식을 잊지 말아야겠다.
소스 코드
소스 코드는 04. 자물쇠와 열쇠.py 파일에서 확인 가능하다.
def validate_lock(M: int, N: int, new_lock: list[list[int]]) -> bool:
for i in range(N):
for j in range(N):
if new_lock[M-1+i][M-1+j] != 1:
return False
return True
def rotate(key: list[list[int]]) -> list[list[int]]:
temp: list[list[int]] = [ [0] * len(key) for _ in range(len(key)) ]
for i in range(len(key)):
for j in range(len(key)):
temp[i][j] = key[j][len(key)-1-i]
return temp
def solution(key: list[list[int]], lock: list[list[int]]) -> bool:
M: int = len(key)
N: int = len(lock)
new_lock: list[list[int]] = [
[0] * ((M-1)*2+N) for _ in range((M-1)*2+N)
]
for i in range(N):
for j in range(N):
new_lock[M-1+i][M-1+j] = lock[i][j]
answer: bool = False
for _ in range(4):
for x in range((M-1)+N):
for y in range((M-1)+N):
for i in range(M):
for j in range(M):
new_lock[x+i][y+j] += key[i][j]
if validate_lock(M, N, new_lock):
return True
else:
for i in range(M):
for j in range(M):
new_lock[x+i][y+j] -= key[i][j]
key = rotate(key)
return answer시간 복잡도
시간 복잡도를 구하는 게 조금 무의미한 문제라 생각은 되는데 M은 무조건 N보다 작거나 같기 때문에 최악의 경우 M과 N의 크기가 같을 때 반복문이 총 4번 중첩되기 때문에 시간 복잡도는 O(N^4)이라 할 수 있다.
기타
2차원 배열을 각각 90도, 180도, 270도를 회전하는 함수는 각각 아래와 같다.
def rotate_90(array: list[list[int]]) -> list[list[int]]:
x_length: int = len(array)
y_length: int = len(array[0])
temp: list[list] = [
[0] * x_length for _ in range(y_length)
]
for i in range(x_length):
for j in range(y_length):
temp[i][j] = array[j][x_length-1-i]
return temp
def rotate_180(array: list[list[int]]) -> list[list[int]]:
x_length: int = len(array)
y_length: int = len(array[0])
temp: list[list] = [
[0] * x_length for _ in range(y_length)
]
for i in range(x_length):
for j in range(y_length):
temp[i][j] = array[x_length-1-i][y_length-1-j]
return temp
def rotate_270(array: list[list[int]]) -> list[list[int]]:
x_length: int = len(array)
y_length: int = len(array[0])
temp: list[list] = [
[0] * x_length for _ in range(y_length)
]
for i in range(x_length):
for j in range(y_length):
temp[i][j] = array[y_length-1-j][i]
return temp 05. 뱀
접근법
이전에 풀었던 게임 개발 문제와 유사하다.
방문한 위치에 대한 정보를 저장하는 배열을 만들고 현재 위치 정보를 계속 저장해나가는데 만약 목표 위치에 사과가 있을 경우 배열에 가장 처음 들어왔던 정보부터 제거하면 된다.
소스 코드
소스 코드는 05. 뱀.py 파일에서 확인 가능하다.
N: int = int(input())
map_info: list[int] = [ [0] * N for _ in range(N) ]
for _ in range(int(input())):
x, y = list(map(int, input().split()))
map_info[x-1][y-1] += 1
move_info: dict[int, str] = {}
for _ in range(int(input())):
time, direction = input().split()
move_info[int(time)] = direction
visited_info: list = []
moved_measure: list[tuple(int, int)] = [ (0, 1), (1, 0), (0, -1), (-1, 0) ]
current_x: int = 0
current_y: int = 0
current_direction: int = 0
answer: int = 0
while True:
answer += 1
x_destination = current_x + moved_measure[current_direction][0]
y_destination = current_y + moved_measure[current_direction][1]
if (x_destination > (N-1)) or (y_destination > (N-1)) or \
(x_destination < 0) or (y_destination < 0):
break
elif (x_destination, y_destination) in visited_info:
break
else:
visited_info.append((current_x, current_y))
current_x, current_y = x_destination, y_destination
if map_info[x_destination][y_destination] == 1:
map_info[x_destination][y_destination] = 0
else:
visited_info.pop(0)
if answer in move_info.keys():
if move_info[answer] == 'L':
current_direction -= 1
if current_direction == -1:
current_direction = 3
else:
current_direction += 1
if current_direction == 4:
current_direction = 0
print(answer)시간 복잡도
최악의 경우 보드의 크기인 N을 전부 다 도는 경우이기 때문에 시간 복잡도는 O(N^2)이다.
06. 기둥과 보 설치
접근법
처음에 전체 좌표가 존재하는 2차원 배열을 만들고 기둥과 보를 설치할 때마다 각 구조에 맞게 해당 배열에 값을 입력했다.
이때 validate_strucutre 라는 함수를 따로 만들어 해당 기둥과 보를 설치 가능한지, 혹은 삭제 가능한지 확인했는데 이때 문제는 전체 구조가 유효한지 여부를 판단한 것이 아닌 해당 설치 또는 삭제의 대상이 되는 기둥과 보의 설치 이후 좌표에 대한 부분만 유효성 검사를 진행했다는 점이다.
그래서 문제를 해결하지 못해서 정답을 확인한 결과 전체 배열에 대한 유효성 검사를 진행하는 게 접근 방법이었다.
소스 코드
소스 코드는 06. 기둥과 보 설치.py 파일에서 확인 가능하다.
def validate_structure(answer: list[list[int]]) -> bool:
for x, y, structure in answer:
if structure == 0:
if y == 0:
pass
elif [x, y-1, 0] in answer:
pass
elif [x-1, y, 1] in answer:
pass
elif [x, y, 1] in answer:
pass
else:
return False
else:
if [x, y-1, 0] in answer:
pass
elif [x+1, y-1, 0] in answer:
pass
elif ([x-1, y, 1] in answer) and ([x+1, y, 1] in answer):
pass
else:
return False
return True
def solution(n: int, build_frame: list[list[int]]) -> list[list[int]]:
answer: list[list[int]] = []
for x, y, structure, work in build_frame:
if work == 0:
answer.remove([x, y, structure])
if not validate_structure(answer):
answer.append([x, y, structure])
else:
answer.append([x, y, structure])
if not validate_structure(answer):
answer.remove([x, y, structure])
return sorted(answer)시간 복잡도
시간 복잡도의 경우 주어진 배열의 크기인 N만큼 -내부 유효성 검사에서의 in 연산을 포함하여- 총 세 번의 반복문을 수행해야 하기 때문에 O(N^3)이다.
07. 치킨 배달
접근법
치킨 집의 좌표가 전부 저장되어 있는 배열에서 M개를 선택하는 조합을 구한 뒤 모든 조합의 경우의 수에 대한 집들의 치킨 거리를 구하여 가장 작은 값들만 선택해서 합하면 해당 조합에 대한 도시의 치킨 거리가 된다.
이후 각 조합에 대한 도시의 치킨 거리 값들 중에서 가장 작은 값을 선택하면 된다
소스 코드
처음에 M개를 선택하는 조합으로 생각하지 않고 1개부터 최대 M개까지의 조합으로 생각해서 문제를 풀었는데 문제에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실 을 알아내었기 때문에 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력 하는 게 요구사항이었다. 다시 말해 1개부터 M개까지의 모든 조합을 구하지 않더라도 M개의 조합만 구하면 되는 문제였다.
이때 조합의 경우 내장 모듈 itertools 에서 combinations 함수를 활용했다. 반대로 중복된 조합의 경우 permutations 함수를 사용하면 된다.
from itertools import combinations
def calculate_distance(
N: int, chickens: list[tuple[int, int]], houses: list[tuple[int, int]]
) -> int:
cumulative_distance: int = 0
for hx, hy in houses:
minimum_distance: int = 2*2*(N-1)*N
for cx, cy in chickens:
current_distance: int = abs(hx - cx) + abs(hy - cy)
if minimum_distance > current_distance:
minimum_distance = current_distance
cumulative_distance += minimum_distance
return cumulative_distance
from itertools import combinations
N, M = map(int, input().split())
houses, chickens = [], []
for i in range(N):
map_info: list[int] = list(map(int, input().split()))
for j in range(N):
if map_info[j] == 1:
houses.append((i, j))
elif map_info[j] == 2:
chickens.append((i, j))
answer: int = 2*2*N*(N-1)
target_chickens: list[tuple(int, int)] = combinations(chickens, M)
for target_chicken in target_chickens:
current_distance: int = calculate_distance(
N=N, chickens=target_chicken, houses=houses
)
if answer > current_distance:
answer = current_distance
print(answer)시간 복잡도
대략적으로 시간 복잡도는 O(N^3)이다.
08. 외벽 점검
외벽 점검의 경우 스터디 시간이 다 되어서 풀지 못했다. 따라서 이후에 도전하기로 하였다.
접근법
소스 코드
시간 복잡도
