마이구미의 HelloWorld 마이구미의 HelloWorld

알고리즘 풀이/동적계획법

• 백준 2602번 돌다리 건너기 :: 마이구미

  알고리즘 풀이/동적계획법 2019. 11. 10. 23:18

  이 글은 백준 알고리즘 문제 2063번 "돌다리 건너기" 를 풀이한다. 정올 고등부 문제이자, 동적계획법(DP) 문제이다. 문제 링크 - https://www.acmicpc.net/problem/2602 절대반지를 얻기 위하여 반지원정대가 출발한다. 원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다. 하나는 이고 다른 하나는 이다. 아래 그림 1은 길이가 6인 다리의 한 가지 모습을 보여준다. 그림에서 위의 가로줄은 를 표시하는 것이고, 아래의 가로줄은 를 표시한다. 두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다. 두 다리에 새겨진 각 문자는 {R, I, N, G, S} 중 하나이다. 출발 R I N G S R 도착 G R G G N S 반지원정대가..

  Read More

• 백준 2591번 숫자카드 :: 마이구미

  알고리즘 풀이/동적계획법 2018. 1. 31. 20:50

  이 글은 백준 알고리즘 문제 2591번 "숫자카드" 를 풀이한다.정올 출제 문제로써, 풀이 방법은 동적계획법을 통해 해결한다.문제 링크 - https://www.acmicpc.net/problem/2591 1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다.나중에, 적어 놓은 것에 맞게 다시 카드를 늘어놓으려고 보니, 방법이 여러 가지일 수 있다는 것을 알았다. 예를 들어 27123의 경우 아래와 같이 여섯 가지 다른 방법이 있다.카드의 숫자를 차례로 적어 놓은 것이 주어질 때, 위와 같이 그것을 가지고 거꾸로 카드의 배열을 찾으려고 한다. 가능한 카드의 배열이..

  Read More

• 백준 7570번 줄 세우기 :: 마이구미

  알고리즘 풀이/동적계획법 2017. 12. 24. 18:42

  이 글은 백준 알고리즘 문제 7570번 "줄 세우기" 를 풀이한다.정올 초등부, 중등부에서 출제된 문제이다.동적계획법과 구현을 통한 2가지 풀이를 다뤄본다.문제 링크 - https://www.acmicpc.net/problem/7570 예를 들어, 5명의 어린이들에게 1부터 5까지의 번호가 주어져 있고, 다음과 같은 순서로 줄서 있다고 하자. 5 2 4 1 3위 방법을 이용해서 다음과 같이 번호순서대로 줄을 세울 수 있다. (1) 1번 어린이를 제일 앞으로 보낸다. (5 2 4 1 3 → 1 5 2 4 3)(2) 4번 어린이를 제일 뒤로 보낸다. (1 5 2 4 3 → 1 5 2 3 4)(3) 5번 어린이를 제일 뒤로 보낸다. (1 5 2 3 4 → 1 2 3 4 5)위의 예에서는 세 명의 어린이를 제일..

  Read More

• 백준 2698번 인접한 비트의 개수 :: 마이구미

  알고리즘 풀이/동적계획법 2017. 11. 30. 20:21

  이 글은 백준 알고리즘 문제 2698번 "인접한 비트의 개수" 를 풀이한다.풀이 방법으로는 동적계획법을 이용한다.문제 링크 - https://www.acmicpc.net/problem/2698 0과 1로 이루어진 수열 S가 있다. S의 첫 수는 s1이고, 마지막 수는 sn이다. S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.s1*s2 + s2*s3 + s3*s4 + ... + sn-1 * sn위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.예를 들..

  Read More

• 백준 10844번 쉬운 계단 수 :: 마이구미

  알고리즘 풀이/동적계획법 2017. 11. 27. 20:33

  이 글은 백준 알고리즘 문제 10844번 "쉬운 계단 수" 를 풀이한다.풀이 방법으로는 동적계획법으로 설명한다.문제 링크 - https://www.acmicpc.net/problem/10844 45656이란 수를 보자.이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 인접한 모든 자리수의 차이가 1인 수를 어떻게 찾을까?직접 적어보면 쉽게 점화식을 만들어낼 수 있다. N = 1=> 1, 2, 3, 4, 5, 6 ......N = 2=> 10, 12, 21, 23, 32, 34, 43, 45 ....

  Read More

• 백준 2624번 동전 바꿔주기 :: 마이구미

  알고리즘 풀이/동적계획법 2017. 11. 21. 20:18

  이 글은 백준 알고리즘 문제 2624번 "동전 바꿔주기" 를 풀이한다.풀이 방법으로는 동적계획법을 통해 진행된다.문제 링크 - https://www.acmicpc.net/problem/2624 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.20 = 10×2 20 = 10×1 + 5×2 20 = 10×1 + 5×1 + 1×5 20 = 5×3 + 1×5입력으로 지폐의 금액 T, 동전..

  Read More

• 백준 1520번 내리막 길 :: 마이구미

  알고리즘 풀이/동적계획법 2017. 10. 12. 09:35

  이 글은 백준 알고리즘 문제 1520번 "내리막 길" 을 풀이한다.풀이 방법은 DFS + DP(동적계획법) 을 통해 해결한다.DFS - http://mygumi.tistory.com/1021520번 - https://www.acmicpc.net/problem/1520 단순히 모든 경로를 탐색한다면, 시간 초과를 경험하게 된다.시간을 줄일 수 있는 방법은 다음과 같다.20 지점에 오면 더이상 탐색할 필요가 없이 경로가 존재한다는 것을 찾을 수 있다.존재하는 경로를 활용하는 방법으로써, 동적계획법을 이용할 수 있다. dp[y][x] = (y, x) 지점일 때 존재하는 경로의 갯수 DFS를 완벽히 이해하고 있다면, 쉽게 코드를 이해할 수 있다.* dp배열을 -1로 초기화한 이유는 방문여부를 위함이다. 1234..

  Read More

• 백준 14722번 우유 도시 :: 마이구미

  알고리즘 풀이/동적계획법 2017. 9. 26. 11:24

  이 글은 백준 알고리즘 문제 14722번 "우유 도시" 를 풀이한다.14720번 "우유 축제" 에서 조금 더 심화된 문제라고 볼 수 있다.그렇기에, 동적계획법을 통해 문제를 해결한다.14722번 문제 - https://www.acmicpc.net/problem/1472214720번 풀이 - http://mygumi.tistory.com/223 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다.입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다.딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다.초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다.바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 저번 축제에서 수많은 우유를 마셨지만 ..

  Read More