DEVLOG DEVLOG

동적 계획법이란? 하나의 큰 문제를 여러개의 작은 단위의 문제로 나누고 작은 단위의 문제를 먼저 해결 후 결과를 저장한 뒤 더 큰 단위의 문제를 해결할 때 재활용하여 사용됩니다. 동적 계획법은 재귀 함수와 동작 방식이 유사합니다. 하지만 재귀 함수는 작은 단위의 문제 해결이 여러번 반복 될 수 있는 구조입니다. 대표적인 예시인 피보나치 수열로 보면 점화식은 f(n) = f(n - 1) + f(n-2) 이지만 f(n - 1), f(n-2)에서 각 함수를 한번씩 더 호출하면 동일한 값을 2번씩 구하게 되고 그로인해 피보나치 수를 구하기 위한 함수의 호출 횟수는 기하급수 적으로 증가하게 되고 시간 복잡도는 O(n^2)가 됩니다. 동적 계획법을 사용하게 된다면 작은 단위의 문제를 저장하게 되어 중복된 계산을 방..

이진 탐색이란? 이진 탐색은 정렬된 리스트에서 검색 범위를 절반씩 줄여 나가며 검색 데이터를 탐색하는 알고리즘입니다. 정렬된 리스트에서만 사용할 수 있다는 단점이 있지만 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는 방식으로 동작합니다. 배열의 중간 데이터를 비교 중간 데이터와 검색 데이터를 비교 중간 데이터가 검색 데이터와 같다면 종료 중간 데이터보다 검색 데이터가 크다면 중간 데이터 기준 배열의 오른쪽 구간을 대상으로 탐색 중간 데이터보다 검색 데이터가 작다면 중간 데이터 기준 배열의 왼쪽 구간을 대상으로 탐색 데이터를 찾을 때까지 2번 작업을 반복 예제 key = 23 ..

누적합 알고리즘은 배열의 각 원소에 대한 누적된 합을 구하는 알고리즘입니다. 누적합 알고리즘을 사용하면 배열의 부분합을 낮은 시간복잡도로 효율적으로 구할 수 있고 구간 합을 여러번 계산할 때 주로 사용됩니다. 1차원 누적합 arr = [a1, a2, a3, a4] 을 누적합 배열로 계산하게 되면 다음과 같이 계산됩니다. accumulated_sum = [a1, a1 + a2, a1 + a2 + a3, a1 + a2 + a3 + a4] 특정 배열 구간(i, j)의 합은 accumulated_sum[j] - accumulated_sum[i - 1]로 표현할 수 있습니다. public int[] accumulate(int[] arr) { int n = arr.length; int[] accumulatedSum..

문제 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요. 3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다. 5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고..

문제 설명 자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다. x에 n을 더합니다 x에 2를 곱합니다. x에 3을 곱합니다. 자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요. 제한사항 1 ≤ x ≤ y ≤ 1,000,000 1 ≤ n

문제 설명 메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다. 지..

문제 설명 호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다. 예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요. 제한사항 1 ≤ book_time의 길이 ≤ 1,000 book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다 [대실 시작 시각, 대실 종료 시각] 형태입니다. 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다. 예약 시각이 자정을 넘어가는 경우는 없습니..

문제 설명 리코쳇 로봇이라는 보드게임이 있습니다. 이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다. 이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다. 다음은 보드게임판을 나타낸 예시입니다. ...D..R .D.G... ....D.D D....D. ..D.... 여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다. 위 예시에서는 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 7번 만에 "G" 위치에 ..