기록

문제 요약https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=java택배 기사가 집마다 배달할 박스와 수거할 박스를 가지고 있음한 번에 운반 가능한 박스 수는 cap개왕복 이동 시 가장 멀리 가는 위치 기준으로 거리 누적목적: 모든 배달과 수거를 완료하는 최소 이동 거리 계산접근 전략이 문제는 단순히 배열을 순회하며 처리하는 방식으로는 거리 최적화를 구현하기 어렵다. 가장 중요한 포인트는 다음과 같다:❗ 한 번의 이동으로 배달과 수거를 동시에 처리하고, 이동 거리 기준은 가장 멀리 가는 위치여야 한다.이를 위해 다음과 같은 방법으로 접근한다.1. 우선순위 큐(PriorityQueue)를 사용해 먼 위치부터 처리idx가 큰 집..

1. 문제 요약- url : https://school.programmers.co.kr/learn/courses/30/lessons/1835 카카오프렌즈 8명이 단체사진을 찍기 위해 일렬로 서고자 한다. 각 프렌즈는 특정 상대와의 거리에 대해 조건을 제시하며, 모든 조건을 만족하는 줄 세우기 방법의 총 경우의 수를 계산하는 문제이다.조건은 다음과 같은 문자열 형태로 주어진다:N~F=0 → 네오와 프로도의 간격이 0이어야 한다.R~T>2 → 라이언과 튜브의 간격이 2보다 커야 한다.조건은 최대 100개까지 주어질 수 있으며, 줄 세움은 8명의 모든 순열(8!)에 대해 탐색하면서 조건을 만족하는 경우만 카운트해야 한다.2. 풀이 전략이 문제는 총 경우의 수가 8! = 40,320으로 완전 탐색(DFS) 으로..

1. 문제- url : https://school.programmers.co.kr/learn/courses/30/lessons/1832?language=java도시의 도로망은 m × n 크기의 2차원 배열 cityMap으로 주어진다. 각 칸은 다음의 도로 속성을 갖는다.값의미0일반 도로 (회전 및 직진 가능)1통행 금지 (해당 칸은 경로에 포함 불가)2직진 전용 도로 (회전 불가, 이전 방향 유지 필요)출발지는 (0,0)이며 도착지는 (m-1,n-1)이다. 가능한 이동 방향은 오른쪽 또는 아래쪽으로만 제한된다. 이동 가능한 서로 다른 경로의 수를 20170805로 나눈 나머지를 반환해야 한다.2. 해결 전략2.1. 상태 분리도착 방향에 따라 경로 수를 구분하여 저장해야 하므로, 두 개의 DP 배열을 사용..

문제 개요두 도둑 A, B가 팀을 이루어 모든 물건을 훔치고자 한다. 각 도둑은 물건을 훔칠 때마다 각자에 대한 흔적을 남기며, 그 누적 흔적이 한계를 넘으면 경찰에 붙잡힌다. 도둑 A가 남긴 흔적의 누적 개수를 가능한 최소로 만들되, 두 도둑 모두 붙잡히지 않도록 모든 물건을 처리하는 방법을 찾아야 한다.info[i][0]: i번째 물건을 A가 훔칠 때 남는 흔적 수info[i][1]: i번째 물건을 B가 훔칠 때 남는 흔적 수n, m: 각각 A, B가 경찰에 붙잡히는 흔적 개수 기준문제 조건 정리각 물건은 한 번씩, A 또는 B가 반드시 가져가야 한다.info.length ≤ 40으로 분기 수는 최대 2^40 → 완전탐색 불가목표: 조건을 만족하는 모든 할당 중 A의 누적 흔적을 최소화해결 전략: B..

1. 문제 개요url : https://school.programmers.co.kr/learn/courses/30/lessons/72413두 사람(A, B)이 한 출발지점(s)에서 각자의 목적지(a, b)로 이동한다.일부 구간을 함께 이동(합승)하고, 이후 각자 귀가할 수 있다.반드시 합승할 필요는 없으며, 요금의 총합이 가장 적은 경로를 찾아야 한다.입력은 지점 수(n), 출발지점(s), 목적지(a, b), 지점 간 요금 정보(fares)로 구성된다.택시 요금은 양방향 동일하다.2. 풀이 전략이 문제는 단순한 DFS로 풀 경우 시간 초과가 발생할 수 있다. 왜냐하면 경우의 수가 많고, 중복 탐색이 빈번하게 발생하기 때문이다. 대신 가중치가 있는 그래프에서의 최단 거리 문제이므로, 다익스트라(Dijkst..

1. 문제 정의양과 늑대가 각각 배치된 트리 구조 상에서 루트 노드(0)부터 출발하여 특정 조건을 만족하는 경로를 탐색하는 문제이다. 각 노드에는 양 또는 늑대가 한 마리 존재하며, 현재까지 모은 양의 수가 늑대 수보다 많을 경우에만 이동을 계속할 수 있다.목표는 이러한 제약 조건 하에서 이동 가능한 경로를 완전 탐색하여 최대로 확보할 수 있는 양의 수를 계산하는 것이다.info: 각 노드에 존재하는 동물 정보를 나타내며, 0은 양, 1은 늑대를 의미한다.edges: 노드 간의 연결 관계를 정의한 트리 구조이다.url : https://school.programmers.co.kr/learn/courses/30/lessons/92343#2. 해결 전략본 문제는 일반적인 트리 탐색과는 달리 다음과 같은 특수..

1. 개요url : https://school.programmers.co.kr/learn/courses/30/lessons/12923본 문서는 주어진 정수 구간 [begin, end]에 대해 각 위치에 설치될 숫자 블록의 값을 계산하는 알고리즘을 설명한다. 해당 문제는 특정 규칙에 따라 도로 위 위치마다 하나씩 블록을 설치하며, 각 블록에 적히는 숫자는 해당 위치값의 특정 조건을 만족하는 약수에 의해 결정된다.2. 문제 정의도로는 1부터 1,000,000,000까지의 정수 위치로 구성된다.각 위치 n에는 블록 하나가 설치되며, 해당 블록에 적히는 숫자는 다음 규칙에 의해 결정된다:n == 1인 경우, 블록은 설치되지 않으며 숫자 0이 반환된다.n > 1인 경우, n의 자기 자신을 제외한 약수 중에서 가장..

문제 요약url : https://school.programmers.co.kr/learn/courses/30/lessons/250136가로 M, 세로 N의 격자 land가 주어지며, 1은 석유가 있는 칸, 0은 빈 칸이다. 상하좌우로 연결된 1은 하나의 석유 덩어리로 간주한다. 단 하나의 열(column)에만 시추관을 설치할 수 있고, 해당 열과 연결된 석유 덩어리들의 총 크기 합이 최대가 되도록 설치해야 한다.방법 1. Union-Find 방식개요각 칸을 유니온 파인드로 연결하며 석유 덩어리를 그룹핑하고, 각 그룹의 크기를 기록한다. 시추관을 각 열마다 내릴 때 해당 열을 관통하는 덩어리들을 중복 없이 집계해 최대 석유량을 계산한다.import java.util.*;class Solution { ..