Q1. 2019년 상반기 LINE 인턴 채용 코딩테스트 (BFS - Deque)
Q1. 연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다.
이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다.
게임이 끝나는데 걸리는 최소 시간을 구하시오.
조건은 다음과 같다.
코니는 처음 위치 C에서 1초 후 1만큼 움직이고,
이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다.
즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다.
브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다.
코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다.
브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다
from collections import deque
c = 11
b = 2
def calculate_cony_pos(cony_loc, time):
cony_pos = cony_loc
for t in range(1, time + 1):
cony_pos += t
return cony_pos
def catch_me(cony_loc, brown_loc):
queue = deque()
queue.append((brown_loc, 0))
brown_visited = [set() for _ in range(200001)]
# 큐가 비어있지 않은 동안, 큐에서 요소를 하나 꺼낸다
# 꺼낸 요소: 브라운의 현재 위치와 현재 시간
while queue:
brown_pos, time = queue.popleft()
cony_pos = calculate_cony_pos(cony_loc, time)
if cony_pos > 200000:
return -1
# 브라운이 코니를 잡았는지 먼저 확인한다
# -> 코니를 잡거나, 이미 있는 위치라면
if cony_pos == brown_pos or cony_pos in brown_visited[time]:
return time
# 꺼낸 위치에서 브라운이 다음에 이동할 수 있는 모든 위치를 큐에 추가
for next_brown_pos in (brown_pos - 1, brown_pos + 1, brown_pos * 2):
# 이때, 이미 이전에 같은 시간에 같은 위치를 탐색한 적이 있다면, 그 위치를 다시 탐색할 필요가 없다
if 0<= next_brown_pos <= 200000 and next_brown_pos not in brown_visited[time + 1]:
brown_visited[time + 1].add(next_brown_pos)
queue.append((next_brown_pos, time+1))
return -1
print(catch_me(c, b))
print("정답 = 3 / 현재 풀이 값 = ", catch_me(10,3))
print("정답 = 8 / 현재 풀이 값 = ", catch_me(51,50))
print("정답 = 28 / 현재 풀이 값 = ", catch_me(550,500))Note:
Visited
visited는 시간마다 브라운이 방문할 수 있는 위치를 기록하기 위한 자료구조입니다. 이는 200,001개의 빈 집합으로 구성된 리스트입니다(0부터 200,000까지 위치를 고려하기 위함). 각 집합은 해당 시간에 브라운이 도달할 수 있는 모든 위치를 저장합니다. 이 방식을 사용함으로써, 같은 시간에 브라운이 같은 위치를 두 번 이상 방문하는 것을 방지하여, 중복된 경로의 탐색을 줄이고, 메모리 사용량을 최소화할 수 있습니다.
visited의 저장 방식을 정한 이유는 다음과 같습니다:
중복 탐색 방지: 특정 시간에 이미 방문한 위치에 대한 재방문을 방지하여, 탐색 효율을 높이고, 불필요한 연산을 줄입니다.
메모리 효율성: 모든 가능한 시간과 위치의 조합을 미리 할당하지 않고, 실제로 방문하는 위치만 기록함으로써 메모리 사용을 최적화합니다.
탐색 속도 향상: 특정 시간에 방문 가능한 위치만 빠르게 확인할 수 있어, 브라운의 다음 가능한 이동을 결정하는 데 있어 계산 속도가 향상됩니다.
visited의 구조를 시각화하면 다음과 같은 형태를 가집니다:
visited[0]: 첫 번째 시간에 브라운이 도달할 수 있는 위치들의 집합
visited[1]: 두 번째 시간에 브라운이 도달할 수 있는 위치들의 집합
...
visited[200000]: 200,000번째 시간에 브라운이 도달할 수 있는 위치들의 집합 (실제로 이렇게 많은 시간이 필요한 경우는 없으나, 최대 범위를 고려한 것)
각 시간 단위마다, 브라운이 해당 시간에 도달할 수 있는 위치를 집합에 추가합니다. 이렇게 함으로써, 각 시간마다 브라운이 어떤 위치에 있을 수 있는지 빠르게 파악할 수 있습니다.
현재 상태의 visited를 출력하여, 실제로 어떻게 데이터가 저장되어 있는지 확인해보겠습니다.
위의 출력에서 볼 수 있듯이, visited는 각 시간 단위에 대해 브라운이 도달할 수 있는 위치를 저장하고 있습니다. 출력된 데이터는 다음과 같이 해석할 수 있습니다:
1: 시간 1초 후에 브라운은 위치 1, 3, 4에 도달할 수 있습니다.
2: 시간 2초 후에는 위치 0, 2, 3, 4, 5, 6, 8에 도달할 수 있습니다.
3: 시간 3초 후에는 더 많은 위치, 즉 0부터 10, 12, 16에 도달할 수 있습니다.
이런 식으로 시간이 진행됨에 따라 브라운이 도달할 수 있는 위치의 범위가 넓어집니다.
이러한 방식으로 visited를 관리함으로써, 각 시간 단위마다 브라운의 가능한 모든 위치를 추적할 수 있고, 이를 통해 코니를 잡을 수 있는 최소 시간을 효율적으로 계산할 수 있습니다. visited의 저장 방식은 각 시간마다 브라운이 새로 방문할 수 있는 위치만을 추가하여 중복 방문을 방지하고, 탐색의 효율성을 최대화합니다.
BFS & Queue
여기에서 큐(queue)는 너비 우선 탐색(BFS, Breadth-First Search)을 구현하는 데 사용되며, 이 탐색 방식은 그래프의 각 노드를 너비를 우선으로 탐색하는 방법입니다. 문제의 맥락에서 큐는 브라운이 이동할 수 있는 모든 위치를 시간 순으로 추적하고 처리하기 위해 사용됩니다.
큐는 선입선출(FIFO, First-In-First-Out) 자료 구조입니다. 이는 먼저 들어온 요소가 먼저 나가는 구조를 말합니다. 이 문제에서는 각 단계에서 브라운이 이동할 수 있는 모든 위치와 해당 시간을 큐에 저장하고, 큐에서 하나씩 요소를 꺼내어 그 위치에서 다음 단계로 갈 수 있는 모든 위치를 다시 큐에 추가합니다. 이 과정은 코니를 잡을 수 있는 조건을 만족하거나 모든 가능한 위치를 탐색할 때까지 반복됩니다.
큐의 작동 방식을 구체적으로 살펴보겠습니다:
초기 상태에서 브라운의 시작 위치와 시간 0을 큐에 추가합니다. 이는 탐색을 시작하는 지점입니다.
큐가 비어있지 않은 동안, 큐에서 요소를 하나 꺼냅니다. 꺼낸 요소는 브라운의 현재 위치와 현재 시간을 나타냅니다.
꺼낸 위치에서 브라운이 다음에 이동할 수 있는 모든 위치(즉, 현재 위치 -1, 현재 위치 +1, 현재 위치 *2)를 계산합니다.
각 이동 가능한 위치에 대해, 그 위치가 아직 탐색되지 않았다면(즉, 해당 시간에 방문한 적이 없다면), 그 위치와 다음 시간(현재 시간 +1)을 큐에 추가합니다. 이렇게 함으로써 모든 가능한 이동 경로를 너비 우선으로 탐색합니다.
동시에, 각 단계에서 코니의 위치를 계산하고, 브라운이 코니의 위치에 도달했는지 확인합니다. 만약 브라운이 코니를 잡았다면, 탐색을 종료하고 현재 시간을 결과로 반환합니다.
만약 큐가 비게 되면(즉, 더 이상 탐색할 위치가 없으면) 탐색을 종료합니다. 이 경우, 브라운이 코니를 잡을 수 없는 것으로 간주하고 적절한 값을 반환합니다(예제 코드에서는 -1).
이 방법을 통해, 각 시간 단계에서 브라운이 이동할 수 있는 모든 위치를 체계적으로 탐색하며, 가능한 모든 경로를 고려하여 코니를 잡을 수 있는 최소 시간을 효율적으로 찾아낼 수 있습니다.
next_pos not in visited[time + 1]
next_pos not in visited[time + 1] 부분은 중복 탐색을 방지하고 탐색 과정의 효율성을 높이기 위해 필요합니다. 너비 우선 탐색(BFS)를 수행하면서, 브라운이 다음 시간 단계에 특정 위치에 도달하는 모든 가능한 경로를 탐색합니다. 이때, 이미 이전에 같은 시간에 같은 위치를 탐색한 적이 있다면, 그 위치를 다시 탐색할 필요가 없습니다. 왜냐하면, 한 번 방문한 위치는 같은 시간에 다시 방문했을 때 새로운 정보나 결과를 제공하지 않기 때문입니다.
따라서, next_pos not in visited[time + 1] 조건을 통해 다음과 같은 이점을 얻을 수 있습니다:
중복 제거: 같은 시간에 동일 위치를 여러 번 탐색하는 것을 방지하여, 불필요한 연산을 줄일 수 있습니다. 이는 특히 가능한 이동 경로가 많은 경우에 중복 탐색의 양을 크게 줄여줍니다.
탐색 속도 향상: 중복된 경로를 제외함으로써 탐색해야 할 전체 경로의 수가 줄어들고, 결과적으로 알고리즘의 탐색 속도가 향상됩니다.
메모리 사용 최적화: 이미 방문한 위치를 다시 큐에 추가하지 않음으로써, 큐의 크기와 메모리 사용량을 줄일 수 있습니다. 이는 특히 탐색해야 할 공간이 클 때 중요합니다.
최적의 해 찾기: BFS는 레벨 별로 탐색을 진행하기 때문에, 최초로 코니를 잡는 순간이 발견되면 그 시점이 바로 최소 시간임을 보장합니다. 중복을 제거함으로써 더 빠르게 최적의 해를 찾을 수 있습니다.
이러한 이유로, next_pos not in visited[time + 1] 조건은 BFS를 이용한 문제 해결 방식에서 중요한 역할을 하며, 탐색의 효율성과 정확성을 높이는 데 기여합니다.
Q2. 2020 카카오 신입 개발자 블라인드 채용 1차 코딩테스트 - 1 (문자열 압축)
Q2. 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다.
최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 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이 됩니다.
def string_compression_verbose(string):
n = len(string)
shortest_length = n # Start with the original length as the shortest
# Iterate over possible split sizes
for split_size in range(1, n // 2 + 1):
splited = []
compressed = ""
count = 1
# Alternative: Generate the split segments
# splited = [string[i:i + split_size] for i in range(0, n, split_size)]
for i in range(0, n , split_size):
splited.append(string[i:i + split_size])
# Iterate over the segments to compress
for j in range(1, len(splited)):
if splited[j] == splited[j - 1]:
count += 1
else:
# Add the previous segment and its count to the compressed string
compressed += (str(count) if count > 1 else '') + splited[j - 1]
count = 1 # Reset count for the new segment
# for last segment
compressed += (str(count) if count > 1 else '') + splited[-1]
# Just for demonstration, not updating shortest_length here
shortest_length = min(shortest_length, len(compressed))
return shortest_length # 최솟값 리턴
# Example input for demonstration
input_string = "abcabcabcabcdededededede"
print(string_compression_verbose(input_string))
print("정답 = 3 / 현재 풀이 값 = ", string_compression_verbose("JAAA"))
print("정답 = 9 / 현재 풀이 값 = ", string_compression_verbose("AZAAAZDWAAA"))
print("정답 = 12 / 현재 풀이 값 = ", string_compression_verbose('BBAABAAADABBBD'))Note
splited = [string[i:i + split_size] for i in range(0, n, split_size)]splited = []
for i in range(0, n , split_size):
splited.append(string[i:i + split_size])Q3. 2020 카카오 신입 개발자 블라인드 채용 1차 코딩테스트 - 2
Q3. 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.
수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.
용어의 정의
'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.
그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
예를 들어, "(()))("와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 문자열은 아닙니다.
반면에 "(())()"와 같은 문자열은 균형잡힌 괄호 문자열 이면서 동시에 올바른 괄호 문자열 입니다.
'(' 와 ')' 로만 이루어진 문자열 w가 균형잡힌 괄호 문자열 이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환할 수 있습니다.
- 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
- 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
- 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. - 문자열 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 and stack[-1] == "(":
stack.pop()
return len(stack) == 0
# 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자.열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
# 균형잡힌 괄호 문자열의 조건은 ( 와 )의 개수가 같아야 합니다!
def separate_u_v(w):
queue = deque(w)
left, right = 0, 0
u , v = "", ""
while queue:
char = queue.popleft()
u += char
if char == "(":
left += 1
else:
right += 1
# u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 합니다.
if left == right:
break
v = ''.join(queue)
return u, v
def reverse_parentheses(parentheses_string):
reverse = ""
for s in parentheses_string:
if s == "(":
reverse += ")"
else:
reverse += "("
return reverse
def change_to_correct_parentheses(parentheses_string):
# 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
if len(parentheses_string) == 0:
return ""
u, v = separate_u_v(parentheses_string)
# 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
# → change_to_correct_parentheses 함수로 돌아와서, 조건문과 재귀 함수를 추가합니다.
if is_correct_parentheses(u):
# 3-1. 수행한 결과 문자열을 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) + ")" + reverse_parentheses(u[1:-1])
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)
return
print(get_correct_parentheses(balanced_parentheses_string)) # "()(())()"가 반환 되어야 합니다!
print("정답 = (((()))) / 현재 풀이 값 = ", get_correct_parentheses("(((()))) "))
print("정답 = (((()))) / 현재 풀이 값 = ", get_correct_parentheses(")()()()("))
print("정답 = ()()( / 현재 풀이 값 = ", get_correct_parentheses("))()("))
print("정답 = ((((()())))) / 현재 풀이 값 = ", get_correct_parentheses(')()()()(())('))clear version:
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
def separate_to_u_v(string): # u, v로 분리
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: # 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 합니다. 즉, 여기서 괄 쌍이 더 생기면 안됩니다.
break
v = ''.join(list(queue))
return u, v
def reverse_parentheses(string): # 뒤집기
reversed_string = ""
for char in string:
if char == '(':
reversed_string += ")"
else:
reversed_string += "("
return reversed_string
def change_to_correct_parentheses(string):
if string == '': # 1번
return ''
u, v = separate_to_u_v(string) # 2번
if is_correct_parentheses(u): # 3번
return u + change_to_correct_parentheses(v)
else: # 4번
return '(' + change_to_correct_parentheses(v) + ')' + reverse_parentheses(u[1:-1])
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)
print(get_correct_parentheses(balanced_parentheses_string)) # "()(())()"가 반환 되어야 합니다!
print("정답 = (((()))) / 현재 풀이 값 = ", get_correct_parentheses(")()()()("))
print("정답 = ()()( / 현재 풀이 값 = ", get_correct_parentheses("))()("))
print("정답 = ((((()())))) / 현재 풀이 값 = ", get_correct_parentheses(')()()()(())('))