알고리즘 풀이/수학
-
백준 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 이다..
-
백준 10610번 30 [배수 판정법] :: 마이구미알고리즘 풀이/수학 2017. 2. 13. 16:02
이번 글은 백준 알고리즘 10610번 "30" 을 다뤄본다.이 문제는 배수 판정법을 활용해서 문제를 해결할 수 있다.일단 먼저 문제를 보자. 어느날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. (그 수가 존재한다면) 주어지는 수에 대해 섞은 모든 경우에서 30의 배수가 되는 가장 큰 수를 찾는 문제다.예를 들어보자. 120과 210이 30의 배수이지만 가장 큰 수는 210이기 때문에 정답은 210이다.이 문제를 배수판정법을 통해 해결해보자. 3의 배수 판정법에 의하면, 모든 자리 수의 합이 3..
-
백준 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..
-
백준 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..
-
백준 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
-
백준 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
-
백준 3053번 택시 기하학 :: 마이구미알고리즘 풀이/수학 2016. 10. 18. 20:28
이번 글은 백준 알고리즘 3053번 "택시 기하학" 을 다뤄본다.문제 이름 그대로 택시 기하학에 관한 문제이다.문제는 아래와 같다. 19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다.택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다.D(T1,T2) = |x1-x2| + |y1-y2|두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다.따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다.원: 평면 상의 어떤 점에서 거리가 일정한 점들의 집합반지름 R이 주어졌을 때, 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓이를 구하는 프로그램을 작성하시오. 유클리드 기하학과 ..