알고리즘 풀이
-
백준 10610번 30 [배수 판정법] :: 마이구미알고리즘 풀이/수학 2017. 2. 13. 16:02
이번 글은 백준 알고리즘 10610번 "30" 을 다뤄본다.이 문제는 배수 판정법을 활용해서 문제를 해결할 수 있다.일단 먼저 문제를 보자. 어느날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. (그 수가 존재한다면) 주어지는 수에 대해 섞은 모든 경우에서 30의 배수가 되는 가장 큰 수를 찾는 문제다.예를 들어보자. 120과 210이 30의 배수이지만 가장 큰 수는 210이기 때문에 정답은 210이다.이 문제를 배수판정법을 통해 해결해보자. 3의 배수 판정법에 의하면, 모든 자리 수의 합이 3..
-
백준 2875번 대회 or 인턴 [Greedy] :: 마이구미알고리즘 풀이/그리디 2017. 2. 11. 17:59
이번 글은 백준 알고리즘 2875번 "대회 or 인턴" 을 다뤄본다.이 문제는 그리디 알고리즘으로 문제를 접근할 수 있다.그리디 알고리즘 - http://mygumi.tistory.com/1212875번 대회 or 인턴 - https://www.acmicpc.net/problem/2875 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다.그런데 올해에는 대회에 참여하려는 학생들 중 K명을 반드시 인턴쉽 프로그램에 참여하라는 학교의 방침이 생기게 되었다.백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것..
-
백준 1946번 신입사원 [Greedy] :: 마이구미알고리즘 풀이/그리디 2017. 2. 8. 21:14
이번 글은 백준 알고리즘 1946번 "신입사원" 을 다뤄본다.문제 해결법은 그리디 알고리즘이다.그리디 알고리즘 - http://mygumi.tistory.com/121 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않..
-
백준 12353번 Baby Height :: 마이구미알고리즘 풀이/수학 2017. 2. 7. 21:32
이번 글은 백준 알고리즘 12353번 "Baby Height" 를 다뤄본다.2013 Google code jam 문제이다.영어 문제라 번역이 필요하다. Every parent wants to know how tall their child will grow.모든 부모는 자녀들의 키가 얼마나 자라는 지 알고 싶어한다. Dr.Spaceman's algorithm, which we describe below.Dr.Spaceman의 알고리즘을 아래에서 설명하겠다. Accurately calculates, with errors low, Adult height of any child, with just genetics, yo!단순히 유전학으로 어떤 아이의 성인 신장을 낮은 오류와 함께 정확한 계산한다. Take th..
-
백준 1015번 수열 정렬 :: 마이구미알고리즘 풀이/정렬 2017. 2. 7. 01:05
이번 글은 백준 알고리즘 1015번 "수열 정렬" 을 다뤄본다.문제 이름을 보다시피 정렬 관련 문제다. P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다. 문제의 키워드는 비내림차순과 사전순으로 볼 수 있다.문제를 해결하기 위해 수열 P를 구해보자. 적용하는 방법으로 나와있는 B..
-
백준 12400번 Speaking in Tongues :: 마이구미알고리즘 풀이/수학 2017. 2. 5. 20:29
이번 문제는 백준 알고리즘 12400번 "Speaking in Tongues" 를 다뤄본다.2012 Google Code Jam 에서 출제된 문제이다.영어로 된 문제이기 때문에 해석이 필요하다.해석만 가능하다면 굉장히 쉬운 문제이기 때문에 두려울 게 없다. 문제를 보자. (번역과 함께 보여주겠다) We have come with up the best possible language here at Google, called Googlerese.- 구글은 Googlerese라고 불리는 최고의 언어를 제시한다. To translate text into Googlerese, we take any message and replace each English letter with another English lett..
-
백준 1507번 궁금한 민호 [플로이드] :: 마이구미알고리즘 풀이/그래프 2017. 2. 3. 17:36
이번 글은 백준 알고리즘 문제 "궁금한 민호"를 다뤄본다.플로이드 와샬 알고리즘을 통해 해결한다.백준 알고리즘 1507번 궁금한 민호 - https://www.acmicpc.net/problem/1507 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.예를 들어, 예제의..
-
백준 2146번 다리 만들기 :: 마이구미알고리즘 풀이/그래프 2017. 1. 24. 22:52
이번 글은 백준 알고리즘 문제 2146번 "다리 만들기" 를 다뤄본다.이 문제는 BFS DFS 활용 문제이다.하단에 비슷한 문제들이 나열되어 있다.DFS, BFS 관련 글.http://mygumi.tistory.com/102 위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나,위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).지도가 주어질 때, 가장 짧은 다리 하..