돌이 코딩하는 방

문제 태그 : https://www.acmicpc.net/problem/1006 앞에서 순서대로 푸는 사람들이 절망할만한 문제이다. 1000~1005 보단 확실히 난이도가 있다. 문제 설명 원형 2열로 배치된 2n 개의 칸을 최소 그룹의 갯수로 묶어야 한다. 그룹에는 조건이 있다. 최대 2개가 같은 그룹일 수 있으며, 배치 상에서 연속된 칸이어야 하고, 두 칸의 값의 합이 m을 넘지 않아야 한다. 2칸이 한 줄이고 n줄이 있다고 생각하면 된다. 문제 풀이 DP를 쓰고 싶은 느낌이 들었다. 어떤 줄까지 다 채우는데 사용된 최소 그룹의 갯수를 이용해 다음 줄까지 채우는데 사용된 최소 그룹의 갯수에 영향을 준다고 생각할 수 있기 때문이다. 하지만 문제가 있다. 어떤 칸을 채울 때에는 이전 칸을 완벽히 채운 상..

너무 잉여롭게 시간을 보내는 것 같아서 사람을 모아서 셋을 돌기로 했다. rkm0959님의 추천해주신 Latin America Regional을 돌게 되었다. 2020/2/5 8:10 ~ 2/6 1:10 (5시간), karuna, youngbear과 함께 했다. 결과는 다음과 같다. 내가 J,L,M 을 풀고, youngbear가 K를 풀었으며, Karuna가 D,E,F,G,I 를 풀었다. 카루나 그는 신인가? 복기 글은 자주 쓸 것 같아서 거창한 풀이와 코드는 생략하고 각 문제별로 문제에 대한 간단한 설명과 풀이에 대한 간단한 설명을 적으려고 한다. B. Build A Perfect House 문제 : N과 점 N개가 주어졌을 때 원점을 중심으로 하고 어떠한 점도 포함하고 있지 않은 최대 정사각형의 크기..

USACO 2018 February Gold 3번이다. BOJ 15747번에 등록되어 있으며 문제는 여기서 볼 수 있다. 문제 설명 문제해석과 이해가 굉장히 어려운 문제다. N이 주어지고 우리는 총 N개를 k개의 그룹으로 나눠야 한다. 이때 나눈 그룹별로 숫자가 0부터 1씩 올라가며 부여된다. 예를 들어 9를 4 3 2로 분할 했다면, (0,1,2,3)(0,1,2)(0,1)이 된다. 이때 분할 후에 매겨진 값으로 만들어진 배열이 주어진 배열과 최소 몇 개가 다른지 n 이하의 모든 k에 대해서 출력해야 한다. 예제를 예시로 들자면 1개의 그룹은 무조건 0,1,2,3,4,5로 1,2 만 같습니다. 2개의 그룹으로 나눌 때는 0,1,2,3 0,1 로 나누어야 다른 원소가 2개로 가장 적습니다. 3개의 그룹으로..

문제 태그 : https://www.acmicpc.net/problem/1520 문제 설명 문제 풀이 (사고의 흐름) (1,1)에서 (n,m)으로 갈 수 있는 경우의 수 찾기. 경우의 수를 찾는 것이고, 어떤 칸까지 갈 수 있는 경우의 수는 그 칸으로 올 수 있는 경우의 수의 합으로 표현된다. 따라서 이 문제는 2차원 DP로 해결 할 수 있다. 2차원 필드에서 진행되는 보통의 간단한 DP 문제 같은 경우에는 오른쪽 혹은 아래로 밖에 움직이지 못한다. 따라서 (i,j)는 (i-1,j)와 (i,j-1)로 표현이 된다. 하지만 이 문제는 그렇지 않다. 어떤 (i,j)의 칸으로 올 수 있는 칸은 주위의 4칸 중 (i,j)보다 숫자가 큰 칸이다. 따라서 (i,j)에 대한 경우의 수를 확실하게 구하기 위해서는 주변..

완벽하다고 이야기하지는 못하겠지만, 거의 DP 원툴로 해온 사람으로서 그래도 나름 좋은 문제들이라고 생각한다. DP에 대한 기본 지식은 이전글에 나름 자세히 나와있다. DP 문제를 공부하는 법은 이 글에 나와있다. 문제 소개는 간단히 하고 스포는 최대한 안하려고 노력했다. 배치는 대충 난이도 순이다. DP를 처음 하신다고요? DP라는 것을 처음 접해보는 사람들을 위한 입문자용 문제 모음 - BOJ 2748 피보나치 수 2 유명하기 때문에 감을 잡기 쉽다. - BOJ 1463 1로 만들기 DP 태그의 첫 문제 - BOJ 9095 123 더하기 123 더하기 시리즈는 많고 대부분 나쁘지 않다! - BOJ 2579 계단 오르기 조금 비 직관적인 형태에서 DP식을 끄집어 내보자! - BOJ 11276 2xn 타..

