본문 바로가기

Hard10

[백준 11438] LCA 2 [Java] 문제https://www.acmicpc.net/problem/11438풀이기존에 선형 탐색으로 O(N)만에 LCA를 구하는 방법으로는 이 문제를 해결할 수 없다.2025.01.15 - [PS/Baekjoon Online Judge] - [백준 11437] LCA [Java] [백준 11437] LCA [Java]문제https://www.acmicpc.net/problem/11437풀이DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.이를 위해서 양방향 그래프를 구성해야 합니다.문제에서 트리의 루트는 1kyr-db.tistory.com각 쿼리에 대해 O(logN)안에 LCA를 찾을 수 있는 방법에 대해 알아보자.깊이가 다른 두 노드의 깊이를 맞추고 LCA를 탐색하는 .. 2025. 1. 26.
[백준 01006] 습격자 초라기 [Java] 문제https://www.acmicpc.net/problem/1006풀이아마 문제 번호가 1006이거나, 알고리즘 분류에 DP밖에 없어서 많은 분들을 낚은(?) 문제입니다.평소 DP를 패턴을 찾아 푸시는 분들이라면 많이 어려울 수 있을 것 같습니다.우선, 특수소대가 구역을 침투하는 방법은 단순합니다.현재 영역과 인접한 영역의 합이 W보다 작다면 둘 다 점령 아니면 현재 영역만 점령하는 방식입니다. 이 문제는 다음과 같이 나눌 수 있습니다.선형 구조를 점령하기 위해 침투 시켜야 할 특구 소대의 최소 수 구하기원형 구조임을 고려해 초기값을 설정하고 다시 선형 구조를 점령하기주어진 영역을 원이 아닌 선형 구조로 표현하고,점령하는 경우의 수는 다음과 같이 3개의 상태로 표현할 수 있습니다.점화식에 대해서는 다음.. 2025. 1. 19.
[백준 03653] 영화 수집 [Java] 문제https://www.acmicpc.net/problem/3653풀이위에서부터 아래 방향으로 영화 1 ~ N이 쌓여있을 때, M번의 쿼리에 대해 영화를 뺀다.이 때, 제거한 영화 위로 쌓여있는 영화의 수를 출력해야 한다.제거한 영화는 다시 맨 위에 쌓는다.만약 제거한 영화가 맨 위에 놓인 영화라면 당연히 쌓여있는 영화의 수는 0이다.영화의 위치가 매번 달라지므로 영화의 수, 즉 부분합을 계속 세어야 한다. M은 최대 100,000이므로 세그먼트 트리를 사용했다.리프 노드가 N개인 세그먼트 트리에 대해 i번 영화를 제거했다면, 1 ~ i - 1번 영화에 대한 누적합을 전부 갱신해야 한다.세그먼트 트리를 사용하는 의미가 없다.따라서, 리프 노드가 M + N개인 세그먼트 트리로 확장해 해결했다. i번 영화.. 2025. 1. 17.
[백준 17071] 숨바꼭질 5 [Java] 문제https://www.acmicpc.net/problem/17071풀이수빈이와 동생이 각각 N, K에서 이동할 때 몇 초 후에 서로 만날 수 있는지 계산하는 문제다.수빈이는 다음과 같이 움직일 수 있다.X - 1X + 12X동생은 다음과 같이 움직일 수 있다.N + KK는 경과 시간이자. 동생이 움직일 수 있는 거리를 의미한다. 풀이에서는 step으로 표현하겠다.만약 N == K인 경우 수빈이와 동생은 제자리에서 만나므로 탐색이 불필요하다. 걸린 시간은 0초다.bfs로 N부터 탐색을 시작하자.큐가 비어있거나, k(동생의 이동 위치)가 500,000이하라면 탐색을 계속해야 하므로 동생의 이동거리부터 계산하며 조건식에 포함시켜주자.본격적으로 풀이를 하기전에 시간복잡도에 대해 생각해보자.수빈이는 X - 1.. 2024. 12. 31.
[백준 01019] 책 페이지 [Java] 문제 지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자. 입력 첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 풀이 1부터 N까지의 수에 대해 0부터9가 몇번 나왔는지 구하는 간단한(?) 문제다. 당연히 모든 수에 대해 등장횟수를 구하면 .. 2024. 4. 9.
[백준 08980] 택배 [Python] 문제 아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다. 각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다. 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다... 2024. 2. 29.

티스토리툴바