실전 문제 풀어보기!
실전 알고리즘 문제는 문제를 어떻게 풀지 알려주지 않는다고 한다. (뭐 당연한 이야기겠지만...ㅠㅠㅠ)
이때까지 배운 것들을 가지고 어떤 알고리즘을 사용하면 좋을지 생각해 보고 문제를 풀어보자!!
실전문제
Q. 연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다.
이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다.
게임이 끝나는데 걸리는 최소 시간을 구하시오.
⠀
조건은 다음과 같다.
코니는 처음 위치 C에서 1초 후 1만큼 움직이고,
이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다.
즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다.
⠀
브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다.
코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다.
브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다
⠀
c = 11 # 코니의 처음 위치
b = 2 # 브라운의 처음 위치
- Queue를 실전에서 사용하려면?
-> 코딩테스트에서 큐는collections.deque를 사용해야 한다. (성능차이 때문에..!!)
>>> from collections import deque
>>> queue = deque()
>>> queue.append(3)
>>> queue.append(4)
>>> print(queue.popleft())
3코니의 위치 변화 : 1초마다 1씩 증가, 그다음 조건인 '이전 이동 거리 + 1'
=> 즉, 증가하는 속도가 1초마다 1씩 증가한다는 소리이다.
1, 2, 3, 4, 5, 6, .....
브라운의 위치 변화는 선택할 수 있다.
1-1. 2-1 = 1
1-2. 2+1 = 3
1-3. 2x2 = 4
1-1-1. 1-1 = 0
1-1-2. 1+1 = 2
1-1-3. 1x2 = 2
1-2-1. 3-1 = 2
1-2-2. 3+1 = 4
1-2-3. 3x2 = 6
이런 식으로 무수한 갈래로 계속해서 뻗어 나갈 수 있어서 구하기 어렵다..
규칙성이 없고, 모든 경우의 수를 다 제고해 봐야 한다면, 바로 --> BFS 를 사용해야 한다는 것을 알아채야 한다!
코니가 브라운을 잡는다는 의미는 같은 시간에 같은 위치에 있어야 한다는 것을 의미한다.
그렇기에 규칙적인 '배열' 과 자유자재로 데이터를 넣을 수 있는 '딕셔너리'를 함께 사용한다.
[{ }]
from collections import deque
c = 11
b = 2
def catch_me(cony_loc, brown_loc):
# 구현해보세요!
time = 0 # 항상 시간을 점검해야 하니 time 변수 필요
queue = deque()
queue.append((brown_loc, 0)) # 위치와 시간을 함께 queue 에 포함시켜 준다. [브라운위치][시간]
# 성공조건을 위한 배열 (코니와 브라운의 위치와 시간이 동일해야 한다.)
visited = [{} for _ in range(200001)] # 방문한 시간와 위치를 저장하기 위해 배열을 만든다.
# 위치마다 브라운이 방문한 시간을 적기 위해 배열 안에 딕셔너리를 넣는다.
# 5 in visited[3] 는 5초에 위치 3을 방문했는지 여부를 저장하고,
# 9 in visited[3] 는 9초에 위치 3을 방문했는지 여부를 저장한다.
# visited[위치][시간]
# visited[cony_loc][time]
while cony_loc <= 200000:
cony_loc += time # +1 +2 +3 +4 +5 .... 시간만큼 가속도가 붙기 때문에
if time in visited[cony_loc]:
return time # 코니와 브라운이 만나는 시점 return
for i in range(0, len(queue)):
current_position, current_time = queue.popleft()
new_time = current_time + 1
new_position = current_position - 1
if 0 <= new_position <= 200000 and new_time not in visited[new_position]:
visited[new_position][new_time] = True
queue.append((new_position, new_time))
new_position = current_position + 1
if 0 <= new_position <= 200000 and new_time not in visited[new_position]:
visited[new_position][new_time] = True
queue.append((new_position, new_time))
new_position = current_position * 2
if 0 <= new_position <= 200000 and new_time not in visited[new_position]:
visited[new_position][new_time] = True
queue.append((new_position, new_time))
time += 1
return -1 # 코니 위치가 조건에 부합하지 않는다면 -1을 return 한다.
print(catch_me(c, b)) # 5가 나와야 합니다!
print("정답 = 3 / 현재 풀이 값 = ", catch_me(10,3))
print("정답 = 8 / 현재 풀이 값 = ", catch_me(51,50))
print("정답 = 28 / 현재 풀이 값 = ", catch_me(550,500))
2번문제
Q. 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다.
⠀
최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
⠀
간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.
⠀
예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
⠀
다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.
⠀
압축할 문자열 input이 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 string_compression 함수를 완성해주세요.
⠀
- 문자열의 길이는 1 이상 1,000 이하입니다.
- 문자열은 알파벳 소문자로만 이루어져 있습니다.
⠀
이 때, 문자열은 항상 제일 앞부터 정해진 길이만큼 잘라야 합니다.
입출력 예 #5 처럼 xababcdcdababcdcd 이 입력되어도,
문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.
⠀
"aabbaccc" # -> 7
"ababcdcdababcdcd" # -> 9
"abcabcdede" # -> 8
"abcabcabcabcdededededede" # -> 14
"xababcdcdababcdcd" # -> 17
['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e']
['ab', 'ca', 'bc', 'ab', 'ca', 'bc', 'de', 'de', 'de', 'de', 'de', 'de']
['abc', 'abc', 'abc', 'abc', 'ded', 'ede', 'ded', 'ede']
['abca', 'bcab', 'cabc', 'dede', 'dede', 'dede']
['abcab', 'cabca', 'bcded', 'edede', 'dede']
['abcabc', 'abcabc', 'dedede', 'dedede']
['abcabca', 'bcabcde', 'dededed', 'ede']
['abcabcab', 'cabcdede', 'dededede']
['abcabcabc', 'abcdedede', 'dedede']
['abcabcabca', 'bcdededede', 'dede']
['abcabcabcab', 'cdedededede', 'de']
None# 주석으로 설명 작성
input = "abcabcabcabcdededededede"
def string_compression(string):
n = len(string)
compression_length_array = []
for split_size in range(1, n // 2): # 문자열을 나누는 기준을 구하는 반복문, 1 ~ n // 2(반까지만 구하면 됨)
splited = [string[i:i+split_size] for i in range(0, n, split_size)]
# 0부터 n까지 split_size 만큼
# print(splited)
compressed = "" # 압축할 수 있는 문자열인지 비교하기 위해 저장해두는 변수
count = 1 # splited 에서 자른 문자열을 비교하기 위해 사용
for j in range(1, len(splited)):
prev, cur = splited[j-1], splited[j] # 첫 문자열과 다음 문자열 비교
if prev == cur: # 0번째와 1번쨰
count += 1
else: # 이전 문자와 다르다면
if count > 1:
compressed += (str(count) + prev)
else: # 문자가 반복되지 않을 때
compressed += prev
count = 1 # 초기화
if count > 1: # splited 배열의 마지막 문자까지 앞 문자와 동일하다면
compressed += (str(count) + splited[-1])
else: # 동일하지 않다면 그냥 문자열 추가
compressed += prev
compression_length_array.append(len(compressed))
return min(compression_length_array)
print(string_compression(input)) # 14 가 출력되어야 합니다!
print("정답 = 3 / 현재 풀이 값 = ", string_compression("JAAA"))
print("정답 = 9 / 현재 풀이 값 = ", string_compression("AZAAAZDWAAA"))
print("정답 = 12 / 현재 풀이 값 = ", string_compression('BBAABAAADABBBD'))
문제 3
문제 설명
카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.
수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.
⠀
용어의 정의
'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.
그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
예를 들어, "(()))("와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 문자열은 아닙니다.
반면에 "(())()"와 같은 문자열은 균형잡힌 괄호 문자열 이면서 동시에 올바른 괄호 문자열 입니다.
⠀
'(' 와 ')' 로만 이루어진 문자열 w가 균형잡힌 괄호 문자열 이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환할 수 있습니다.
⠀
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
4-3. ')'를 다시 붙입니다.
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
4-5. 생성된 문자열을 반환합니다.
⠀
균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를 반환하시오.
⠀
"(()())()" # -> "(()())()"
")(" # -> "()"
"()))((()" # -> "()(())()"
from collections import deque
balanced_parentheses_string = "()))((()"
def is_correct_parentheses(string): # 올바른 괄호 문자열인지 확인해 주는 함수
stack = []
for s in string:
if s == '(':
stack.append(s)
elif stack:
stack.pop()
return len(stack) == 0 # stack에 아무것도 남아있지 않다면 올바른 괄호 문자열임을 알 수 있다.
# 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
# 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
def separate_to_u_v(string):
queue = deque(string)
left, right = 0, 0
u, v = "", ""
while queue:
char = queue.popleft()
u += char
if char == '(':
left += 1
else:
right += 1
if left == right:
break
v = ''.join(list(queue))
# print(u, v)
return u, v
# 4번 - else에서 빼온 함수
def revers_parentheses(string):
reversed_string = ""
for char in string:
if char == '(':
reversed_string += ")"
else:
reversed_string += "("
return reversed_string
def change_to_correct_parentheses(string):
# 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
if string == "":
return ""
# 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
# 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
u, v = separate_to_u_v(string)
# 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
if is_correct_parentheses(u):
return u + change_to_correct_parentheses(v) # 재귀함수 사용
# 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
# 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
# 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
# 4-3. ')'를 다시 붙입니다.
# 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
# 4-5. 생성된 문자열을 반환합니다.
else:
return "(" + change_to_correct_parentheses(v) + ')' + revers_parentheses(u[1:-1]) # 4-1 ~ 4-3
def get_correct_parentheses(balanced_parentheses_string):
if is_correct_parentheses(balanced_parentheses_string):
return balanced_parentheses_string
else:
return change_to_correct_parentheses(balanced_parentheses_string)
# ')' 가 나오면 queue 에다가 넣어놨다가, '(' 가 나오는 것을 확인하면, '('의 개수별로
# queue 에 있던 얘들을 popleft() 시키면 된다.
print(get_correct_parentheses(balanced_parentheses_string)) # "()(())()"가 반환 되어야 합니다!문제 4
Q. 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다.
새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다.
말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다.
체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.
⠀
게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.
⠀
턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.
⠀
1. A번 말이 이동하려는 칸이
1) 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
- A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
- 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
2) 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
- A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
- A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
3) 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다.
4) 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.
⠀
다음은 크기가 4×4인 체스판 위에 말이 4개 있는 경우이다.
⠀
⠀
체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때,
게임이 종료되는 턴의 번호를 반환하시오.
⠀
그 값이 1,000보다 크거나 절대로 게임이 종료되지 않는 경우에는 -1을 반환한다.
⠀
입력
각 정수는 칸의 색을 의미한다. 0은 흰색, 1은 빨간색, 2는 파란색이다.
말의 개수와 체스판의 정보, 현재 말의 위치와 방향을 주어진다.
말의 정보는 세 개의 정수로 이루어져 있고,
순서대로 행, 열의 인덱스, 이동 방향이다.
행과 열의 번호는 0부터 시작하고, 이동 방향은 0, 1, 2, 3 이고
0부터 순서대로 →, ←, ↑, ↓의 의미를 갖는다.
⠀k = 4 # 말의 개수 ⠀ chess_map = [ [0, 0, 2, 0], [0, 0, 1, 0], [0, 0, 1, 2], [0, 2, 0, 0] ] start_horse_location_and_directions = [ [1, 0, 0], [2, 1, 2], [1, 1, 0], [3, 0, 1] ] # 이 경우는 게임이 끝나지 않아 -1 을 반환해야 합니다!⠀
K = 4 # 말의 개수 ⠀ chess_map = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ] start_horse_location_and_directions = [ [0, 0, 0], [0, 1, 0], [0, 2, 0], [2, 2, 2] ] # 이 경우는 2 을 반환해야 합니다!
========
k = 4 # 말의 개수
chess_map = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
start_horse_location_and_directions = [
[0, 0, 0],
[0, 1, 0],
[0, 2, 0],
[2, 2, 2]
]
# 이 경우는 게임이 끝나지 않아 -1 을 반환해야 합니다!
# 동 서 북 남
# →, ←, ↑, ↓
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]
# 동 → 서 : 0 → 1
# 서 → 동 : 1 → 0
# 북 → 남 : 2 → 3
# 남 → 북 : 3 → 2
# ==> 홀 수 = -1 / 짝수 = + 1
def get_d_index_when_go_back(d):
if d % 2 == 0:
return d + 1
else:
return d - 1
# 말은 순서대로 이동한다. -> 말의 순서에 따라 반복문
# 말이 쌓일 수 있다. -> 맵에 말이 쌓이는 걸 저장해놔야 한다.
# 쌓인 순서대로 이동한다. -> stack 사용
# 현재 맵에 어떻게 말이 쌓일지 저장하기 위해서 리스트를 만들어 준다.
def get_game_over_turn_count(horse_count, game_map, horse_location_and_directions):
n = len(chess_map)
current_stacked_horse_map = [ # 3차원 배열
[
[] for _ in range(n)
] for _ in range(n)
]
for i in range(horse_count):
r, c, d = horse_location_and_directions[i] # row, column, direction
current_stacked_horse_map[r][c].append(i)
turn_count = 1
while turn_count <= 1000:
for horse_index in range(horse_count):
r, c, d = horse_location_and_directions[horse_index]
new_r = r + dr[d]
new_c = c + dc[d]
# 파란색이거나 맵을 나갔을 때
if not 0 <= new_r < n or not 0 <= new_c < n or game_map[new_r][new_c] == 2:
new_d = get_d_index_when_go_back(d)
horse_location_and_directions[horse_index][2] = new_d
new_r = r + dr[new_d]
new_c = c + dc[new_d]
# 가기로 한 곳이 막혀 있으면 안감
if not 0 <= new_r < n or not 0 <= new_c < n or game_map[new_r][new_c] == 2:
continue
# 2가 이동한다고 하면 2랑 3만 이동한다.
# 즉, 자기자신의 인덱스보다 큰 애들만 데리고 간다.
moving_horse_index_array = [] # 이동할 말만 넣어주는 변수
for i in range(len(current_stacked_horse_map[r][c])):
current_stacked_horse_index = current_stacked_horse_map[r][c][i]
if horse_index == current_stacked_horse_index: # 현재 이동하고 있는 말과 위치에 저장되어 있는 말의 index가 같은지 확인한다.
moving_horse_index_array = current_stacked_horse_map[r][c][i:] # 위로 쌓여 있는 index 애들을 업고 함께 움직이기 때문
current_stacked_horse_map[r][c] = current_stacked_horse_map[r][c][:i] # 현재 위치에는 남은 애들 (첫 인덱스와 i번째 까지의 말)을 다시 저장해준다.
break # 현재 이동하려고 하는 말을 알았으면 반복문을 중단한다.
if game_map[new_r][new_c] == 1: # 이동하려는 칸의 위치가 1이면 방향(direction)을 변경해야 한다.
moving_horse_index_array = reversed(moving_horse_index_array)
for moving_horse_index in moving_horse_index_array:
current_stacked_horse_map[new_r][new_c].append(moving_horse_index)
horse_location_and_directions[moving_horse_index][0], horse_location_and_directions[moving_horse_index][1] = new_r, new_c
# 턴이 진행되는 중 말이 4개 이상 쌓이는 순간 게임이 종료된다.
if len(current_stacked_horse_map[new_r][new_c]) >= 4:
return turn_count
turn_count += 1
# print(current_stacked_horse_map) # 현재 각 체스 말들이 어떻게 쌓여져 있는지 저장해 놓는 공간이 된다.
return -1
print(get_game_over_turn_count(k, chess_map, start_horse_location_and_directions)) # 2가 반환 되어야합니다문제 5
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
⠀
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
⠀
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
⠀
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
⠀
보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
입력
보드를 나타내는 2차원 배열 game_map이 주어진다.
이 때, 보드의 행, 열의 길이는 3이상 10 이하다.
⠀
보드 내에 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다.
'.'은 빈 칸을 의미하고,
'#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며,
'O'는 구멍의 위치를 의미한다.
'R'은 빨간 구슬의 위치,
'B'는 파란 구슬의 위치이다.
⠀
입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
⠀
출력
파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 True, 없으면 False를 반환한다.
⠀game_map = [ ["#", "#", "#", "#", "#"], ["#", ".", ".", "B", "#"], ["#", ".", "#", ".", "#"], ["#", "R", "O", ".", "#"], ["#", "#", "#", "#", "#"], ] # -> True를 반환해야 한다. ⠀ game_map = [ ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"], ["#", "R", "#", ".", ".", ".", "#", "#", "B", "#"], ["#", ".", ".", ".", "#", ".", "#", "#", ".", "#"], ["#", "#", "#", "#", "#", ".", "#", "#", ".", "#"], ["#", ".", ".", ".", ".", ".", ".", "#", ".", "#"], ["#", ".", "#", "#", "#", "#", "#", "#", ".", "#"], ["#", ".", "#", ".", ".", ".", ".", "#", ".", "#"], ["#", ".", "#", ".", "#", ".", "#", ".", ".", "#"], ["#", ".", ".", ".", "#", ".", "O", "#", ".", "#"], ["#", "#", "#", "#", "#", "#", "#", "#", "#", "#"] ] # -> False 를 반환해야 한다
============
from collections import deque
# 모든 경우를 탐색해야함으로 BFS 사용
game_map = [
["#", "#", "#", "#", "#"],
["#", ".", ".", "B", "#"],
["#", ".", "#", ".", "#"],
["#", "R", "O", ".", "#"],
["#", "#", "#", "#", "#"],
]
# 북 동 남 서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
# 방문 저장 여부인 visited 배열을 만들어야 하는데,
# red, blue 구슬로 구슬이 2개 이다.
# 이때는 4차원 배열을 사용하면 된다.
# visited[red_marble_row][red_marble_col][blue_marble_row][blue_marble_col]
def move_until_wall_or_hole(r, c, diff_r, diff_c, game_map):
move_count = 0
while game_map[r + diff_r][c + diff_c] != '#' and game_map[r][c] != 'O':
r += diff_r
c += diff_c
move_count += 1
return r, c, move_count
def is_available_to_take_out_only_red_marble(game_map):
n, m = len(game_map), len(game_map[0])
visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
red_row, red_col, blue_row, blue_col = -1, -1, -1, -1
queue = deque()
for i in range(n):
for j in range(m):
if game_map[i][j] == "R":
red_row, red_col = i, j
elif game_map[i][j] == "B":
blue_row, blue_col = i, j
# 탐색을 10번까지만 할 수 있다.
queue.append((red_row, red_col, blue_row, blue_col, 1)) # 1 == 탐색 횟수
visited[red_row][red_col][blue_row][blue_col] = True
while queue:
red_row, red_col, blue_row, blue_col, try_count = queue.popleft()
if try_count > 10:
break
for i in range(4):
next_red_row, next_red_col, r_count = move_until_wall_or_hole(red_row, red_col, dr[i], dc[i], game_map)
next_blue_row, next_blue_col, b_count = move_until_wall_or_hole(blue_row, blue_col, dr[i], dc[i], game_map)
if game_map[next_blue_row][next_blue_col] == 'O':
continue
if game_map[next_red_row][next_red_col] == 'O':
return True
if next_red_row == next_blue_row and next_red_col == next_blue_col:
if r_count > b_count:
next_red_row -= dr[i]
next_red_col -= dc[i]
else:
next_blue_row -= dr[i]
next_blue_col -= dc[i]
if not visited[next_red_row][next_red_col][next_blue_row][next_blue_col]:
visited[next_red_row][next_red_col][next_blue_row][next_blue_col] = True
queue.append((red_row, red_col, blue_row, blue_col, try_count + 1))
return False
print(is_available_to_take_out_only_red_marble(game_map)) # True 를 반환해야 합니다문제 6
Q. 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.
⠀
이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
⠀
임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.
⠀
예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.
⠀0 2 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 2⠀
0은 빈 칸, 1은 집, 2는 치킨집이다.
⠀
(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.
⠀
(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.
⠀
이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.
⠀
도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 반환하시오.
⠀
입력
N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
또한 도시의 정보가 주어진다.
⠀
도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.
⠀
출력
첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.
⠀n = 5 m = 3 ⠀ city_map = [ [0, 0, 1, 0, 0], [0, 0, 2, 0, 1], [0, 1, 2, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 2], ] # 5 가 출력되어야 합니다
==================
import itertools, sys
n = 5
m = 3
city_map = [
[0, 0, 1, 0, 0],
[0, 0, 2, 0, 1],
[0, 1, 2, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 2],
]
# 여러 개 중에서 M 개를 고른뒤, 모든 치킨거리의 합이 가장 작게 되는 경우 반환
# -> 여러 개 중에서 특정 개수를 뽑는 경우의 수 + 모든 경우의 수를 다 구해야 함
# ==> "조합" 사용
def get_min_city_chicken_distance(n, m, city_map):
chicken_location_list = []
home_location_list = []
for i in range(n):
for j in range(n):
if city_map[i][j] == 1: # 집
home_location_list.append([i, j])
elif city_map[i][j] == 2: # 치킨 집
chicken_location_list.append([i, j])
chicken_location_m_combinations = list(itertools.combinations(chicken_location_list, m))
min_distance_of_m_combinations = sys.maxsize
for chicken_location_m_combinations in chicken_location_m_combinations:
city_chicken_distance = 0 # 현재 도시의 치킨 거리
for home_r, home_c in home_location_list: # 각 거리의 치킨 거리를 구할 수 있다.
min_home_chicken_distance = sys.maxsize
for chicken_location in chicken_location_m_combinations:
min_home_chicken_distance = min(min_home_chicken_distance,
abs(home_r - chicken_location[0]) + abs(home_c - chicken_location[1]))
city_chicken_distance += min_home_chicken_distance
min_distance_of_m_combinations = min(min_distance_of_m_combinations, city_chicken_distance)
return min_distance_of_m_combinations
# 출력
print(get_min_city_chicken_distance(n, m, city_map)) # 5 가 반환되어야 합니다!
print("hihi")⠀
github 사용 방법에 대해서도 공부하였다!!
알고리즘 공부 5주차를 마무리 하였는데, 알고리즘이라는 것이 경험해 보지 않았을 때는 엄청 어렵겠구나 했다가 직접 경험해 보니 정말 어려운 것이라는 것을 느끼게 되었다. 그만큼 노력이 필요한 분야고 공부를 많이 해야 겠다는 생각을 하게 되었다.
⠀
⠀
⠀
알고리즘 무료 문제 사이트
1. 프로그래머스(https://programmers.co.kr/)
안녕하세요 잘 봤습니다
스파르타코딩애서 들으신 수업 어떠셨나요??!