이번에는 DP(Dynamic Programing)에 대해 말해보려고 한다. 사전적으로 동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 동적 계획법에 대해서는 딱히 내용은 없지만 할 말이 많아서 차근 차근 진행해 보려고 한다. 0. DP란? 위에서 서술한 것 처럼 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 간단하게 예시를 들어보자. 피보나치 수의 100번째 수를 구해야 한다고 해보자. 하지만 P(100)=P(99)+P(98)이기 때문에 우리는 피보나치 수의 100번째 수를 구하는 대신 99번째와 98번째 수를 구하는 것으로 대체할 수 있다. 이런 식으로 더 부분 문제에 대한 답을 구해 놓아 이를 통해 더 큰 문제의 답을 계산 하여 구하는 과정을 반복하여 최종 ..

USACO 2018 US Open Gold 2번이다. BOJ 15758번에 등록되어 있으며 문제는 여기서 볼 수 있다. 문제 설명 첫 줄에 n과 m이 주어진다. n는 소의 숫자이며, m은 세트의 숫자이다. 다음 m개의 줄에 한 세트씩 입력이 들어온다. 한개의 세트에 대한 입력은 k와 k개의 숫자로 구성된다. k개의 숫자는 소들의 순서관계이다. 우리는 위에서부터 최대한 많이 순서를 지켜서 소들을 정렬 시키려고 한다. 순서가 상관없는 소들에 대해서는 숫자가 작은 소를 우선으로 정렬한다. 이때 위에서 부터 지킬 수 있는 조건의 갯수와 그 정렬방법을 출력해야 한다. 문제 풀이 문제를 보자 마자 바로 떠오르는 개념이 있다. "위상정렬". 위에서 부터 최대 몇 개까지의 조건을 지킬 수 있는지를 알 수 있다면 Pri..

Union & Find 란? 유니온 파인드 (Union & Find)는 Disjoint set으로도 불리는 일종의 자료구조이다. 그래프 문제에서도 그래프 문제가 아니어도 자주 등장하여 활용되어지는 친구이다. 보통 각 요소들을 묶어주고, 둘이 같은 그룹에 속해 있는지에 대한 판별등을 해줄 수 있고, 그러한 연산들이 필요할 때 사용되어진다. 기본 로직 소개 Union & Find 는 보통 두 개의 함수로 이루어져있다. 하나는 두 개의 요소를 받아서 두 개의 요소가 포함된 각각의 그룹을 묶어주는 함수이고, 하나는 하나의 요소를 받아서 그 요소의 조상을 알려주는 함수이다. 방금 조상이라는 표현에서 알 수 있듯이 한 그룹내에서 요소를 묶을때 상하관계가 존재하게 되며 한 그룹의 조상은 하나만 존재한다.. 또한 묶을..

문제 태그 : https://www.acmicpc.net/problem/4243 문제 설명 문제 풀이 (사고의 흐름) 일단 DP라는 것을 어느정도 바로 생각할 수 있었다. 직선에서 하는 DP인데 N이 작기 때문에 N^2이라고 생각을 했고, 이러면 보통 DP[i][j]는 i에서 j까지 ~~~ 라고 생각했다. 여기서 우리는 i 부터 j까지 다 들렀다면 당연히 최종위치는 i또는 j라는 것을 알 수 있다. 들르는데 걸리는 시간은 0이기 때문에 중간에 띄고 건널 이유가 아예없다. 그래서 관찰한 사실을 토대로 DP[state][i][j]는 state의 방향에 있으면서 i부터 j까지 들리는데 기다림의 합의 최소라고 생각할 수 있다. 하지만 이러면 문제가 있다. 지금까지 대기시간의 총합이 최소가 되는 경우가 지금까지 ..

이번에는 최소 스패닝 트리 (Minimum Spanning Tree 약칭 MST)에 대해 이야기 해보려고 한다. MST란? 최소 스패닝 트리로 스패닝 트리 중 간선의 가중치의 합이 최소인 트리이다. 그럼 스패닝 트리는 무엇일까? 그래프에 n개의 정점이 있을때 n-1개의 간선으로 모든 점을 이은 트리이다. 사이클이 존재하지 않으며, 임의의 두 정점에 대해서 이동할 수 있는 경로가 유일하다. 다시 말하자면 그래프에서 n-1개의 간선을 뽑아내 사이클이 없는 트리를 완성하고 이때의 간선의 가중치의 합이 최소이면 이를 최소 스패닝 트리, 즉 MST라고 한다. MST를 구하는 방법 그래프에서 MST를 구하는 방법에는 크게 두가지가 있다. 바로 크루스칼 알고리즘과 프림 알고리즘이다. 둘 다 그리디를 기반으로 하고 있..