돌이 코딩하는 방

문제 태그 : https://www.acmicpc.net/problem/2162 문제 소개 만나는 선분끼리 싹다 그룹을 만들어서 그룹의 갯수와 최대 그룹의 크기를 출력하는 문제 문제 풀이 선분 교차 알고리즘을 이용해 만나는 선분을 판별하고, union & find를 이용하여 그룹을 만들어 주는 문제. 출력처리는 조상의 번호별로 갯수를 세면 간단하게 할 수 있는 것 같다. 선분교차와 union&find를 모른다면 각각 이글과 이글을 참고하자. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52..

이번 글부터 지금까지 공부한 기하 알고리즘들에 대해서 정리를 하고 넘어가려고 한다. 솔직히 나는 기하를 잘 못한다. 많은 사람들이 기하를 어려워 하지만, 나의 꼼꼼한 코딩을 잘 못한다는 약점이 기하의 어려운 점을 더 부각시킨다. 또한, 기본적으로 기하 알고리즘을 많이 알고 있지도 않다. 그래서 아는 기하 알고리즘들을 한 번 정리하고 넘어가려고 한다. 기하 알고리즘? 기하 문제를 푸는 데 쓰이는 알고리즘 들이다. n차원으로 나아가기도 하지만, 보통 좌표평면 상에서 이루어지며, 점, 선 ,도형들 간의 관계, 상태를 표현하는 알고리즘들이 많다. 기본적으로 수학에서의 기하의 지식이 있으면 전체적으로 도움이 될 수 있다. 기하 구현 모든 기하 문제는 일단 기본적으로 점을 잡고 시작한다. 보통 pair형을 사용하여..

문제 태그 : https://www.acmicpc.net/problem/15647 문제 소개 간선의 가중치가 있는 트리가 주어진다. 1번 노드 부터 N번 노드까지 각 노드에 대해서 다른 모든 노드에서 그 노드까지의 거리의 합을 출력하시오. 문제 풀이 처음에는 하나당 O(logN)에 구하는 방법을 생각했다. HLD나 centriod decomposition을 떠올렸지만, 잘 모르는 쪽이기 때문에 더 이상 풀이를 떠올릴 수 없었다. 분명히 centriod를 활용해 풀 수 있을 것 같긴하다. 그래서 전체를 O(N)으로 구하는 방식으로 바꾸었다. Tree DP를 이용하는 방식이다. F[i] = 내 서브트리의 노드들이 i번 노드까지 오는데 걸리는 거리의 합 cnt[i] = 내 버스트리의 노드 수 dp[i] = 내..

BUSACO 2017 February Contest에 대한 전체 풀이를 작성하려고 한다. Bronze ~Gold 까지는 전부 작성하고 Platinum은 되는대로 추가할 예정이다. 소가 길을 건너는 이유 시리즈 이고, 한글 번역이 되어있으므로 따로 문제 설명은 하지 않으려 한다. 백준에서는 https://www.acmicpc.net/category/396 에서 볼 수 있다. Bronze 1 문제 설명 : https://www.acmicpc.net/problem/14467 문제 풀이 : 배열에 최근 위치를 저장해서 현재 받은 입력이 최근 위치와 달랐는지 판별하고 횟수를 세준다. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace..

이 글은 Segment Tree에 대한 이해가 어느정도 완벽히 되어있다고 가정하고 쓰는 글입니다. Top-Down 방식으로 구현이 되며, Top-Down 세그트리에 대한 이해가 부족하면 이 글을 먼저 읽는 것을 추천합니다. 예제 - 구간 합 구하기 2 링크는 https://www.acmicpc.net/problem/10999 이다. 이번에도 문제에 대해서 이야기 하면서 Lazy Propagation에 대해서 소개해보려고 한다. 이 문제에서 요구하는 사항은 두 가지 이다. 1. 배열 중 구간에 일정 값을 더한다 2. 배열의 구간의 합을 구한다. Segment Tree를 생각해보자. 2번 쿼리는 기존 Segment Tree에 존재하는 기능이다. 하지만 여기서 문제가 되는 것은 1번 쿼리이다. 기존의 방식으로..

