0과 1의 쉼터

풀이 대표적인 Disjoin Set 문제이다. 일전에도 기본 Set이 아닌 Disjoin Set을 이용해 문제를 푼 경험이 있다. [백준 1043] 거짓말 [Python] 풀이 N명의 사람이 중복해서 참여할 수 있는 M개의 파티가 주어진다. 이 중 진실을 아는 사람(know_truth)과 같이 파티에 참석한 사람들은(people) 전부 진실을 알기 때문에, 진실을 알게 된 사람들(peop kyr-db.tistory.com 문제에서 주어진 n + 1개의 집합은 Disjoin Set을 이용할 때 기본적으로 자신의 부모는 자신임을 나타내는 과정이다. 때문에 n + 1의 인덱스에 대해 자신의 인덱스로 초기화를 해주면 된다. 그 이후로는 문제에서 주어진대로 집합 a, b에 대해 입력을 받아 공통 부모를 갱신하거나..

풀이 입력받은 N개의 수들에 대해 중복없이 입력 받은대로 수들을 출력해주어야 한다. 이미 입력받은 수인지 확인하는 과정을 단순히 반복문을 돌며 확인한다면 시간초과가 발생한다. 때문에 O(1)만에 이미 입력받은 수 인지 아닌지 여부를 판단해주어야 한다. 입력될 수 있는 수의 범위(2^25 - 1)만큼 배열을 선언해주어 입력 여부를 0과 1로 표현한다면 빠른 시간안에 이미 입력받은 수인지 아닌지 판별이 가능하다. 단, int형 배열을 선언한다면, 메모리 제한에 걸릴 것 이다. 때문에 BitSet을 이용해 수의 범위만큼 배열을 선언해주면서 메모리 제한을 넘지않도록 하자. 입력을 받으며 이미 입력받은 수인지 확인하고, 아니라면 입력받은수로 표시를 하고 결과 버퍼에 저장해주자 java 15는 메모리 제한 예외 대..

풀이 트리로 주어지는 목차의 정보를 글머리 번호 형태로 바꾸면 되는 문제다. 아래 조건에 따라 변환할 수 있다. i 번째 수가 i - 1번째 수보다 작다면, 상위 글머리 번호부터 변환해주어야 한다. i 번째 수가 i - 1번째 수보다 크다면, 글머리 번호 형태에 따라 1로 변해야 한다. i 번째 수가 i - 1번째 수와 동일하다면, 이미 존재하는 목차이므로 i - 1번째 수의 글머리 번호 형태 + 1로 변해야 한다. 먼저 i번째 수가 i - 1번째 수보다 작은 경우다. 상위 글머리 번호부터 변환해주어야 하기에 이전에 기록된 하위 글머리 번호에 대해 누적된 수들을 0으로 초기화 하는 과정이 시간초과의 원인이 되었다. 이번 기회에 알게 된 사실인데, 문제를 틀렸거나 부분점수를 얻은 경우 '내 제출' 란에서 ..

풀이 N개의 집들에 대해 2개의 그룹으로 나누고, M개의 길에 대해, 유지비가 최솟값이 되도록 집들을 연결해주면 된다. 단순하게 접근해보자. Minimum Spanning Tree 문제를 풀이할 때, N개의 정점에 대해서 가중치를 기준으로 미리 정렬된 N - 1개의 간선으로 모든 정점을 연결할 수 있다는 사실을 알고있다. 그렇다면, N개의 집들을 2개의 그룹으로 나누는 가장 단순한 방법은 무엇일까? 바로, N - 2개의 간선만 이용해 N - 1개의 정점을 연결해주면 된다. 가중치에 대해 오름차순으로 정렬하고, 최소 가중치를 우선적으로 연결하는게 이득인점을 이용한 풀이다. 소스코드 소스코드 보기 출처 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,00..

풀이 문제에서 주어진 규칙에 따라 N줄을 내려가면서 최댓값과 최솟값을 구하면 되는 문제다. 주어진 규칙을 살펴보자. 별의 위치에 따라 더하거나 뺄수 있는 칸의 범위가 달라진다. 이번에는 아래 그림을 살벼보자 별이 기준이 아닌, 동그라미를 기준으로 각각 빨,초,파의 선을 그었다. 첫 번째 칸에 위치한 동그라미는 첫 번째와 두 번째의 별에 대해 더하거나 뺄 수 있다는 의미이다. 앞으로 계산해야되는 칸을 각각 max_dp, min_dp에 담아주자. 1번 줄은 그대로 담으면 된다. 2번 줄 부터 N번 줄까지는 위에서 말했듯 동그라미를 기준으로 계산하듯이 계산해주면 된다. 각각 max_dp와 min_dp를 구하는 코드이다. 코드가 너무 길다고 생각된다면 아래처럼 쌍으로 묶어주어 관리해도 된다. dp[0] = [ ..

풀이 가중치가 양수인 간선은 양방향, 음수인 간선은 단방향인 그래프에서 출발 정점에서 도착 정점까지 돌아오는 음수사이클이 존재하는지 확인하면 되는 문제다. 특이한 점이라 하면 출발점이 주어지지 않았고, 그래프 내에 어디든 상관없이 조건에 부합하는 음수 사이클이 존재하는지 여부만 알면 되는 문제다. 때문에 모든 정점을 출발점으로 간주하고 bellman ford를 여러 번 진행해야 한다. 만약 탐색 후 dist가 inf가 아니라면, 이미 탐색을 한 번 완료한 그래프이기에, 탐색이 되지 않은 또 다른 그래프에 대해서만 탐색을 진행해주었다. 좀 더 빠르게 탐색해보자. 어떤 정점을 기준으로 조건에 부합하는 음수 사이클이 존재하는지 모르기 때문에, 어차피 모든 정점에 대한 탐색이 이루어져야 하며 매 탐색마다 시작 ..

풀이 M명에 대해 N권의 책을 최대한 많은 학생에게 주는 문제다. greedy와 bipartite matching 둘다 풀이해보았다. Greddy 최대한 많은 인원에게 주기 위해서는 최대한 균등하게 나누어서 주어야 한다는 사실은 자명하다. 어떤 기준으로 나누어 줄까? 다음의 경우에 대해 생각해보자. (a, b)가 { (1, 4), (1, 5), (1, 2) } 일 때의 경우다. 3명 다 a = 1 동일한 상태이고, b만 다른 경우다. 위에서 순서대로 2, 3, 1번 책을 가져가면 3명 모두 다 책을 가지고 갈 수 있고 (1, 5) 구간에 대해서는 다르게 책을 가지고 가는 방법이 존재할 수 있다. 그 중 중요히 여겨야 할 부분은 바로 a가 동일한 3명에 대해서도 구간(b)이 작은 순서대로 가져가는 방법이 ..

풀이 LIS문제의 원리를 잘 다룬 문제이다. 기존에 O(N^2) 방식으로 LIS를 구할 때, 비연속 LIS 길이를 찾을 수 있었다. [백준 11053] 가장 긴 증가하는 부분 수열 [Python] 풀이 LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다. 즉, 가 kyr-db.tistory.com LDS를 찾을 때도 마찬가지로 같은 방식을 사용했다. [백준 11722] 가장 긴 감소하는 부분 수열 [Python] 풀이 일전에 풀었던 LIS문제에서 사용한 방법을 응용해 풀이할 수 있다. [백준 11053] 가장 긴 증가하는 부분 수열 [Pyt..

풀이 주어진 트리에 대해 트리의 지름을 구하면 되는 문제다. [백준 1967] 트리의 지름 [Python] 에서 더 많은 정점을 입력받는 동일한 문제이지만, 이전 글의 풀이와 동일한 방법으로 문제를 해결할 수 있다. 다른 점이라 하면, 입력이 양방향 그래프로 주어지기 때문에 따로 처리하지 않아도 된다. 소스코드 소스코드 보기 출처 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net

풀이 주어진 트리에 대해 트리의 지름을 구하면 되는 문제다. 트리의 지름이란, 트리에서 임의의 두 정점을 연결하는 간선의 가중치 합이 최대가 되는 값을 의미한다. 즉, 문제에 나온 이미지처럼 임의의 두 정점을 길게 당길 때 가장 큰 원을 만들 수 있는 간선의 합이 트리의 지름을 의미한다. 그렇다면 임의의 두 정점을 연결하는 간선의 가중치 합이 최대가 되는 정점은 어떻게 찾을까? 임의의 두 정점(x, y)과 간선의 가중치의 합이 최대가 되는 정점(v1, v2)의 관계에 있어 다음과 같다. (x, y) 두 정점 모두 (v1, v2)와 일치할 때 : 한 번의 탐색으로 정답을 구할 수 있다. (x, y) 중 하나의 정점(x)만 (v1, v2)의 (v1)과 일치할 때 : 한 번의 탐색으로 (v1)를 구할 수 있다..