백준
-
백준 2156번 포도주 시식 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 16. 21:00
이번 글은 백준 알고리즘 문제 2156번 "포도주 시식" 을 다뤄본다.일단 문제를 보자. 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 6, 10, 13, 9, 8, 1 주어졌을 때, 6, 10, 9, 8 을 고르면 최대의 양 33이 정답이 된다. 이 문제..
-
백준 1912번 연속합 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 15. 23:50
이번 글은 백준 알고리즘 1912번 문제 "연속합" 을 다뤄본다.일단 문제를 보자.n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.문제는 쉽게 이해할 수 있다.연속되는 수들을 골라 최대의 합이 되는 수를 고르면 된다. 사이트에서 알고리즘 분류를 보면 알다시피 동적계획법으로 풀기를 권장하는 문제이다. 어떻게 점화식을 만들 수 있을까?점화식에 앞서 함정만 파악하면 쉽게 문제를 풀 수 있다. 임의의 수열 7 8 -9 10..
-
백준 1932번 숫자삼각형 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 3. 23:26
이번 글은 백준 알고리즘 문제 1932번 "숫자삼각형" 을 다뤄본다.이 문제의 풀이 방식은 DP(동적계획법)이다.문제를 한번 보자. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5위 그림은 크기가 5인 숫자 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.맨 위층을 0층으로 가정하겠다.1 층 : 7 -> 3 || 7 -> 82 층 : 7 -> 3 -> 8 || 7 -> 3 -> 1 || 7 -> 8 -> 1 || 7 -> 8 -> 0................
-
백준 2688번 줄어들지 않아 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 2. 20:47
이번 글은 백준 알고리즘 2688번 "줄어들지 않아" 문제를 다뤄본다.핵심은 DP라고 불리는 동적계획법이다.일단 문제를 보자. 어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.각 자리 수에 따라 줄어들지 않는 경우의 수를 구하면 된다.간단하게 나타..
-
백준 1377번 버블 소트:: 마이구미알고리즘 풀이/정렬 2016. 12. 28. 22:52
이번 글은 백준 알고리즘 사이트의 1377번 "버블 소트" 를 다뤄본다.정답률은 20% 대로, 200명정도이다.1377번 버블 소트 - https://www.acmicpc.net/problem/1377 이미 문제에서도 버블 소트의 소스를 보여줬다.출력되는 정답이 의미하는 건 버블 정렬이 몇단계를 거쳤는지를 알아내는 것이다.버블 정렬을 잠깐 살펴보자. (기본적으로 버블 정렬을 숙지하고 있다고 가정하겠다.)다음과 같이 주졌다고 하자. (10 4 2 5 9 1)10 4 2 5 9 1 -> 4 10 2 5 9 1 -> 4 2 10 5 9 1 -> 4 2 5 10 9 1 -> 4 2 5 9 10 1 -> 4 2 5 9 1 10위의 경우가 1단계라고 하자.그렇다면 다음이 2단계라고 할 수 있다.4 2 5 9 1 1..
-
백준 1072번 게임 :: 마이구미알고리즘 풀이/이진 탐색 2016. 12. 27. 23:55
이번 글은 백준 알고리즘 1072번 "게임" 문제를 다뤄본다.접근 방식은 이진 탐색으로 해결한다.이진 탐색 - http://mygumi.tistory.com/72문제 링크 - https://www.acmicpc.net/problem/1072 게임 기록은 다음과 같이 생겼다.게임 횟수 : X 이긴 게임 : Y (Z %) Z는 형택이의 승률이다. 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z = 88이다.X와 Y가 주어졌을 때, 형택이가 게임을 몇 판해야 Z가 변하는지 구하는 프로그램을 작성하시오. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.본인이 처음 접근한 방법을 설명해보겠다.일단 승률을 구하는 방법이다.(이긴 게임횟수 / 게임횟수) * 100 이 된다.int로 형변환 시킴으로써 소수..
-
LIS 최장증가수열 알고리즘 :: 마이구미알고리즘 2016. 12. 10. 11:55
이번 글의 주제는 LIS 알고리즘이다. LIS는 Longest Increasing Subsequence 로써 최장증가부분수열이라는 의미이다.시간복잡도 O(n^2)을 다룰 것이고, O(nlogn)의 경우는 링크를 보자. (관련 글) 백준 알고리즘 11053번 11055번을 가지고 진행할 것이다. 최장증가수열은 무엇인지 백준 알고리즘 사이트 문제만 읽어도 알 수 있다. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 위와 같은 경우가 증가 부분 수열이다. 본인은 이번 글에서 이 문제를 가..