문제 태그 : https://www.acmicpc.net/problem/18292 문제 소개 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. 문제 풀이 숫자가 작고 인접한 칸을 고르지 않는다는 조건. Bit를 활용한 DP가 풀이로 바로 떠오른다. 한 줄에 대해서 0~2^m 까지를 고르는 경우를 모두 고려 해주면 된다. 각 숫자별로 켜져 있는 비트가 골라진 칸 이라고 생각하면 된다. dp[i][j][k]= i 번째 줄까지 j 개의 칸을 선택했으며, 마지막 (i번째) 줄 의 선택된 모양이 k일때 최댓값이다. 총 테이블의 크기는 O(NK 2^M)이고, ..

USACO 2017 January Contest에 대한 전체 풀이를 작성하려고 한다. Bronze ~Gold 까지는 전부 작성하고 Platinum은 되는대로 추가할 예정이다. 백준에서는 https://www.acmicpc.net/category/395에서 볼 수 있다. Bronze 1 BOJ 14455 Don't Be Last 문제 설명: 우유를 얻은 소와 양이 여러차례에 걸쳐 주어질 때 마지막에서 두번째로 적은 양의 우유를 얻은 소를 구하시오. 문제 풀이: 구조체등을 이용하여 이름과 우유의 양을 같이 저장하자. 이름에 맞춰 짠 우유의 양을 더해주고, 정렬을 해서 출력하면 된다. 여담: 다른 브론즈 문제보다 오히려 어려웠다. 구현과정에서 고려해야 할 것이 적지 않고 은근히 까다로운 문제. Bronze 2..

한 번 배웠다하면 응용되는 부분도 엄청많고 정말 많은 문제에서 다양하게 사용되는 자료구조인 Segment Tree를 소개하려 한다. 예제 - 구간 합 구하기 1 링크는 https://www.acmicpc.net/problem/2042 다. 평소처럼 Segment Tree란? 으로 시작하지 않고 예제를 가지고 오며 시작한 이유는 간단하다. Segment Tree의 역할, 존재의의, 이점등을 가장 잘 설명할 수 있는 문제이기 때문이다. 워낙 유명한 문제인 만큼 풀린사람 수도 엄청나다는 것을 알 수 있다. Segment Tree를 알면서 이 문제를 모르기는 쉽지 않다. 이 문제에서 요구하는 사항은 두 가지다. 1. 배열의 값을 바꾼다. 2. 구간의 합을 구한다. 시간을 생각하지 않고 가장 쉽게 풀 수 있는 방..

문제 태그 : https://www.acmicpc.net/problem/17955 나한테 잘 맞는 문제였다. 정말 좋은 문제라고 생각한다. 문제 소개 n,m이 주어진다. 이후 1 이상 m 이하의 수 n개가 주어진다. n개의 숫자는 원형으로 이루어져 있다. 이후 2가지 행동을 할 수 있다. 1. 어떤 한 칸을 골라 그 수를 max(원래 숫자, 왼쪽의 숫자, 오른쪽 숫자)로 바꾼다. 2. 어떤 한 칸을 골라 그 수를 min(원래 숫자, 왼쪽의 숫자, 오른쪽 숫자)로 바꾼다. 원형으로 이루어진 n개의 숫자를 모두 (1,2,3,...m)으로 만드는데 필요한 최소 행동의 횟수를 각각 구하시오. 만약 만들 수 없다면 -1을 출력한다. 문제 풀이 스포 주의! Step1. 문제 관찰 문제의 예제를 봄으로써 몇가지 사실..

지난번에 이어서 다시 모여서 셋을 돌기로 하였다. 셋 선정에 관해서는 또 rkm0959님께 신세를 졌고, 추천해 주신 셋 중에 갑자기 lotus가 무조건 매운맛으로 돌자고 하는 바람에 2017-2018 ACM-ICPC NEERC Northern Subregional로 돌게 되었다. solved.ac 기준 4다이아 1루비인 무서운 셋! stonejjun,lotus(easrui),karuna 가 같이 돌게 되었다. 백준에서는 https://www.acmicpc.net/category/detail/1795 에서 볼 수 있다. 결과는 다음과 같다. 솔직히 정말 많이 놀랐다. 이정도 성적이면 이대로 바로 대회를 나가도 꽤나 준수한 성적을 거둘 정도의 상황이 나왔다. 셋을 추천해주신 rkm0959님도 조금 놀라시더..