알고리즘 풀이
-
백준 1107번 리모컨 [브루트 포스] :: 마이구미알고리즘 풀이/브루트 포스 2017. 5. 10. 23:12
이번 글은 백준 알고리즘 문제 1107번 "리모컨" 을 다뤄본다.문제 접근 방법은 브루트 포스. 즉, 노가다로 해결할 수 있다.1107번 리모컨 - https://www.acmicpc.net/problem/1107 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 망가져있는지 주어졌을 때, N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 본인은 처음에 단순히 채널을 한자리씩 분해하여..
-
백준 1339번 단어 수학 :: 마이구미알고리즘 풀이/수학 2017. 5. 5. 18:46
이번 글은 백준 알고리즘 문제 1339번 "단어 수학" 을 다뤄본다.문제의 함정을 이해하면 백트래킹으로 접근해야한다는 것이 보인다.하지만 본인은 수학적으로 접근하여 문제를 해결하였다. 민식이는 수학학원에서 숙제를 받았다. 숙제는 단어 수학이라는 것인데, 0-9까지의 수를 알파벳 하나로 나타낸 것이다. 그렇게 한 후, 문자가 2개 주어졌을 때, 그 두 수의 합을 최대로 만드는 것이다.예를 들어, MCR + ACDEB를 계산한다고 할 때,A = 9, B = 4, C = 8, D = 6, E = 5, R = 3, M = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.알파벳으로 이루어진 수가 N개 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 문제는 위와 같이 간단하다..
-
백준 9047번 6174 [카프리카 수] :: 마이구미알고리즘 풀이/수학 2017. 5. 3. 23:28
이번 글은 백준 알고리즘 문제 9047번 "6174" 를 다뤄본다.문제는 단순히 수학 문제로써, "카프리카 수" 에 관련된 문제가 된다. 9, 45, 55, ( ), 297, 703 에서 ( ) 안에 들어갈 수는? 최근 영재 발굴단 방송에서 문제를 푼 최연소 이태호(10살) 군을 주제로 방영되었다. (답은 99)카프리카 수를 알고 있다면, 쉽게 해결할 수 있는 문제이다. (카프리카 수)보자마자 메모하여 관련 알고리즘 문제를 발견하여 다룰 수 있게 되었다. 9047번 문제는 아래와 같다. 간단한 연산이지만 Kaprekar 는 이 연산이 놀라운 결과를 보여준다는 것을 발견했다. 올해 연도인 2008 로 그 결과를 알아보자. 2008 로 만들 수 있는 가장 큰 수는 8200 이고 가장 작은 수는 0028 이다..
-
백준 14501번 퇴사 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 4. 21. 11:14
이 글은 백준 알고리즘 문제 14501번 "퇴사" 를 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.동적계획법을 통해 문제를 해결할 수 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일Ti3511242Pi1020102015402001일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.또한, N+1일 째에는 ..
-
백준 1038번 감소하는 수 :: 마이구미알고리즘 풀이/브루트 포스 2017. 4. 20. 00:17
이번 글은 백준 알고리즘 1038번 문제 "감소하는 수" 를 다뤄본다.문제는 동적계획법으로 접근해야한다. 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 하지만 본인은 도저히 동적계획법으로는 생각나지 않아, 브루트 포스(노가다)로 풀었다.완전한 노가다는 아니라, 불필요한 과정을 제외시킴으로써, 시간 제한을 피할 수 있었다.테스트케이스가 많은 것도 아니고, 노가다로 풀어도 충분히 시간 제한에 걸리지 않을 거..
-
백준 5567번 결혼식 [그래프] :: 마이구미알고리즘 풀이/그래프 2017. 4. 10. 14:21
이번 글은 백준 알고리즘 5567번 "결혼식" 을 다뤄본다.그래프를 통해 문제를 해결할 수 있다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 문제는 상근이의 친구와 상근이의 친구의 친구를 초대할 수 있다.상근이의 친구상근이의 친구의 친구위의 2가지의 조건에 ..
-
백준 1495번 기타리스트 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 4. 6. 22:30
이번 글은 백준 알고리즘 1495번 "기타리스트" 를 다뤄본다.문제 해결은 동적계획법을 활용할 수 있다. Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작..
-
백준 2096번 내려가기 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 4. 4. 20:25
이번 글은 백준 알고리즘 2096번 문제 "내려가기"를 다뤄본다.이 문제는 동적계획법으로 해결할 수 있다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 문제를 이해하기에는 어렵지 않다.문제에서..