2022 KAKAO BLIND RECRUITMENT 사라지는 발판 Lv. 3

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92345

파이썬 소스: https://bit.ly/3watUuE

 

 문제를 읽다가 아래 문장을 만나면… 문제가 더 이해가 안가기 시작합니다.

양 플레이어는 최적의 플레이를 합니다. 즉, 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이합니다. '이길 수 있는 플레이어'는 실수만 하지 않는다면 항상 이기는 플레이어를 의미하며, '질 수밖에 없는 플레이어'는 최선을 다해도 상대가 실수하지 않으면 항상 질 수밖에 없는 플레이어를 의미합니다. 최대한 오래 버틴다는 것은 양 플레이어가 캐릭터를 움직이는 횟수를 최대화한다는 것을 의미합니다.

 이게 무슨 말인지…? 하는 생각이 드는 대요… 이 부분을 좀더 알아보겠습니다.

플레이어는 A, B 두명으로, A가 이기면, B는 지고, B가 이기면 A는 지는 게임입니다.

1. A 가 먼지 이동하고,

2. B 가 이동하고,

3. A 가 이동하고

4. B 가 이동 못해서 패배할 수도 있고,

이런 순서로 계속 서로 누가 먼저 패배하는 조건에 이를 때까지 반복인 것이죠.

4번에서 B 가 이동하지 못해서 패배했다고 가정해 보겠습니다.

그러면 B의 패배를 리턴 할 수 있습니다. 이문제는 이동한 거리를 구하는 문제 임으로, A와 B가 그동안 이동한 거리도 함께 리턴합니다.

그러면 3번 A의 입장에서는 B가 패배를 리턴 했으므로, A의 승리가 됩니다.

2번의 B의 입장에선 A가 승리했으므로 B의 패배가 되구요.

최종적으로 1번 A는 승리하게 됩니다.

 

앞에서는 간략하게 설명하기 위해서, 1, 2, 3, 4각 단계 마다 승리, 패배를 간략하게 설명했는대요, 이제는 실제와 같이 승리, 패배, 이동거리가 여러가지인 경우를 알아 보겠습니다.

이 문제는 A가 이동하고 B가 이동하는 형태 임으로 2개의 재귀함수가 서로를 호출하는 형태입니다. 소스에서는 a_move()함수에서 A가 한칸 이동하고, b_move()함수를 호출하게 되고, 다시 b_move()는 a_move()를 호출하게 됩니다. 이 때, A, B 중에 하나가 패배하게 되면, 패배와, 이동거리의 합을 리턴합니다. 앞에서는 4번의 B는 자신의 패배임으로, 이동거리가 가장 긴 것을 리턴합니다.

3번 a_move()는 최대 4가지 방향으로 이동이 가능합니다. 4가지 방향으로 이동했을 때, 4번의 b_move()함수가 리턴하는 B의 승리, 패배, 이동 거리는 여러가지 경우가 있습니다.

3가지 경우로 모을 수 있는대요, 1. B의 승리만 리턴, 2. B의 패배만 리턴, 3, B의 승리, 패배 모두 리턴 되는 경우입니다.

1. 모두 B의 승리만 리턴한 경우, A는 패배하는 경우 밖에 없습니다.

A의 패배를 리턴하고, 가장 이동거리가 긴 것을 리턴합니다.

2. 모두 B의 패배만 리턴한 경우, A는 승리하는 경우 밖에 없습니다.

A의 승리를 리턴하고, 가장 이동거리가 짧은 것을 리턴합니다.

3. B의 승리, 패배 2가지 리턴되는경우

A의 입장에서는 B의 승리는 모두 무시하고, B의 패배만 확인합니다.

B의 패배 중에서 가장 짧은 것을 골라서, A의 승리와 함께, 가장 짧은 길이를 리턴합니다.

 

이제 문제를 코딩해보겠습니다.

dyx = [[-1, 0], [0, 1], [1, 0], [0, -1]]

가장 먼저 전,후,좌,우로 이동하는 값 dyx부터 코딩합니다.

 

def solution(board: List[List[int]], aloc: List[int], bloc: List[int]) -> int:     answer = a_move(board, aloc[0], aloc[1], 0, bloc[0], bloc[1], 0)     return answer[1]

이동은 항상 A부터 시작 하기 때문에, a_move()함수를 호출 합니다.

a_move() 함수는 A의 승리/패배와 이동거리를 함께 리턴합니다.

이동거리만 리턴하기 때문에 answer[1]을 리턴합니다.

 

