백준
-
백준 13900번 순서쌍의 곱의 합 [부분합] :: 마이구미알고리즘 풀이/수학 2017. 5. 21. 00:34
이번 글은 백준 알고리즘 문제 13900번 "순서쌍의 곱의 합" 을 다뤄본다.최근에는 서강대학교 프로그래밍 대회에서 출제된 문제이다.정답률이 30%이하로써, 단순히 쉬운 문제는 아닐 것이다.풀이 방법은 많겠지만, 부분합으로 일반적으로 접근할 수 있다. N개의 정수 중 서로 다른 위치의 두 수를 뽑는 모든 경우의 두 수의 곱의 합을 구하라.예를 들어 N = 3이고 주어진 정수가 2, 3, 4일 때, 두 수를 뽑는 모든 경우는 (2, 3), (2, 4), (3, 4)이며 이 때 각각의 곱은 6, 8, 12이다. 따라서 총합은 26이다. 처음에는 동적계획법 느낌으로 접근하려했다.2를 뽑을 경우 나머지 3, 4를 뽑을 수 있고, 3을 뽑을 경우 4를 뽑을 수 있다.쉽게 2개의 반복문을 통해 구현할 수 있겠다고 ..
-
백준 6322번 직각 삼각형의 두 변 :: 마이구미알고리즘 풀이/수학 2017. 5. 20. 22:10
이번 글은 백준 알고리즘 문제 6322번 "직각 삼각형의 두 변" 을 다뤄본다.사실 제목만 봐도 무슨 문제인지 파악할 수 있다. 중등과정 피타고라스의 공식을 활용하면 문제를 풀 수 있다.사실 상 쉬운 문제로써, 글의 주제거리가 될만큼은 아니지만 좋은 문제라고 판단했다.문제는 피타고라스의 공식의 약간의 응용이 필요하다.피타고라스 공식, 소수점 포맷, 제곱근 3가지만 알고 있다면, 무난히 해결할 수 있다. 직각 삼각형의 세 변의 길이 a, b, c가 주어진다. a, b, c중 하나는 -1이며, -1은 알 수 없는 변의 길이이다. 다른 두 수는 10,000보다 작거나 같은 자연수이다. 주어지지 않는 한 가지 변의 길이를 찾는 문제가 된다. a^2 + b^2 = c^2a^2 + b^2 - c^2 = 0 피타고라..
-
백준 3060번 욕심쟁이 돼지 :: 마이구미알고리즘 풀이/수학 2017. 5. 16. 23:21
이번 글은 백준 알고리즘 문제 3060번 "욕심쟁이 돼지" 를 다뤄본다.난이도 있는 문제가 아니지만, 정답률은 30%이기 때문에, 함정이 있을거라 예측할 수 있다.문제 풀이는 나머지 연산을 활용하는 문제라고 볼 수 있다. 예를 들어, 현수가 1번부터 6번까지 돼지에게 각각 3, 2, 7, 1, 5, 4만큼 밥을 주었다면, 2번 돼지는 첫 날 받은 양 2에다 양쪽과 맞은편 돼지가 받은 양 15(3+7+5)만큼을 더해 17만큼 받기를 원한다.마음씩 좋은 농부 박현수는 이런 돼지의 요구를 모두 들어주려고 한다. 매일 현수의 집에 신선한 사료가 N만큼 배달된다. 사료의 유통기한은 하루이기 때문에, 남은 사료는 모두 폐기한다.첫 날 돼지들이 먹었던 양이 주어졌을 때, 현수가 6마리의 돼지들의 요구를 들어줄 수 없..
-
백준 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을 출력한다. 하지만 본인은 도저히 동적계획법으로는 생각나지 않아, 브루트 포스(노가다)로 풀었다.완전한 노가다는 아니라, 불필요한 과정을 제외시킴으로써, 시간 제한을 피할 수 있었다.테스트케이스가 많은 것도 아니고, 노가다로 풀어도 충분히 시간 제한에 걸리지 않을 거..