알고보면 알기쉬운 알고리즘 - 5주차 개발일지(라인, 카카오, 삼성 코딩테스)

GD프로젝트 알고리즘 수업 마지막 주 차가 시작되었다.

그럼 마지막주 차에는 라인, 카카오, 삼성 코딩 테스트 위주로 공부하게 되었는데 이에 대해 설명하겠다.

 

 

목차

1. 2019년 상반기 LINE 인턴 채용 코딩테스트

2. 2020 카카오 신입 개발자 블라인드 채용 1차 코딩 테스트

3. 삼성 역량 테스트

 

 

---

1. 2019년 상반기 LINE 인턴 채용 코딩 테스트

---

문제

Q. 연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다. 이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나는데 걸리는 최소 시간을 구하시오.

조건은 다음과 같다. 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다.

브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다. 코니와 브라운의 위치 p는 조건 0 <= x <= 200,000을 만족한다. 브라운은 범위를 벗어나는 위치로는 이동할 수 없고, 코니가 범위를 벗어나면 게임이 끝난다

 

사용해야 할 개념 : 큐, BFS, DP

 

게임이 끝나는데 걸리는 최소 시간을 구하시오 -> 코니와 브라운이 k초 후에 갈 수 있는 모든 경우의 수 중 가장 짧은 시간을 구해야 한다 -> 모든 경우의 수를 생각해야 한다 -> BFS

 

그렇다면 코니와 브라운이 k초 후에 갈 수 있는 경우의 수는 어떻게 구하냐면

 

 

 

처음 큐에 코니의 처음 위치인 C를 집어넣는다

 

 그 후 dnqueue 해서 C의 값을 가져오고 그 값에 +1, +3, +6 한 값을 enqueue 한다. 

 

 

 

 한 번 더 반복하면 c+1, c+3, c+ 6을 dequeue 하고 각각 +1, +3, +6한 값이 enqueue가 된다. 이러면 모든 경우의 수를 생각할 수 있다. 브라운의 위치 또한 이와 같다.

 

즉 큐에 enqueue를 할 때마다 카운트시켜서 코니와 브라운이 간 거리가 같을 때 그 카운트 값이 최단 시간인 것이다.

 

그런데 여기 입력 조건을 보면 0 <= x <= 200000 이다.

큐 안에 들어가 있는 수가 200000이 될 때까지 한 번 연산할 때마다 3배가 늘어나는 데이터를 모두 연산하려면 시간이 많이 필요해진다. 그러므로 DP를 사용해 어느 시점에 몇 미터를 방문한 것들은 다시 연산하지 않게 무시하기로 하자.

 

from collections import deque
c = 2
b = 17
def catch_me(cony_loc, brown_loc):
    time = 0
    queue = deque()
    queue.append((brown_loc, 0))
    visited = [{} for _ in range(200001)] 
	# [{1:True}, ...] index : 위치 key: 몇 초 value : 방문한 적이 있으면 True
    while cony_loc < 200000:		# 200000을 넘어가면 탈출
        cony_loc += time
        if time in visited[cony_loc]:	# 어느 위치에 time 초에 방문한 적이 있으면 코니가 브라운을 잡은 것이다.
            return time

        for i in range(0, len(queue)):
            current_position, current_time = queue.popleft()
            
            new_position = current_position - 1
            new_time = current_time + 1
            if new_position >= 0 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 new_position < 200001 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 new_position < 200001 and new_time not in visited[new_position]:
                visited[new_position][new_time] = True
                queue.append((new_position, new_time))
                
        time += 1

print(catch_me(c, b))

 

모든 경우의 수를 생각하면 BFS, 입력값의 범위가 많으면 DP를 쓰자

 

 

 

---

2. 2020 카카오 신입 개발자 블라인드 채용 1차 코딩 테스트

---

문제

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	2a2ba3c	7
ababcdcdababcdcd	2ababcdcd	9
abcabcdede	2abcdede	8
abcabcabcabcdededededede	2abcabc2dedede	14
xababcdcdababcdcd	xababcdcdababcdcd(압축되지 않음)	17

 

사용해야 할 개념 : 스택

 

abcabcdede 를 예로 들면 

한 칸씩 쪼개서 압축 시도해야 하고

두 칸씩 쪼개서 압축 시도해야 하고

...

최대 len(abcabcdede) // 2 칸씩 압축시도를 해야한다.

 

주어진 문자열의 길이의 절반 이상으로는 압축될 수 없기 때문이다.

 

 

 

 대략적으로 이러한 시도를 모두 거쳐야 한다고 생각하면 된다.

압축이 될 때마다 그 길이를 저장하여 여태까지 나온 최소 길이랑 비교를 해야 한다.

그러면 저렇게 처음에 쪼개진 문자들이 압축이 가능한지 아닌지는 어떻게 판단할까?

 

