돌이 코딩하는 방

문제 태그 : 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님도 조금 놀라시더..

문제 태그 : 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 는 보통 두 개의 함수로 이루어져있다. 하나는 두 개의 요소를 받아서 두 개의 요소가 포함된 각각의 그룹을 묶어주는 함수이고, 하나는 하나의 요소를 받아서 그 요소의 조상을 알려주는 함수이다. 방금 조상이라는 표현에서 알 수 있듯이 한 그룹내에서 요소를 묶을때 상하관계가 존재하게 되며 한 그룹의 조상은 하나만 존재한다.. 또한 묶을..