def a_move(board: List[List[int]], ay, ax, adepth, by, bx, bdepth):     if board[ay][ax] == 0:         return [False, adepth + bdepth]     loses = [adepth + bdepth]     wins = []     for dy, dx in dyx:         ny, nx = dy + ay, dx + ax         if is_movable(board, ny, nx):             new_board = copy.deepcopy(board)             new_board[ay][ax] = 0             [win, depth] = b_move(new_board, ny, nx, adepth + 1, by, bx, bdepth)             if win:                 loses.append(depth)             else:                 wins.append(depth)     if wins:         wins.sort()         return [True, wins[0]]     loses.sort(reverse=True)     return [False, loses[0]]

A와 B가 같은 위치에 있을 수도 있습니다. 이 때 B가 다른 위치로 이동 했다면, 해당 위치가 0이 되어, A는 이동할 기회도 없이 패배 하게 됩니다.

따라서, 가장 먼저 현재 A의 위치가 0인지부터 확인하고, 패배한 경우에는 False와 A, B이동 거리의 합을 리턴합니다.

 A가 이동할 수 없는 경우에도 A의 패배 이기 때문에, 패배한 경우의 이동거리를 모아두는 리스트 loses 에 현재까지 A,B 이동거리를 초기값으로 넣어 주게 됩니다.

4가지 방향으로 이동을 시도해보고, is_movable()함수로 이동 가능한 위치인지 확인하고 이동하게 됩니다. 여러 방향으로 이동해야 하기 때문에 board를 복사해서, 현재 위치를 0으로 바꾸고, b_move()함수를 호출해서 이제 B가 이동합니다.

함수 b_move()가 리턴해주는 B의 승리/패배 여부에 따라서, B가 승리했다면, A 가 졌으므로, 진경우를 모아두는 loses리스트에 이동거리를 추가합니다. B가 패배 했다면, B가 이겼으므로, 이긴 경우를 모아두는 wins리스트에 이동기를 추가합니다.

A가 승리한 경우가 한 개 이상이라면, A의 승리를 리턴합니다. A의 승리 중에서 가장 짧은 경우를 리턴하기 위해서, wins를 sort()하구요, 가장 짧은 거리인 wins[0]과 함께 A의 승리 True를 리턴합니다.

A의 승리가 없다면, 패배를 리턴합니다. 최대한 이동거리가 긴 것을 선택하기 위해서 reverse=True로 sort()를 하고, False와 함께 loses[0]을 리턴합니다.

 

함수 b_move()도 같은 방식으로 코딩할 수 있으므로 아래 전체 코드를 참고해주세요.

 

궁금한 문제, 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래에 있습니다.

import copy from typing import List dyx = [[-1, 0], [0, 1], [1, 0], [0, -1]] def solution(board: List[List[int]], aloc: List[int], bloc: List[int]) -> int:     answer = a_move(board, aloc[0], aloc[1], 0, bloc[0], bloc[1], 0)     return answer[1] def a_move(board: List[List[int]], ay, ax, adepth, by, bx, bdepth):     if board[ay][ax] == 0:         return [False, adepth + bdepth]     loses = [adepth + bdepth]     wins = []     for dy, dx in dyx:         ny, nx = dy + ay, dx + ax         if is_movable(board, ny, nx):             new_board = copy.deepcopy(board)             new_board[ay][ax] = 0             [win, depth] = b_move(new_board, ny, nx, adepth + 1, by, bx, bdepth)             if win:                 loses.append(depth)             else:                 wins.append(depth)     if wins:         wins.sort()         return [True, wins[0]]     loses.sort(reverse=True)     return [False, loses[0]] def b_move(board: List[List[int]], ay, ax, adepth, by, bx, bdepth):     if board[by][bx] == 0:         return [False, adepth + bdepth]     loses = [adepth + bdepth]     wins = []     for dy, dx in dyx:         ny, nx = dy + by, dx + bx         if is_movable(board, ny, nx):             new_board = copy.deepcopy(board)             new_board[by][bx] = 0             [win, depth] = a_move(new_board, ay, ax, adepth, ny, nx, bdepth + 1)             if win:                 loses.append(depth)             else:                 wins.append(depth)     if wins:         wins.sort()         return [True, wins[0]]     loses.sort(reverse=True)     return [False, loses[0]] def is_movable(board, y, x):     if 0 <= y < len(board) and 0 <= x < len(board[0]) and board[y][x] == 1:         return True     return False

 

2022 KAKAO BLIND RECRUITMENT 파괴되지 않은 건물 Lv. 3

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92344

파이썬 소스: https://bit.ly/49Yj8oW

 

이 문제를 풀기 위해서는 누적합 알고리즘을 알아야 합니다. 누적합으로 검색해보면, prefix sum과 cumulative sum에 대한 내용이 같이 나오는대요, 둘 중에, cumulative sum알고리즘으로 풀어야 하는 문제입니다.

