기록

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 { ..

문제 개요url : https://school.programmers.co.kr/learn/courses/30/lessons/152995#각 사원은 두 개의 점수 (점수1, 점수2)를 가진다.어떤 사원이 다른 사원보다 두 점수 모두 낮으면 인센티브를 받을 수 없다.살아남은 사원들 중 두 점수의 합으로 석차를 계산한다.동점자는 동석차이며, 동석차 수만큼 다음 석차는 건너뛴다.특정 사원(완호)의 석차를 반환하되, 탈락한 경우 -1을 반환한다.핵심 아이디어: 정렬 기준의 역할이 문제를 O(N log N)으로 효율적으로 해결하려면 두 점수 모두 낮은 사원을 빠르게 걸러내는 방법이 필요하다. 이때 가장 중요한 테크닉이 다음의 정렬 기준이다:Arrays.sort(scores, (a, b) -> { if (b[0..

1. 문제 개요- url : https://school.programmers.co.kr/learn/courses/30/lessons/132266 그래프가 주어졌을 때, 여러 개의 출발지(source) 노드에서 하나의 도착지(destination)까지의 최단 경로를 각각 구해야 하는 상황이 종종 발생한다.2. 비효율적인 접근: 출발지마다 Dijkstra 수행for (int source : sources) { runDijkstra(source, destination);}위 방식은 출발지가 K개일 경우 총 K회의 Dijkstra를 실행하게 된다. 노드 수를 V, 간선 수를 E라고 할 때, 전체 시간 복잡도는 다음과 같다.O(K * (V + E) log V)출발지의 수가 수십 개 이상일 경우, 현실적인 입..