0과 1의 쉼터

[백준 03584] 가장 가까운 공통 조상 [Java]

문제https://www.acmicpc.net/problem/3584풀이문제에서 주어지는 간선이 부모-자식 관계를 나타내고 있기 때문에 별도의 알고리즘 없이 dfs으로 선형탐색하면 된다. 우선 정점 u에 대해 루트 노드까지 탐색하며 방문 표시를 해주자.정점 v에 대해 루트 노드까지 방문하지 않은 노드까지 탐색하면 된다.소스코드보기

LCA, (Lowest Common Ancestor, 최소 공통 조상)

트리에서 두 노드 u, v의 가장 가까운 공통 조상을 찾는 알고리즘💡공통 조상이란?두 노드가 공통으로 공유하는 조상 노드의 집합= 루트 노트에서 두 노드로 가는 경로가 만나는 노드의 집합 트리에서 LCA를 찾아보자! 1 / \ 2 3 / \ \ 4 5 6 / \ 8 92, 3의 LCA : 18, 5의 LCA : 24, 8의 LCA : 4🔄 동작 원리LCA를 찾는 일반적인 방법은 다음과 같습니다.깊이 맞추기 두 노드의 깊이가 다를 경우, 깊이가 더 깊은 노드를 조상 방향으로 올려 깊이를 맞춥니다.공통 조상 찾기 두 노드가 같아질 때 까지 두 부모를 따라 올라가며 비교합니다.최종 공통 조상 반환 가장 먼저 발견된 공통 조상을 반환합니다...

문제https://www.acmicpc.net/problem/1006풀이아마 문제 번호가 1006이거나, 알고리즘 분류에 DP밖에 없어서 많은 분들을 낚은(?) 문제입니다.평소 DP를 패턴을 찾아 푸시는 분들이라면 많이 어려울 수 있을 것 같습니다.우선, 특수소대가 구역을 침투하는 방법은 단순합니다.현재 영역과 인접한 영역의 합이 W보다 작다면 둘 다 점령 아니면 현재 영역만 점령하는 방식입니다. 이 문제는 다음과 같이 나눌 수 있습니다.선형 구조를 점령하기 위해 침투 시켜야 할 특구 소대의 최소 수 구하기원형 구조임을 고려해 초기값을 설정하고 다시 선형 구조를 점령하기주어진 영역을 원이 아닌 선형 구조로 표현하고,점령하는 경우의 수는 다음과 같이 3개의 상태로 표현할 수 있습니다.점화식에 대해서는 다음..

문제https://www.acmicpc.net/problem/3653풀이위에서부터 아래 방향으로 영화 1 ~ N이 쌓여있을 때, M번의 쿼리에 대해 영화를 뺀다.이 때, 제거한 영화 위로 쌓여있는 영화의 수를 출력해야 한다.제거한 영화는 다시 맨 위에 쌓는다.만약 제거한 영화가 맨 위에 놓인 영화라면 당연히 쌓여있는 영화의 수는 0이다.영화의 위치가 매번 달라지므로 영화의 수, 즉 부분합을 계속 세어야 한다. M은 최대 100,000이므로 세그먼트 트리를 사용했다.리프 노드가 N개인 세그먼트 트리에 대해 i번 영화를 제거했다면, 1 ~ i - 1번 영화에 대한 누적합을 전부 갱신해야 한다.세그먼트 트리를 사용하는 의미가 없다.따라서, 리프 노드가 M + N개인 세그먼트 트리로 확장해 해결했다. i번 영화..

문제https://www.acmicpc.net/problem/2533풀이우선, 주어지는 루트가 없으며, 어디서 탐색해도 상관없다.그래프를 구성 후 dfs를 진행하자. 얼리 어답터의 수가 최소가 되도록 만드는 방법에 대해 알아보자.맨 처음 리프노드는 자기 자신이 얼리 어답터라고 가정해야 한다.하지만, 부모 노드가 존재한다면 리프 노드는 얼리 어답터가 아닌 상태가 정답이다.여기서 dp는 두 상태(EARAY, GENERAL)에 대해 고려해야 한다.dp[i][j] : 상태가 i일때 j ~ N에 필요한 최소 얼리 어답터의 수dfs를 통해 방문을 진행하면 방문 표시와 함께 현재 정점이 얼리 어답터인 경우를 세주자.리프 노드까지 도달 후 리프 노드들이 얼리 어답터라고 표시된 후 부모 노드로 돌아와서 부모 노드의 두 ..

문제https://www.acmicpc.net/problem/11966 풀이입력받은 N이 2의 제곱수인지 확인하는 문제다.N을 2로 나누었을때의 나머지가 1이면 2의 제곱수가 될 수 없다. 이 과정을 반복해주자만약 N이 2의 제곱수가 아니라면 N은 1이 될 수 없다. 이 점을 이용해 결과를 출력하면 된다.소스코드보기

문제https://www.acmicpc.net/problem/11437풀이DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.이를 위해서 양방향 그래프를 구성해야 합니다.문제에서 트리의 루트는 1번이라 언급되어 있으니, 1번 정점부터DFS를 통해 모든 노드의 부모 노드와, 깊이를 구해주면 된다.이제 LCA를 구해야 하는 두 노드 u, v에 대해 깊이가 다르다면 부모 노드로 올라가며 깊이를 맞춰주고,깊이가 동일한 두 노드의 부모노드가 같을 때까지, 즉 LCA를 찾아주면 된다.소스코드보기

문제https://www.acmicpc.net/problem/3584풀이주어지는 트리에 대해 두 정점의 공통 조상을 찾는 문제다.이미 부모-자식에 대한 정보가 주어지므로, 입력과 동시에 parent를 바로 구성할 수 있다. 공통 조상을 구해야하는 두 정점 중 한 정점으로부터 루트노드까지 방문해주고,다른 정점도 동일하게 방문하지 않은 부모 노드를 따라 방문하면 된다.이미 방문한 적 있는 부모노드는 공통 조상 노드이므로 탐색을 중단하고 반환해주면 된다.소스코드보기

문제https://www.acmicpc.net/problem/11024풀이주어지는 N개의 배열의 합을 출력하면 되는 문제다.스트림을 사용해 입력받은 배열의 합을 쉽게 구할 수 있다.소스코드보기

문제https://www.acmicpc.net/problem/15688풀이처음 풀어보는 시간 누적 유형의 문제다.문득 궁금한건 TC의 전체 수가 공개되지 않았는데 어떤 기준으로 시간 제한에 걸리지 않게 푸는지 이해하지 못했다.일단은 기존에 작성한 코드를 최대한 효율적으로 변경했다.2025.01.08 - [PS/Baekjoon Online Judge] - [백준 11931] 수 정렬하기 4 [Java] [백준 11931] 수 정렬하기 4 [Java]문제https://www.acmicpc.net/problem/11931풀이N개의 수를 입력받아 내림차순으로 정렬 후 출력하면 된다.우선 입력을 받고,내림차순 정렬 후순회하며 StringJoiner에 담아도 되고, 정규표현식을 사용해 간단kyr-db.tistory..