끄적끄적 코딩
[Javascript] 프로그래머스 - 괄호 회전하기
알고리즘 2025. 2. 6. 23:24

문제 설명주어진 문자열 s가 대괄호 [], 중괄호 {}, 소괄호 ()로 이루어져 있을 때, 이를 왼쪽으로 x(0 ≤ x 올바른 괄호 문자열은 다음 규칙을 따릅니다.(), [], {}는 올바른 괄호 문자열입니다.올바른 괄호 문자열 A가 있다면, (A), [A], {A} 또한 올바른 괄호 문자열입니다.올바른 괄호 문자열 A와 B가 있다면, AB 또한 올바른 괄호 문자열입니다.제한 사항s의 길이는 1 이상 1,000 이하입니다.해결 방법알고리즘: 스택, 문자열 회전올바른 괄호 문자열 판별스택을 이용하여 괄호가 올바르게 짝을 이루는지 확인합니다.여는 괄호는 스택에 push하고, 닫는 괄호가 나오면 스택의 top과 비교하여 일치하면 pop합니다.모든 문자를 검사한 후 스택이 비어있다면 올바른 괄호 문자열입니다.문..

[Javascript] 프로그래머스 - 모두 0으로 만들기
알고리즘 2025. 2. 6. 22:08

문제 설명각 정점에 가중치가 부여된 트리가 주어질 때, 다음 연산을 이용하여 모든 정점의 가중치를 0으로 만들고자 합니다.임의의 연결된 두 정점을 선택하여 한쪽의 가중치를 1 증가시키고, 다른 한쪽의 가중치를 1 감소시킵니다.모든 트리가 이 연산을 통해 가중치를 0으로 만들 수 있는 것은 아닙니다. 주어진 트리가 가능 여부를 판별하고, 가능하다면 최소한의 연산 횟수를 구해야 합니다.제한 사항a의 길이는 2 이상 300,000 이하입니다.a[i]의 값은 -1,000,000 이상 1,000,000 이하입니다.edges의 행 개수는 (a의 길이 - 1)이며, 트리의 간선 정보를 나타냅니다.edges는 항상 트리의 형태를 유지합니다.해결 방법알고리즘: 트리 DP, DFS 후위 순회루트 노드 선정리프 노드를 루트..

[Javascript] 프로그래머스 - 쿼드압축 후 개수 세기
알고리즘 2025. 2. 5. 06:49

문제 설명0과 1로 이루어진 2^n x 2^n 크기의 2차원 정수 배열 arr이 주어집니다. 이 배열을 쿼드 트리와 같은 방식으로 압축하려 합니다.압축 방식은 다음과 같습니다:특정 영역 S를 선택합니다.S 내 모든 값이 같다면, 하나의 값으로 압축합니다.값이 다르면 S를 4개의 균일한 정사각형 영역으로 나누고, 각 영역에 대해 같은 방식으로 압축을 시도합니다.최종적으로 압축이 완료된 후, 배열에 남아있는 0의 개수와 1의 개수를 반환합니다.제한 사항arr의 크기는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태입니다. (예: 1, 2, 4, 8, ..., 1024)arr는 정사각형 배열입니다.arr의 모든 요소는 0 또는 1입니다.해결 방법알고리즘: 분할 정복주어진 배열의 특정 영역 (sy, sx) ..

[Javascript] 프로그래머스 - 시험장 나누기
알고리즘 2025. 2. 5. 01:36

문제 설명각 시험장은 노드로 표현되며, 각 노드에는 응시자 수가 할당됩니다. 이 시험장들은 간선으로 연결된 트리 구조를 이루고 있습니다. 시험장의 트래픽을 안정적으로 관리하기 위해, 시험장 간 연결을 k-1개 끊어 k개의 그룹으로 나누려고 합니다.이때, 가장 큰 그룹의 응시자 수를 최소화하는 것이 목표입니다.제한 사항1 ≤ k ≤ 10,000k ≤ num의 길이 ≤ 10,0001 ≤ num[i] ≤ 10,000links는 num의 길이와 동일하며, 각 노드는 이진 트리 구조를 이룹니다.해결 방법알고리즘: 이진 탐색 + DFS (트리 순회)루트 노드 찾기모든 노드가 한 번씩 등장하는 트리에서, 등장하지 않은 노드를 찾아 루트로 설정합니다.이진 탐색을 활용한 그룹 나누기그룹별 최대 응시자 수를 mid로 설정..

[Javascript] 프로그래머스 - 최적의 행렬 곱셈
알고리즘 2025. 2. 4. 07:08

문제 설명여러 개의 행렬을 곱할 때, 곱셈의 순서에 따라 연산 횟수가 달라질 수 있습니다.주어진 행렬들의 크기를 이용하여 곱셈 연산 횟수가 최소가 되도록 곱하는 경우의 연산 횟수를 구하는 문제입니다.제한 사항행렬의 개수는 3 이상 200 이하입니다.각 행렬의 행과 열 크기는 200 이하입니다.계산할 수 없는 행렬이 입력으로 주어지는 경우는 없습니다.해결 방법알고리즘: 동적 계획법 (Dynamic Programming)dp[i][j]: i번째 행렬부터 j번째 행렬까지 곱할 때 최소 연산 횟수를 저장하는 배열을 사용합니다.dp[i][i] = 0: 자기 자신만 있는 경우 연산이 필요 없으므로 0으로 초기화합니다.dp[i][j]를 계산할 때, 가능한 모든 k에 대해 분할하여 최소 비용을 구합니다.dp[i][j]..

[Javascript] 프로그래머스 - 매출 하락 최소화
알고리즘 2025. 2. 3. 23:12

문제 설명 유통 전문 회사 "카카오상사"는 여러 개의 팀으로 구성된 조직도를 가지고 있으며, 직원들은 팀장과 팀원으로 나뉘어 있습니다. CEO는 항상 팀장이며, 특정 직원은 두 개의 팀에 속할 수도 있습니다. 모든 팀이 최소 1명 이상의 직원을 워크숍에 참석시키면서, 참석하는 직원들의 하루평균 매출액의 합을 최소로 하는 방법을 찾아야 합니다.제한 사항직원 수는 2 이상 300,000 이하입니다.직원의 하루평균 매출액은 0 이상 10,000 이하입니다.조직도는 트리 구조로 주어집니다.해결 방법 알고리즘: 동적 프로그래밍 (트리 DP)트리를 DFS 방식으로 탐색하며 하위 노드부터 최적 값을 계산합니다.각 노드는 참석하는 경우와 참석하지 않는 경우 두 가지 상태를 가집니다.dpOn: 해당 노드가 참석하는 경우..

[Javascript] 프로그래머스 - 푸드 파이트 대회
알고리즘 2025. 2. 3. 08:59

문제 설명푸드 파이트 대회에서는 두 선수가 동일한 양의 음식을 같은 순서로 먹어야 합니다. 칼로리가 낮은 음식부터 배치하며, 물을 중앙에 둡니다. 주어진 음식의 양을 고려하여 대회에 사용 가능한 음식만을 배치하는 문자열을 생성해야 합니다.제한 사항2 ≤ food의 길이 ≤ 91 ≤ food의 각 원소 ≤ 1,000food[i]는 i번 음식의 개수를 나타내며, food[0]은 항상 1(물)입니다.정답의 길이가 3 이상이 되도록 입력이 주어집니다.해결 방법알고리즘: 구현food 배열에서 물(food[0])을 제외한 각 음식의 개수를 확인합니다.각 음식의 개수를 절반(food[i] / 2)만큼 사용하여 문자열을 만듭니다.생성한 문자열을 이어붙이고, 물("0")을 중앙에 배치한 후, 반대 방향의 문자열을 추가합..

[Javascript] 프로그래머스 - 문자열 나누기
알고리즘 2025. 2. 3. 06:10

문제 설명주어진 문자열 s를 특정 규칙에 따라 여러 문자열로 분해하는 문제입니다.문자열을 왼쪽에서 오른쪽으로 순차적으로 탐색하며, 첫 번째로 등장하는 문자를 x로 정합니다. 이후 x와 x가 아닌 문자의 등장 횟수를 각각 세면서, 두 횟수가 같아지는 순간 문자열을 분리합니다.이 과정을 문자열 전체에 대해 반복하여, 최종적으로 분해된 문자열의 개수를 구합니다.제한 사항1 ≤ s의 길이 ≤ 10,000s는 영어 소문자로만 이루어져 있습니다.해결 방법알고리즘: 그리디, 문자열 탐색문자열을 순차적으로 탐색하면서 첫 번째로 등장하는 문자를 기준(x)으로 설정x의 개수와 x가 아닌 문자 개수를 카운트두 개수가 같아질 때 문자열을 분리하고, 새로운 기준 문자를 설정하여 반복시간 복잡도문자열을 한 번 순회하므로 O(N)..

검색 태그