방법은 쉽다. 현재 비교하고 있는 문자열과 이전 index에 있는 문자열과 서로 같은지를 보면 된다.

다르면 압축되지 않는 거고 같으면 압축이 되는 것이다. 

또한 이전 값과 같으면 달라지기 이전까지 카운트를 재면 얼마큼 압축될 수 있는지 확인할 수 있다.

 

 

 

input = "abcabcdede"

def string_compression(string):
    n = len(string)
    stack = []
    result = len(string)
    for split_size in range(1, n//2 + 1):
        splited = [	# 문자열을 split_size 단위로 쪼개는 과정
            string[i:i + split_size]for i in range(0,n,split_size)
        ]
        compression_string = ''
        stack.append(splited[0])
        for i in range(1, len(splited)):
            if stack[len(stack) - 1] != splited[i] :	# 이전 값과 다르다면 
                count = '' if len(stack) == 1 else len(stack)	# 이번 처음만 달랐다면 그대로 저장하고 아니라면 stack길이만큼 압축된 것이다.
                compression_string = compression_string + str(count) + str(stack.pop())
                stack.clear()
                stack.append(splited[i])
            else :
                stack.append(splited[i])	# 이전 값과 같다면 스택에 저장

        if len(stack) != 0 :	# 스택에 잔여데이터 처리
            count = '' if len(stack) == 1 else len(stack)
            compression_string = compression_string + str(count) + str(stack.pop())
            stack.clear()

        result = min(result, len(compression_string))	# 이전 최소길이랑 비교하여 다시 업데이트
        print(splited)
        print(compression_string)
        print(result)

    return result

print(string_compression(input))

 

 

 

 

 

 

---

3. 삼성 역량 테스트

---

문제

 스타트 링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있 고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

 이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

 각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때까지이다.

 보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

입력
보드를 나타내는 2차원 배열 game_map이 주어진다. 이때, 보드의 행, 열의 길이는 3 이상 10 이하다.

보드 내에 문자열은 '.', '#', 'O', 'R', 'B'로 이루어져 있다.
'.'은 빈칸을 의미하고,
'#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며,
'O'는 구멍의 위치를 의미한다.
'R'은 빨간 구슬의 위치,
'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력
파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 True, 없으면 False를 반환한다.

 

 

사용해야 할 개념 : 큐, BFS, DP

 

위에 2019 라인 코딩 테스트 문제의 상위 호환이다.

visited가 딕셔너리 구조에서 4차원 배열로 변한다.

visited[ 빨간 공의 y좌표 ][ 빨간공의 x좌표 ][ 파란 공의 y좌표 ][ 파란공의 x좌표 ] = 방문한 적이 있으면 True

 

 

 

 

이런 식으로 빨간 공이 구멍에 빠질 때까지 큐에 반복적으로 넣고 빼주는 것을 순환하면 된다.

또한 게임이 10번 안에 끝나니 4^10 = 1,048,576 개의 큐에 데이터가 넣고 빠진다.

그러므로 성능을 더욱 좋게 하기 위해 같은 시간에 빨간 공과 파란 공이 같은 위치에 방문한 적이 있다면 큐에 넣지 않고 계산에서 제외된다. 

 

또한 여기서 우리는 파란 공과 빨간공이 같은 위치에 존재하는 것을 피해야 한다.

피하는 방법은 간단하다.

파란공과 빨간 공은 같은 시간에 같은 기울기에 의해 같은 방향으로 굴러가게 된다.

그렇다면 두 개의 공이 서로의 진로를 막는 경우는 아예 없고

한쪽의 공이 다른 공에 의해 진로가 막히는 경우밖에 없다.

그렇다면 어떤 위치에 먼저 온 공이 늦게 온 공의 진로를 방해하는 경우밖에 없다.

 

 

 

즉 이것을 코드로 짜려면 빨간 공과 파란 공이 같은 공간에 위치하게 된다면

일단 두 공 모두 벽으로 막힌 곳까지 보낸 다음

늦게 온 공(더 많이 움직인 공)이 가려고 했던 방향 한 칸 뒤쪽으로 가면 된다.

 

from collections import deque

game_map = [
    ["#", "#", "#", "#", "#"],
    ["#", ".", ".", "B", "#"],
    ["#", ".", "#", ".", "#"],
    ["#", "R", "O", ".", "#"],
    ["#", "#", "#", "#", "#"],
]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

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
    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


    queue.append((red_row, red_col, blue_row, blue_col, 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]
            # visited에 있는 거라면 큐에 집어넣지 않는다
            if not visited[next_red_row][next_red_col][next_blue_col][next_blue_row] :
                visited[next_red_row][next_red_col][next_blue_col][next_blue_row] = True
                queue.append((next_red_row, next_red_col, next_blue_row, next_blue_col, b_count + 1))

    return False

print(is_available_to_take_out_only_red_marble(game_map))  # True 를 반환해야 합니다