하지만, cumulative sum으로 검색하면, 이게 cumulative sum에 대한 내용보다 cumulative distribution function에 대한 내용이 더 많이 나와서, 찾기가 어렵더라구요. 카카오에서 제공하는 풀이를 통해서 cumulative sum에 대한 내용을 미리 공부하고 나서, 문제를 풀어 보시는 것도 추천드립니다.

https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/

 

cumulative sum알고리즘을 사용하지 않고, 문제를 푼다고 가정하면 시간 복잡도가 너무 커서 문제를 풀 수 없습니다.

skill의 길이 250000 = 2.5 * 10 ** 5

board의 가로/세로 길이 = 10 ** 3, 10 ** 3

결과 적으로 O(2.5 * 10 ** 11)이 되어서, 일반적으로 시간내에 풀 수 있는 10 ** 9 보다 매우 큰 수입니다. 여기서 줄일 수 있는 부분은 skill을 사용했을 때, r1, c1 ~ r2, c2 영역을 모두 방문하는 부분입니다.

이제 cumulative sum알고리즘을 알아보겠습니다.

1, 0, 3, 2 <- #1 배열이 있다고 가정합니다.

첫번째 아이템의 값을 0으로 만들이 위해서, 1을 모든 아이템에서 빼기를 합니다.

0, -1, 2, 1 <- #1 배열의 값에서 모두 1을 뺀 상태입니다.

원래 값으로 돌아 가기 위해서, 더 해야 할 값을 아래와 같이 배열을 하나 더 만들어 줍니다.

1, 1, 1, 1 <- #2 배열입니다. 1을 뺀 것을 표시하는 배열 이구요, 원래 배열과 더하면 기존의 #1 배열 값으로 돌아 갈 수 있습니다.

#2 배열을 아래와 같이 변형할 수 있습니다.

1, 0, 0, 0, -1

첫번째 1아이템 1을 오른쪽으로 계속 더해주면, 1, 1, 1, 1, 0 배열로 변환 되구요, 마지막 아이템 0만 제외하면, #2 배열과 동일한 배열입니다.

현재 상태를 다시한번 정리하면 아래와 같습니다.

1, 0, 3, 2 <- #1 배열

0, -1, 2, 1 <- 1 뺀 상태

1, 0, 0, 0, -1 <- #2 배열의 변형

여기서 3번째 아이템 2를 0으로 만들기 위해서 2를 아래와 같이 빼기 합니다.

0, 0, 2, 2

0, -1, 0, -1 <- 1을 빼고, 2를 뺀 상태, #4 배열입니다.

여기서 0, 0, 2, 2 배열을 #2 배열의 변형과 같은 변형을 해보겠습니다.

0, 0, 2, 0, -2 가 되구요, 이 배열을 #3 배열의 변형이라고 부르겠습니다.

#2 배열의 변형과 #3 배열의 변형을 아래와 위에서 아래로 더해줍니다.

1, 0, 0, 0, -1

0, 0, 2, 0, -2

1, 0, 2, 0, -3 <- 더한 결과 배열입니다.

이 배열을 왼쪽부터 오른쪽으로 더해 보겠습니다.

1, 1, 3, 3, 0 이 됩니다. 여기에 #4 배열을 더 하면, #1 배열로 돌아 갈 수 있습니다.

0, -1, 0, -1 <- 1, 2를 빼고 남은 숫자

1, 1, 3, 3, 0

1, 0, 3, 2, 0 <- 마지막 0만 제외하면, 기존 #1 배열과 같아 졌습니다.

 

위의 방법을 사용하면 내구도 증가/감소하는 양만 표시해 두었다가, 증가/감소하는 양을 한번에 계산해서, board 배열과 더하면, 보다 빠르게 계산이 가능합니다.

하지만, 아직 1차원이구요, 2차원 배열에 위의 cumulative sum알고리즘를 적용해 보겠습니다.

더하고자 하는 숫자 n 이 있다고 하고, board가 4 x 4 2차원 배열이라고 가정하고, 목표로 하는 영역은 1,1 부터 3, 3까지입니다.

아래 배열을 #1 배열이라고 부르겠습니다.

0, 0, 0, 0, 0

0, n, 0, 0, -n

0, 0, 0, 0, 0

0, 0, 0, 0, 0

0, -n, 0, 0, n

위의 배열을 왼쪽에서 오른쪽으로 더해주겠습니다.

0, 0, 0, 0, 0

0, n, n, n, 0

0, 0, 0, 0, 0

0, 0, 0, 0, 0

0, -n, -n, -n, 0

위의 배열을 위에서 아래로 더해줍니다.

0, 0, 0, 0, 0

0, n, n, n, 0

0, n, n, n, 0

0, n, n, n, 0

0, 0, 0, 0, 0

 

#1 배열 상태에서 내구도 증가/감소를 연산을 할 수 있습니다.

0, 0에서, 2, 2까지 -m 감소시키겠습니다.

-m, 0, m, 0, 0

