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

알고리즘 풀이

• 백준 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..

  Read More

• 백준 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................

  Read More

• 백준 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자리 수의 개수를 구하는 프로그램을 작성하시오.각 자리 수에 따라 줄어들지 않는 경우의 수를 구하면 된다.간단하게 나타..

  Read More

• 백준 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..

  Read More

• 백준 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로 형변환 시킴으로써 소수..

  Read More

• 백준 1940번 주몽 :: 마이구미

  알고리즘 풀이/수학 2016. 12. 17. 23:22

  이번 글의 주제는 백준 알고리즘 사이트의 문제 "주몽"이라는 문제이다. https://www.acmicpc.net/problem/1940 1차원 배열을 활용하여 푸는 문제이다. 아직 1차원 배열을 응용하는 법이 능숙하지 못하는 분들에게 좋은 풀이라 생각한다. - 재채점으로 실패 문제는 입력되는 번호들 중 2개를 골라 합한 것이 필요한 숫자가 되는 경우의 횟수를 구하는 문제이다. 이 문제의 힌트는 고유한 번호가 주어지는 것이다. 즉, 중복되지 않는 수가 주어진다. 함정은 중복되는 경우를 체크하면 안된다. 예를 들어 필요한 숫자가 3일 때 답은 (1,2) (2,1) 로써 2개가 아닌 (1,2) 1개가 된다. 어떻게 접근할까? 일단 순수한 방법으로 구현을 해보겠다. for (int i=0; i

  Read More

• 백준 10974번 모든 순열 :: 마이구미

  알고리즘 풀이/수학 2016. 10. 25. 22:08

  이 글은 백준 알고리즘 문제 10974번 "모든 순열" 를 풀이한다.perm 알고리즘을 통해 문제를 해결할 수 있다.참고 링크 - https://www.nayuki.io/page/next-lexicographical-permutation-algorithm10974번 - https://www.acmicpc.net/problem/10974 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다. 이번 문제는 테스트 케이스를 보면 1 = array[i]) { i--; } // 마지막 변경이 되었을 때 4321일 경우 i는 위의 접미사 인덱스를 구하는 과정에서 -1이 됨. if (i

  Read More

• 백준 1021번 회전하는 큐 [Queue] :: 마이구미

  알고리즘 풀이/스택, 큐 2016. 10. 19. 20:27

  이번 글은 백준 1021번 회전하는 큐를 다룰 것이다.정답률 33%정도이지만 쉬운 문제이다.1021번 회전하는 큐 - https://www.acmicpc.net/problem/1021Github - https://github.com/hotehrud/acmicpc 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.첫번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.오른쪽으로 한 칸 이동시킨..

  Read More