개발자꿀꿀이

문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 풀이 선형 시간의 LCA 알고리즘을 사용하였다. 해당 LCA까지의 간선 비용을 모두 합한 것이 두 정점 사이의 거리가 된다. 배열은 세개를 선언하였다 parents[] : 해당 정점의 바로 위 조상을 저장 하는 배열 parent_len[] : 해당 정점의 바로 위 조상과의 거리를 저장하는 배열 depth[] : 1번 정점을 제일 큰 조상을 두고 그로 부터의 깊이를 저장하는 배열 거리를 구하는 코드는 아래와 같다. public static int find_Dist(int a, int b) { if(depth[a] < depth[b]) {..

문제 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 풀이 conpulake.tistory.com/60 백준 11438 (LCA 2) - 최소공통조상(HLD 풀이) 문제 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 conpulake.tistory.com 위의 링크에서 HLD 풀이를 했다. 좀 더 직관적이고 보편..

문제 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 풀이 최소 공통 조상(Lowest Common Ancestror)을 찾는 문제다. 방식은 여러가지가 있겠지만 HLD(Heavy-Light Decomposition)의 Heavy-Edge 와 Light-Edge 로 구분한 것을 이용해 트리를 분할하여 푸는 방식을 이용하여 풀었다. Heavy-Edge : 각 정점에서 아래로 뻗어나가는 간선중에서 가장 무거운 간선을 의미한다.( 여기서 무겁다는 것은 자식이 가장 많은 정점으로 이어지는 ..

문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. 풀이 스택과 문자열처리에 관한 문제다. 스택을 직접 사용하지 않고 스택의 자료구조..

문제 문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다. 이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라. 풀이 LCS 의 개념을 미리 앞에서 풀어 봤기 때문에 문제를 이해하는데는 어렵지 않았다. conpulake.tistory.com/55 백준 9252 (LCS 2) 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. ..

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 풀이 이문제를 분류를 두는것이 어려웠다. 동적 계획법(Danamic Programming)을 기반을 한 String 문제이기 때문이다. 하지만 중요한건 문자열 이므로 문자열 카테고리에 넣는다. LCS는 두가지가있다. Longest Common Substring (공통 부분 문자열) Longest Common Subsequence (공통 부분 수열) ACAYKP CAPCAK 이 두개의 문자열에서 Substring -> CA Subsequence -> ACAK 이..

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 풀이 세그먼트트리를 이용한 문제를 이해하는데 오래걸렸다. 1 ~ n 까지중 아직 제거되지 않은 수를 1로 두고 제거된 수를 0으로 둔 뒤 그 수들의 구간합을 세그먼트 트리로 구현한 트리를 이용해 문제를 푼다. 아..

문제 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다. 은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대해서 다음과 같은 과정을 거친다. 서랍 Ai가 비어있다면, i번 술을 그 서랍에 보관한다. 서랍 Bi가 비어있다면, i번 술을 그 서랍에 보관한다. Ai에 들어있는 술을 다른 서랍으로 이동시킨다.(다른 서랍은 Ai에 들어있는 술이 들어갈 수 있는 서랍 중 ..

문제 종빈이는 아주 큰 그룹의 총수다. 이 그룹은 1부터 N번까지의 번호로 구분할 수 있는 N개의 기업을 운영하고 있다. 현재 각 기업은 서로 독립적인 자체 컴퓨팅 및 통신센터를 가지고 있다. 어느 날 종빈이는 계열사의 CTO인 서현이에게 서비스 개선을 위해 각 기업의 서버를 네트워크로 연결하여 단일 통신센터에서 관리 가능한 클러스터 형태로 구성할 것을 제안했다. 종빈이의 제안을 들은 서현이는 다음과 같은 병합 과정을 고안해냈다. 클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다. 클러스터 B를 제공하는 기업 J를 고른다. B는 A가 아닌 임의의 클러스터이며, J는 센터가 아닐 수 있다. I와 J를 통신 라인으로 연결한다. 이때 기업 I와 J를 잇는 라인의 길이는 |I – J|(mod 1000)이..

문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다. 신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가? 풀이 gi의 가장 뒷부분 부터 도킹을 해야 많은 수의 비행기를 도킹 할 수 있기에 gi의 위치에 도킹을 먼저 시도한다. 해당 부분의 gate 배열의 저..