GOD동하님의 블로그

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1697&sca=5030 JUNGOL | 순서찾기 > 문제은행 아주 먼 옛날 정올국이라는 국가가 있었다. 한재는 정올국에 대해 연구를 하는 학자인데, 어느날 정올국의 문서로 추측되는 문서가 발견되었다. 한재는 정올국이 사용하던 문자가 현재의 영어와 같다는 사실을 알고 있었으나, 사용되는 알파벳의 순서가 영어와 같이 "abc...z"순이 아니라는 사실을 본 문서를 통해 알게 되었다. 허나 정확한 순서를 알수가 없었고, 이에 대해 정올국에서 사용하던 알파벳의 정확한 순서를 알고자 시도하였지만 목표하던 바에 도달하지 www.jungol.co.kr 전형적인 순서를 찾기 위한 위상정렬 문제이다. 여기서 고민할..

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1361&sca=5040 JUNGOL | 자리 배치 > 문제은행 어떤 극장의 자리는 한 줄로 배치되어 있고 자리번호는 왼쪽부터 1에서 N까지 차례대로 매겨져 있다. 이 N개의 자리 중에서 N-1개의 자리는 지정석으로 모두 판매하고, 어떤 한 자리만 자유석으로 비워둔다. 지정석 표를 산 사람들은 아래 규칙에 따라서만 앉을 수 있다. 규칙) 사람들은 구입한 지정석 표에 적힌 번호의 자리에 앉든지, 그 자리의 바로 왼쪽이나 오른쪽의 인접한 자리에 앉든지, 또는 자유석에 앉을 수 있다. 예를 들어 설명해보자. 4개의 자리가 www.jungol.co.kr 자유석을 기준으로 왼쪽 오른쪽으로 나누는 것이 포인트 ..

https://koitp.org/problem/IOI_1999_FLOWER/read/ Korea Olympiad in Informatics Training Program 문제 꽃집에서는 꽃을 꽃병에 꽂아 진열한다. F개의 서로 다른 꽃이 있고, V개의 꽃병들이 일렬로 있다. 꽃병들은 움직일 수 없고, 왼쪽에서부터 순서대로 1, 2, ..., V번까지 번호가 매겨져있다. 또한, 꽃은 1, 2, ..., F번까지 번호가 매겨져있다. 하나의 꽃병에는 하나의 꽃만 꽂을 수 있는데, 모든 꽃은 자신보다 큰 번호의 꽃보다 왼쪽에 있는 꽃병에 꽂아야 한다. 어떤 꽃을 어떤 꽃병에 꽂느냐에 따라 아름다움의 정도가 다르다. 이 아름다움의 koitp.org 이것도 전형적인 DP 문제.. (전형적인 DP라고 하면 부분문제 ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 오늘은 전형적인 DP 문제를 푼다 사실 조건이 크지 않아 전체 탐색을 해도 상관 없지만 이런 문제로 DP 연습을 하기 딱 좋다..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 오늘도 브루트 뽀쓰 먼저 복잡도를 생각해보자 문제에서 추출한 조건 1. 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다 -> 보드의 최대 칸 수는 N^2 개이다. 2. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것..

RGB 거리 알고리즘 문제 Dynamic Programming을 연습하기에는 아주 전형적인 문제라고 생각한다. 풀이1 : 하향식 DP (Top-Down 재귀) 1. 큰 문제를 작은 문제로 분류 2. 최소 단위의 답을 해결하며 병합 풀이2 : 상향식 DP (Bottom-Up 반복문) 1. 작은 문제를 먼저 해결 2. 먼저 푼 문제의 답을 이용해 큰 문제를 해결 설명 : TODO 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475/** * RGB 거리 (문제번호 : 1149) * * @category Dyna..