자료 구조16 [백준 01321] 군인 [Java] 문제 캠프 내내 그랬듯이, 여전히 옆 나라와의 전쟁이 한창이다. 전쟁에는 N개의 부대가 투입되었는데, 전쟁이 장기전이 되다 보니 군사의 적절한 배치를 위해 각 부대에 군인이 늘어나기도 하고 줄어들기도 하고 있다. 행정의 편의를 위해 각 군인들에겐 번호가 붙어 있는데, 군인들은 1번 부대부터 군번순서대로 차례차례 배치된다. 예를 들어 1번 부대에 4명, 2번 부대에 3명, 3번 부대에 7명의 군인이 있다면 군번이 6번인 군인은 2번 부대에 배치되게 된다. 문제는 어떤 부대의 인원이 늘어나거나 줄어들었을 때 i번 군인이 어디에 배치되는지 인데, 이럴 때에는 군인도 군번도 처음부터 다시 배치하게 된다. 위의 예에서와 같이 1번 부대에 4명, 2번 부대에 3명, 3번 부대에 7명의 군인이 있었는데, 1번 부대에.. 2023. 11. 8. [백준 15678] 연세워터파크 [C++] 풀이 정수 K가 적혀있는 N개의 징검다리에 대해 징검다리를 건너며 얻을 수 있는 최대값을 구하는 문제다. 문제에서 주어진 조건 중 아래와 같은 조건이 있다. N개의 모든 징검다리에 순서대로 1 ~ N의 번호를 붙인다. U번 징검다리에서 V번 징검다리로 점프하기 위해서는, U와 V의 차이가 미리 정해진 값 D 이하여야 한다. 어떤 징검다리도 두 번 이상(한 번을 넘게) 밟을 수는 없다. 때문에, 징검다리의 양 끝이 아닌 중간에서 시작하더라도 왼쪽 또는 오른쪽 방향으로만 진행할 수 있다. 서로 다른 방향이더라도 결국 반대 방향의 부분집합에 속하는 영역이기 때문에 징검다리를 한 방향으로 진행한다고 가정하고 dp로 풀이할 수 있다. 진행 방향은 1번부터 N번이며 D씩 이동한다면 모든 징검다리가 탐색 대상이다. .. 2023. 9. 30. [백준 2104] 부분배열 고르기 [C++] 풀이 일반적으로 범위가 넓을수록 최솟값과의 곱으로 인해 점수가 작을것이다. 때문에, 최솟값을 기준으로 나눈 영역(최솟값을 제외한 나머지 영역)에 대해 점수를 구할 때 높은 점수를 기대할 수 있다. 그러기 위해서는 먼저, 구간별로 가지는 합과, 최솟값을 구해야 한다. leaf를 입력받은 후 초기화를 진행해주자. pair에 합과, 최솟값을 가지는 요소의 index를 넣어줬다. 위에서 언급했듯, 최솟값을 기준으로 나눈 영역의 범위를 설정하기 위해서 value가 아닌 index를 넣어줬다. 구간별로 점수를 계산하기 위해 query를 작성해주었다. 주어진 구간에 대한 합과 최솟값의 index로 이루어진 pair를 반환한다. 초기화 단계에서는 올바르지 않은 요소를 접근하지 않는다. 하지만 위의 query는 올바르지.. 2023. 8. 7. [백준 1939] 중량제한 [Java] 풀이 출발지(from)와 목적지(to)에 대해 연결된 다리 중 최대중량을 구하는 문제다. 입력받은 다리의 중량제한에 대해 내림차순 정렬 후 순서대로 union시키며, from과 to가 동일한 집합에 속하는지(연결됬는지) 확인해주어 연결된 순간 union한 간선의 가중치가 최대 가중치이므로 출력하면 된다. 소스코드 소스코드 보기 출처 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 2023. 7. 9. [백준 10775] 공항 [Java] 풀이 Greedy 순서대로 들어오는 비행기에 대해 최대한 많은 비행기를 매칭시켜야 한다. 만약 순서대로 들어오는 비행기 중 한대가 매칭이 불가능 하다면 공항이 폐쇄되기 때문에 탐색을 중단해야 한다. 그렇다면, 비행기를 최대로 매칭시키는 방법은 뭘까? 비행기는 1 ~ g 번째 게이트 중 어디든지 도킹하면 된다. 하지만, 최대한 많은 비행기를 도킹하기 위해서는 g번 게이트에 가깝게 비행기를 도킹함으로써 다른 비행기가 확률적으로 도킹을 하게될 낮은 번호를 피하는 방법이다. 위의 그림을 보면 모든 비행기가 1 ~ gi번 게이트라는 선택지가 주어졌기에 최대한 높은번호를 선택해야 많은 비행기가 도킹 가능하다. 그렇다면 어떻게 최대한 높은 번호의 게이트를 찾을까? 단순한 방법으로 gi부터 1번 게이트까지 이미 도킹중.. 2023. 7. 4. [백준 20040] 사이클 게임 [Java] 풀이 n개의 점에 대해 주어지는 m개의 선분이 사이클을 이루는지 확인하는 문제다. 쉽게 두 원소 x, y에 대해 union할 때 대표 원소가 동일하다면, 선형 구조상 동일한 집합에 속한 원소들이고 한 번 더 연결하려 시도했기 때문에 사이클을 형성할 것이다. 만약 union이 모두 정상적으로 이루어졌다면, 동일한 집합에 속한 원소들끼리 union이 이루어지지 않았기에 사이클은 생길 수 없다. 사이클이 생기지 않은 경우에는 0을 출력하면 된다. 소스코드 소스코드 보기 출처 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmic.. 2023. 7. 2. 이전 1 2 3 다음
