구현
구현 : 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 과정
구현 능력이 요구되는 대표적인 알고리즘 문제 유형으로 완점 탐색과 시뮬레이션이 있다.
완전 탐색 : 모든 경우의 수를 빠짐없이 다 계산하는 해결 방법을 의미
- dfs, bfs 알고리즘을 이용해서 문제를 해결한다.
시뮬레이션 : 문제에서 제시하는 논리나 동작 과정을 그대로 코드로 옮겨야 하는 유형을 의미
- 문제에서 요구하는 복잡한 구현 요구사항을 그대로 코드로 옮겨야 한다는 점에서 해결 방법이 비슷하다.
표준 라이브러리 itertools
원소를 나열하는 모든 경우의 수를 고려해야하는 상황에서 보통 순열이나 조합 라이브러리를 사용할 때 itertools로 구현한다.
소스코드를 구현하기가 까다롭거나, 까다로운 문자열 처리를 해야 하거나, 구현해야 할 소스코드의 양이 매우 많은 문제도 구현 유형으로 구분한다.
[Q 07] 럭키 스트레이트
n = input()
front_n = n[0:len(n)//2]
back_n = n[len(n)//2:len(n)]
front_n = map(int,front_n)
back_n = map(int,back_n)
result_f = sum(front_n)
result_b = sum(back_n)
if result_f == result_b:
print('LUCKY')
else:
print('READY')
[Q 08] 문자열 재정렬
list을 문자열로 변환하기
A = ['a','b','c']
stra = ''.join(A)
print(stra)소스
s = input()
alpa = []
sum = 0
for i in range(len(s)):
if '1' <= s[i] and s[i] <= '9':
sum += int(s[i])
else:
alpa.append(s[i])
alpa.sort()
alpa.append(str(sum))
print(''.join(alpa))
[Q 09] 문자열 압축
def solution(s):
answer = 0
total = ''
result = ''
for i in range(1, len(s)//2+1):
check_in_s = s[:i]
cnt = 1
result = ''
# print("i : ",i,end = " ")
for j in range(i,len(s),i):
# print("j : ",j,end = " ")
check_after_s = s[j:i+j]
# print("after_s : ",check_after_s, end=" ")
if check_in_s == check_after_s:
cnt += 1
else:
if cnt > 1:
result += str(cnt) + check_in_s
else:
result += check_in_s
check_in_s = check_after_s
cnt = 1
# print("result : ",result, end=" ")
# print()
if cnt > 1:
result += str(cnt) + check_in_s
else:
result += check_in_s
# print("result : ",len(result), " ",result)
# print()
if total == '' or len(total) > len(result):
total = result
answer = len(total)
if answer == 0:
answer = 1
return answer
[Q 10] 자물쇠와 열쇠
해야할 일 : 열쇠를 적당히 회전하고 이동시켜 자물쇠의 홈에 딱 맞게 끼워 넣는 것
크기가 20 x 20 인 2차원 리스트에 있는 모든 원소에 접근할 때는 400만큼의 연산이 필요하다.
완전 탐색을 이용하여 열쇠를 이동이나 회전시켜서 자물쇠에 끼워보는 작업을 전부 시도해보는 접근 방법을 이용할 수 있다.
예시에서
일 때,
와 같이 된다.
Lock 빈공간에 Key가 넣어지면 문이 열리게 된다.
Lock을 대상으로 모든 경우를 확인하면 된다.
완전 탐색을 수월하게 하기 위해서 자물쇠 리스트의 크기를 3배 이상으로 변경하면 계산이 수월해진다.
열쇠와 자물쇠가 3 * 3 크기일 때, 가장 먼저 자물쇠를 크기가 3배인 새로운 리스트로 만들어 중앙 부분으로 옮긴다.
이제 열쇠 배열을 왼쪽 위부터 시작해서 한 칸씩 이동하는 방식으로 차례대로 자물쇠의 모든 홈을 채울 수 있는지 확인한다.
0 : 홈, 1 : 돌기 부분
자물쇠 리스트에 열쇠 리스트의 값을 더한 뒤, 더한 결과를 확인했을 때 자물쇠 부분의 모든 값이 정확히 1인지를 확인하면 된다.
모든 값이 정확히 1이라면 자물쇠의 홈 부분을 정확히 채운 것이다.
소스에서 사용되는 rotate_a_matrix_by_90_degree() 메소드
: 2차원 리스트를 90도 회전한 결과를 반환하는 메서드 (파이썬에서 2차원 리스트를 다룰 때 가끔식 사용된다.)
# 2차원 리스트 90도 회전
def rotate_a_matrix_by_90_degree(a):
n = len(a) # 행 길이 계산
m = len(a[0]) # 열 길이 계산
result = [[0] * n for _ in range(m)] # 결과 리스트
for i in range(n):
for j in range(m):
result[j][n - i - 1] = a[i][j]
return result
# 자물쇠의 중간 부분이 모두 1인지 확인
def check(new_lock):
lock_length = len(new_lock) // 3
for i in range(lock_length, lock_length * 2):
for j in range(lock_length, lock_length * 2):
if new_lock[i][j] != 1:
return False
return True
def solution(key, lock):
n = len(lock)
m = len(key)
# 자물쇠의 크기를 기존의 3배로 변환
new_lock = [[0] * (n * 3) for _ in range(n * 3)]
# 새로운 자물쇠의 중앙 부분에 기존의 자물쇠 넣기
for i in range(n):
for j in range(n):
new_lock[i + n][j + n] = lock[i][j]
# 4가지 방향에 대해서 확인
for rotation in range(4):
key = rotate_a_matrix_by_90_degree(key) # 열쇠 회전
for x in range(n * 2):
for y in range(n * 2):
# 자물쇠에 열쇠를 끼워 넣기
for i in range(m):
for j in range(m):
new_lock[x+i][y+j] += key[i][j]
# 새로운 자물쇠에 열쇠가 정확히 들어맞는지 검사
if check(new_lock) == True:
return True
# 자물쇠에서 열쇠를 다시 빼기
for i in range(m):
for j in range(m):
new_lock[x + i][y + j] -= key[i][j]
return False# 강의 영상 : https://youtu.be/RrWnBaflV2o
def match(arr, key, rot, r, c):
n = len(key)
for i in range(n):
for j in range(n):
# 회전 값이 없다면 그대로 복사한다.
# 이외는 회전한다.
if rot == 0:
arr[r + i][c + j] += key[i][j]
elif rot == 1:
arr[r + i][c + j] += key[n - 1 - j][i]
elif rot == 2:
arr[r + i][c + j] += key[n - 1 - i][n - 1 - j]
else:
arr[r + i][c + j] += key[j][n - 1 - i]
def check(arr, offset, n):
for i in range(n):
for j in range(n):
if arr[offset+ i][offset + j] != 1:
return False
return True
def solution(key, lock):
offset = len(key) - 1
# key * key 크기의 사각형에서
# offset은 겹치는 부분 제외 나머지 부분
for r in range(offset + len(lock)):
for c in range(offset + len(lock)):
for rot in range(4):
# 90도 방향으로 돌려본다. (4번을 돌리게 된다.)
# 열쇠 같은 경우 최대 가로 20, 20, 20 세로 20, 20, 20
# 최대한 하나는 겹쳐야 하므로 key 양쪽 끝 2개를 제외함으로
# 60 - 2 = 58개가 필요하다.
arr = [[0 for _ in range(58)] for _ in range(58)]
# 자물쇠를 offset만큼 떨어진 위치에 복사한다.
for i in range(len(lock)):
for j in range(len(lock)):
arr[offset + i][offset + j] = lock[i][j]
# r, c, rot를 통하여 열쇠를 복사한다.
match(arr, key, rot, r, c)
if check(arr, offset, len(lock)):
return True
return False
k = [[0,0,0],[1,0,0],[0,1,1]]
lock = [[1,1,1],[1,1,0],[1,0,1]]
solution(k, lock)
[Q 11] 뱀
n = int(input())
k = int(input())
data = [[0] * (n + 1) for _ in range(n + 1)] # 맵 정보
info = [] # 방향 회전 정보
# 맵 정보(사과 있는 곳은 1로 표시)
for _ in range(k):
a, b = map(int, input().split())
data[a][b] = 1
# 방향 회전 정보 입력
l = int(input())
for _ in range(l):
x, c = input().split()
info.append((int(x), c))
# 처음에는 오른쪽을 보고 있으므로(동, 남, 서, 북)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def turn(direction, c):
if c == "L":
direction = (direction - 1) % 4
else:
direction = (direction + 1) % 4
return direction
def simulate():
x, y = 1, 1 # 뱀의 머리 위치
data[x][y] = 2 # 뱀이 존재하는 위치는 2로 표시
direction = 0 # 처음에는 동쪽을 보고 있음
time = 0 # 시작한 뒤에 지난 '초' 시간
index = 0 # 다음에 회전할 정보
q = [(x, y)] # 뱀이 차지하고 있는 위치 정보(꼬리가 앞쪽)
while True:
nx = x + dx[direction]
ny = y + dy[direction]
# 맵 범위 안에 있고, 뱀의 몸통이 없는 위치라면
if 1 <= nx and nx <= n and 1 <= ny and ny <= n and data[nx][ny] != 2:
# 사과가 없다면 이동 후에 꼬리 제거
if data[nx][ny] == 0:
data[nx][ny] = 2
q.append((nx, ny))
px, py = q.pop(0)
data[px][py] = 0
# 사과가 있다면 이동 후에 꼬리 그대로 두기
if data[nx][ny] == 1:
data[nx][ny] = 2
q.append((nx, ny))
# 벽이나 뱀의 몸통과 부딪혔다면
else:
time += 1
break
x, y = nx, ny # 다음 위치로 머리를 이동
time += 1
if index < l and time == info[index][0]: # 회전할 시간인 경우 회전
direction = turn(direction, info[index][1])
index += 1
return time
print(simulate())
[Q12 기둥과 보 설치]
전체 명령의 개수 : M(1,000개 이하)
시간 복잡도 : 빅오(M^2), 시간 제한이 5초이므로 빅오(M^3) 사용가능
기둥과 보를 중점 
기둥과 맞닿으면 보를 설치할 수 있다.
설치 및 삭제 연산을 요구할 때마다 일일이 '전체 구조물을 확인하며' 규칙을 확인한다.
possible() 메서드
- 현재의 구조물이 정상인지를 체크
- 매번 연산이 발생할 때마다, possible() 메서드를 호출하여 현재 구조물이 정상인지 체크
- 정상이 아니라면 현재의 연산을 무시
# 현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):
for x, y, stuff in answer:
if stuff == 0: # 설치된 것이 '기둥'인 경우
# '바닥 위' 혹은 '보의 한쪽 끝부분 위' 혹은 '다른 기둥 위'라면 정상
if y == 0 or [x - 1, y, 1] in answer or [x, y, 1] in answer or [x, y - 1, 0] in answer:
continue
return False # 아니라면 거짓(False) 반환
elif stuff == 1: # 설치된 것이 '보'인 경우
# '한쪽 끝부분이 기둥 위' 혹은 '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
if [x, y - 1, 0] in answer or [x + 1, y - 1, 0] in answer or ([x - 1, y, 1] in answer and [x + 1, y, 1] in answer):
continue
return False # 아니라면 거짓(False) 반환
return True
def solution(n, build_frame):
answer = []
for frame in build_frame: # 작업(frame)의 개수는 최대 1,000개
x, y, stuff, operate = frame
if operate == 0: # 삭제하는 경우
answer.remove([x, y, stuff]) # 일단 삭제를 해본 뒤에
if not possible(answer): # 가능한 구조물인지 확인
answer.append([x, y, stuff]) # 가능한 구조물이 아니라면 다시 설치
if operate == 1: # 설치하는 경우
answer.append([x, y, stuff]) # 일단 설치를 해본 뒤에
if not possible(answer): # 가능한 구조물인지 확인
answer.remove([x, y, stuff]) # 가능한 구조물이 아니라면 다시 제거
return sorted(answer) # 정렬된 결과를 반환
[Q13 치킨 배달]
문제 이해
0 : 빈칸, 1 : 집, 2 : 치킨집
기존에 존재하는 치킨집을 줄여서 최대 M개로 유지하면서, 일반 집들로부터 M개의 치킨 집까지의 거리를 줄이는 것이 목표이다.
이후에 도시의 치킨 거리 합의 최솟값을 계산하면 된다.
예시 결과 이와 같이 된다.
치킨집의 개수 범위 : M <= 치킨집의 개수 <= 13
만약, 치킨집 중에서 M개를 고르는 조합을(Combinations) 고려한다면 경우의 수
최대 13개에서 M개를 선택하는 조합과 동일하다.
13CM의 값은 100,000을 넘지 않는다.
집의 개수 또한 최대 100개이기 때문에, 모든 경우의 수를 다 계산하더라도 시간 초과 없이 문제를 해결할 수 있다.
파이썬에서는 조합 라이브러리를 제공
이를 이용하면 모든 경우를 간단히 계산할 수 있다.
치킨집 중에서 M개를 고르는 모든 경우에 대해서 치킨 거리의 합을 계산하여(완전 탐색), 치킨 거리의 최솟값을 구해 출력하면 된다.
5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2
candidates 결과 예시
[((0, 1), (3, 0)), ((0, 1), (4, 0)), ((0, 1), (4, 1)), ((0, 1), (4, 4)), ((3, 0), (4, 0)), ((3, 0), (4, 1)), ((3, 0), (4, 4)), ((4, 0), (4, 1)), ((4, 0), (4, 4)), ((4, 1), (4, 4))]
소스
from itertools import combinations
n, m = map(int, input().split())
chicken, house = [], []
for r in range(n):
data = list(map(int, input().split()))
for c in range(n):
if data[c] == 1:
house.append((r, c)) # 일반 집
elif data[c] == 2:
chicken.append((r, c)) # 치킨 집
# 모든 치킨집 중에서 m개의 치킨집을 뽑는 조합 계산
candidates = list(combinations(chicken, m))
# 치킨 거리의 합을 계산하는 함수
def get_sum(candiate):
result = 0
# 모든 집에 대하여
for hx, hy in house:
# 가장 가까운 치킨집을 찾기
temp = 1e9
for cx, cy in candiate:
temp = min(temp, abs(hx - cx) + abs(hy - cy))
# 가장 가까운 치킨집까지의 거리를 더하기
result += temp
# 치킨 거리의 합 반환
return result
# 치킨 거리의 합의 최소를 찾아 출력
result = 1e9
for candiate in candidates:
result = min(result, get_sum(candiate))
print(result)
[Q14 외벽 점검]
n : 외벽의 길이
weak : 취약 지점의 위치
dist : 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열
weak 리스트와 dist 리스트의 길이가 매우 작다.
주어지는 데이터의 개수가 적을 때는 모든 경우를 일일이 확인하는 완전 탐색으로 접근해볼 수 있다.
문제에서 찾고자 하는 값 : 투입해야 하는 친구 수의 최솟값
전체 친구의 수 최대 값 : 8(dist의 길이 최대 값)
모든 친구를 무작위로 나열하는 모든 순열의 개수 : 8P8 = 8! = 40,320으로 충분히 계산 가능한 경우의 수
(순열 : Permutations)
from itertools import permutations
arr = ['A', 'B', 'C']
nPr = permutations(arr, 2)
print(list(nPr))
# 결과
# [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
친구를 나열하는 모든 경우의 수를 각각 확인하여 친구를 최소 몇 명 배치하면 되는지 계산하면 문제를 해결할 수 있다.
다만, 문제에서는 취약한 지점들이 원형으로 구성되어 있다고 설명하고 있다.
원형으로 나열된 데이터를 처리하는 경우에는, 문제 풀이를 간단히 하기 위하여 길이를 2배로 늘려서 '원형'을 일자 형태로 만드는 작업을 해주면 유리하다.
ex) n : 12, weak : [1, 3, 4, 9, 10], dist : [3m, 5m, 7m], result : 1
취약한 지점을 2번 나열해서 '원형'을 일자 형태로 만든다. 점검시간 1시간(n : 12)
- 취약한 지점 : 1, 3, 4, 9, 10, 13, 15, 16, 21, 22
각 친구를 나열하는 모든 경우의 수 : 3! = 6가지
- [3m, 5m, 7m]
- [3m, 7m, 5m]
- [5m, 3m, 7m]
- [5m, 7m, 3m]
- [7m, 3m, 5m]
- [7m, 5m, 3m]
각각의 경우에 대하여 5개의 취약한 지점을 모두 검사할 수 있는지 확인하면 된다.
친구를 나열하는 경우의 수 중 [7m, 3m, 5m]를 확인해보면
7m을 이동할 수 있는 친구가 9m 지점에서 출발하여 5곳을 방문한다면 7m만 이동해도 모든 취약 지점을 점검할 수 있다.
- 1, 3, 4, 9, 10, 13, 15, 16, 21, 22
소스
from itertools import permutations
def solution(n, weak, dist):
# 길이를 2배로 늘려서 '원형'을 일자 형태로 변형
length = len(weak)
for i in range(length):
weak.append(weak[i] + n)
answer = len(dist) + 1 # 투입할 친구 수의 최솟값을 찾아야 하므로 len(dist) + 1로 초기화
# 0부터 length - 1까지의 위치를 각각 시작점으로 설정
for start in range(length):
#print()
#print("시작지점(start) : ", start)
# 친구를 나열하는 모든 경우의 수 각각에 대하여 확인
for friends in list(permutations(dist, len(dist))):
#print("friends : ", friends, end=' ')
count = 1 # 투입할 친구의 수
# 해당 친구가 점검할 수 있는 마지막 위치
position = weak[start] + friends[count - 1]
#print("친구가 점검할 수 있는 마지막 위치 : ", position, ":", weak[start], "+", friends[count - 1])
# 시작점부터 모든 취약 지점을 확인
#print("시작점 부터 모든 취약지점을 확인", start, start + length)
for index in range(start, start + length):
# 점검할 수 있는 위치를 벗어나는 경우
if position < weak[index]:
#print("현재 index", index, "해당 친구가 점검할 수 있는 마지막 위치 < 취약한 지점 :", position, weak[index], end =' ')
count += 1 # 새로운 친구를 투입
#print("새로운 친구를 투입")
if count > len(dist): # 더 투입이 불가능하다면 종료
#print("새로운 친구 명수가, 총 투입될 수 있는 인원수 보다 많아 종료")
break
position = weak[index] + friends[count - 1]
#print("새로운 친구가 점검할 수 있는 마지막 위치 업데이트 : ", position,":",weak[index]," + ",friends[count-1], " index, count : ", index, count)
answer = min(answer, count) # 최솟값 계산
#print("결과 : ", answer)
if answer > len(dist):
return -1
return answer
참고자료
- https://youtu.be/_hVVk-frECw
- 이것이 취업을 위한 코딩 테스트다.
- 프로그래머스