0, n, 0, 0, -n

m, 0, -m, 0, 0

0, 0, 0, 0, 0

0, -n, 0, 0, n

위의 2차원 배열을 왼쪽으로 더해주고, 다시 아래쪽으로 더해보면, 2번 내구도 증가/감소한 결과 배열을 얻을 수 있습니다. 이 배열을 board와 더하면, 내구도가 1이상인 건물을 찾을 수 있습니다.

cumulative sum알고리즘을 사용하여 시간 복잡도를 다시 계산해보면 다음과 같습니다.

1. 리스트 skill의 길이: 2.5 * 10 ** 5

2. 매 스킬 마다 + 또는 -가 4번 있습니다.

3. 보드의 크기 보다 1큰: 101 * 101 루프를 돌아서 내구도 증가/감소의 합을 구합니다.

4. 보드 크기만큼 100 * 100 루프를 돌아서, 모든 건물의 내구도를 구합니다.

1번은 시간 복잡도에 포함되구요.

2번은 상수의 곱하기 이기 때문에 시간복잡도에서 제외합니다.

3번은 10 ** 4 이지만, 이미 더 높은 차수인 10 ** 5가 있고, 여기에 더하기 이기 때문에 시간 복잡도 계산에서 제외합니다.

4번은 3번과 같은 이유로 시간 복잡도 계산에서 제외합니다.

2.5 곱하기도 제외하면, cumulative sum알고리즘을 사용했을 때, 이 문제의 시간복잡도는 O(10 ** 5) 에 수렴하게 됩니다.

 

cumulative sum알고리즘에 따라서, 함수 solution()의 인자로 주어지는 board보다 가로, 세로 크기가 1씩 더 큰 2차원 배열이 필요합니다.

sums = [[0 for _ in range(len(board[0]) + 1)] for _ in range(len(board)+1)]

리스트 sums로 0으로 초기화된 2차원 배열을 만들었습니다.

skill에서 주어지는 type에 따라서, 건물의 내구도를 높이거나 낮춥니다.

for type, r1, c1, r2, c2, degree in skill:     r2, c2 = r2 + 1, c2 +1     if type == 1:         sums[r1][c1] -= degree         sums[r1][c2] += degree         sums[r2][c1] += degree         sums[r2][c2] -= degree     else:         sums[r1][c1] += degree         sums[r1][c2] -= degree         sums[r2][c1] -= degree         sums[r2][c2] += degree

r2, c2는 cumulative sum알고리즘을 사용하기 위해서, 1씩 증가된 값을 사용하는 것을 확인해주세요.

변수 type이 1 or 2 인지에 따라서, 건물 내구도를 증가/감소시키는 값을 sums의 4가지 위치에 저장합니다.

cumulative sum알고리즘에 따라서, 리스트 sums에 간략하게 표시된 증가/감소 값을 풀어 볼 차례입니다.

먼저 왼쪽에서 오른쪽 방향으로 증가/감소 값을 풀겠습니다.

for r in range(len(sums)):     for c in range(len(sums[0])-1):         sums[r][c+1] += sums[r][c]

그 다음에는 위에서 아래 방향으로 증가/감소 값을 풀겠습니다.

for c in range(len(sums[0])):     for r in range(len(sums)-1):         sums[r+1][c] += sums[r][c]

이제 모든 증가/감소 값이 리스트 sums에 저장되었습니다.

answer = 0 for r in range(len(board)):     for c in range(len(board[0])):         if board[r][c] + sums[r][c] >= 1:             answer += 1 return answer

위와 같이 board의 값과 sums의 값을 더 하면, 건물의 내구도입니다. 이 값이 1보다 크거나 같은 횟수를 모두 answer에 저장하여, 리턴하면 이문제의 답을 구할 수 있습니다.

 

궁금한 문제, 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래에 있습니다.

from typing import List def solution(board: List[List[int]], skill: List[List[int]]):     sums = [[0 for _ in range(len(board[0]) + 1)] for _ in range(len(board)+1)]     for type, r1, c1, r2, c2, degree in skill:         r2, c2 = r2 + 1, c2 +1         if type == 1:             sums[r1][c1] -= degree             sums[r1][c2] += degree             sums[r2][c1] += degree             sums[r2][c2] -= degree         else:             sums[r1][c1] += degree             sums[r1][c2] -= degree             sums[r2][c1] -= degree             sums[r2][c2] += degree     for r in range(len(sums)):         for c in range(len(sums[0])-1):             sums[r][c+1] += sums[r][c]     for c in range(len(sums[0])):         for r in range(len(sums)-1):             sums[r+1][c] += sums[r][c]     answer = 0     for r in range(len(board)):         for c in range(len(board[0])):             if board[r][c] + sums[r][c] >= 1:                 answer += 1     return answer