문제 설명두 도둑이 경찰에 붙잡히지 않도록 모든 물건을 훔치는 문제입니다. 각 도둑이 물건을 훔칠 때 남기는 흔적이 있으며, 특정 수치 이상이 되면 경찰에 붙잡힙니다. 모든 물건을 가져가면서도 두 도둑이 붙잡히지 않도록 흔적을 최소화하는 것이 목표입니다.제한 사항물건 개수: 최대 40개흔적 개수: 1 이상 3 이하A도둑과 B도둑이 경찰에 붙잡히는 한계: 최대 120해결 방법알고리즘: 우선순위 큐를 활용한 상태 공간 탐색 (BFS 변형)우선순위 큐(Priority Queue) 사용현재까지의 최소 흔적을 기준으로 탐색 순서를 결정흔적이 적은 경로부터 탐색하여 최소값을 찾음방문 여부 확인 (3차원 배열 사용)visit[a][b][i]를 사용해 특정 흔적 상태에서 특정 물건을 고려한 적이 있는지 체크BFS 방식..
문제 설명창고에는 1부터 n까지 번호가 매겨진 택배 상자가 존재하며, 가로로 w개씩 배치한 뒤 지그재그 방식으로 쌓여 있습니다. 특정 상자 num을 꺼내기 위해서는 그 위에 있는 모든 상자를 먼저 꺼내야 합니다. 주어진 n, w, num을 바탕으로 총 몇 개의 상자를 꺼내야 하는지 계산하는 문제입니다.제한 사항1 ≤ n ≤ 10,0001 ≤ w ≤ 1001 ≤ num ≤ n해결 방법알고리즘: 구현창고의 배치를 2차원 배열로 생성합니다.왼쪽에서 오른쪽으로 채운 후, 다음 층은 오른쪽에서 왼쪽으로 채우는 방식으로 반복합니다.찾고자 하는 상자(num)의 위치를 파악합니다.num이 포함된 행과 열의 좌표를 저장합니다.해당 좌표에서 아래쪽으로 몇 개의 상자가 쌓여 있는지 세어 반환합니다.시간 복잡도창고를 구성하는..
문제 설명온라인 게임 운영 시, 동시 접속자 수가 증가함에 따라 추가 서버가 필요하다. 한 대의 서버는 m명의 이용자를 감당할 수 있으며, 추가된 서버는 k시간 동안 유지된다. 주어진 players 배열을 기반으로, 모든 시간대에서 필요한 최소 서버 증설 횟수를 구하는 문제이다.제한 사항players의 길이 = 24 (각 시간대별 이용자 수)0 ≤ players[i] ≤ 1,0001 ≤ m ≤ 1,0001 ≤ k ≤ 24해결 방법알고리즘: 그리디 (탐욕법)curServer: 현재 운영 중인 서버 개수stopServer: 특정 시간에 운영이 종료될 서버를 추적하는 배열각 시간대(i)마다 현재 운영 중인 서버 개수를 갱신현재 서버로 감당할 수 없는 경우 추가 서버 개수 계산 및 증설증설된 서버는 k시간 후에..
문제 설명영우는 1억 x 1억 크기의 억억단을 외우기로 했고, 친구 수연은 이를 활용한 퀴즈를 냈다. 수연은 먼저 특정 수 e를 정하고, e 이하의 여러 개의 s를 제시한다. 각 s에 대해 s 이상 e 이하의 수 중에서 억억단에서 가장 많이 등장한 수를 찾아야 한다. 등장 횟수가 같다면 가장 작은 수를 선택한다.제한 사항1 ≤ e ≤ 5,000,0001 ≤ starts의 길이 ≤ min {e, 100,000}1 ≤ starts의 원소 ≤ estarts에는 중복된 원소가 존재하지 않음해결 방법알고리즘: 에라토스테네스의 체 방식의 약수 개수 계산 + DP 활용약수 개수 계산countArr[i]를 i의 약수 개수로 설정한다.1부터 e까지 모든 숫자 i에 대해 i의 배수들에게 1씩 더해주며 약수 개수를 구한다...
문제 설명자연수 n개로 이루어진 집합 중,모든 원소의 합이 S가 되며각 원소의 곱이 최대가 되는집합을 찾아야 합니다.제한 사항집합을 오름차순으로 정렬해야 하며,존재하지 않는 경우 [-1]을 반환해야 합니다.해결 방법알고리즘: 수학, 그리디최대한 균등한 값으로 분배곱을 최대로 만들려면 각 원소들이 최대한 균등해야 합니다.mid = s / n 을 통해 가능한 최대한 균등한 값을 찾습니다.몫과 나머지 활용mid = Math.floor(s / n) 로 기본 값을 정합니다.sub = s % n 를 계산하여 일부 원소에 +1을 더해줍니다.배열 생성n - sub개의 원소를 mid로 설정sub개의 원소를 mid + 1로 설정이로 인해 자연스럽게 오름차순 정렬이 유지됩니다.시간 복잡도O(n), 배열을 생성하는 과정이 한..
문제 설명주어진 문자열에서 "110"을 제거한 후 원하는 위치에 다시 삽입하여, 사전 순으로 가장 앞서는 문자열을 만들어야 합니다.제한 사항문자열 배열 s의 길이는 최대 1,000,000입니다.각 문자열의 길이는 최대 1,000,000이며, 모든 원소의 길이 합이 1,000,000을 초과하지 않습니다.해결 방법알고리즘: 스택 활용, 문자열 조작문자열을 순회하며 "110"을 찾아 제거하고, 개수를 기록합니다.제거 후 남은 문자열에서 '0'이 등장하는 마지막 위치를 찾습니다.찾은 위치에 "110"을 모두 삽입하여 가장 작은 사전 순 문자열을 만듭니다.각 문자열을 처리한 후 결과를 반환합니다.시간 복잡도각 문자열을 한 번 순회하여 "110"을 제거하는 과정: O(N)문자열을 다시 조합하는 과정: O(N)전체 ..
문제 설명주어진 문자열 s가 대괄호 [], 중괄호 {}, 소괄호 ()로 이루어져 있을 때, 이를 왼쪽으로 x(0 ≤ x 올바른 괄호 문자열은 다음 규칙을 따릅니다.(), [], {}는 올바른 괄호 문자열입니다.올바른 괄호 문자열 A가 있다면, (A), [A], {A} 또한 올바른 괄호 문자열입니다.올바른 괄호 문자열 A와 B가 있다면, AB 또한 올바른 괄호 문자열입니다.제한 사항s의 길이는 1 이상 1,000 이하입니다.해결 방법알고리즘: 스택, 문자열 회전올바른 괄호 문자열 판별스택을 이용하여 괄호가 올바르게 짝을 이루는지 확인합니다.여는 괄호는 스택에 push하고, 닫는 괄호가 나오면 스택의 top과 비교하여 일치하면 pop합니다.모든 문자를 검사한 후 스택이 비어있다면 올바른 괄호 문자열입니다.문..
문제 설명각 정점에 가중치가 부여된 트리가 주어질 때, 다음 연산을 이용하여 모든 정점의 가중치를 0으로 만들고자 합니다.임의의 연결된 두 정점을 선택하여 한쪽의 가중치를 1 증가시키고, 다른 한쪽의 가중치를 1 감소시킵니다.모든 트리가 이 연산을 통해 가중치를 0으로 만들 수 있는 것은 아닙니다. 주어진 트리가 가능 여부를 판별하고, 가능하다면 최소한의 연산 횟수를 구해야 합니다.제한 사항a의 길이는 2 이상 300,000 이하입니다.a[i]의 값은 -1,000,000 이상 1,000,000 이하입니다.edges의 행 개수는 (a의 길이 - 1)이며, 트리의 간선 정보를 나타냅니다.edges는 항상 트리의 형태를 유지합니다.해결 방법알고리즘: 트리 DP, DFS 후위 순회루트 노드 선정리프 노드를 루트..