알고리즘 풀이/수학
-
백준 4158번 CD :: 마이구미알고리즘 풀이/수학 2017. 9. 2. 14:36
이 글은 백준 알고리즘 문제 4158번 "CD" 에 대한 문제를 풀이한다.이 문제를 풀기위해 특정 알고리즘에 대한 지식은 필요하지 않다.정답 비율이 20%대뿐만 아니라, 제출수가 많지 않은 문제이다.하지만 단순히 문제를 이해하고, 그것에 대해 논리적 사고만으로 충분히 풀 수 있는 문제이다. 상근이와 선영이는 동시에 가지고 있는 CD를 팔려고 한다. CD를 몇 개나 팔 수 있을까?입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄부터 N개 줄에는 상근이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. 다음 M개 줄에는 선영이가 가지고 있는 CD의 번호가..
-
백준 14653번 너의 이름은 :: 마이구미알고리즘 풀이/수학 2017. 8. 22. 00:28
이 글은 백준 알고리즘 문제 14653번 "너의 이름은" 을 풀이한다.2017 선린고에서 열린 천하제일 코딩대회 본선 문제에 속하면서, 가장 정답률이 낮은 문제가 된다. OAKAK TALK에는 신기한 기능이 있다. 바로 메세지 옆에 아직 안 읽은 사람의 수를 표시해주는 기능이다. 하지만 이 기능은 읽지 않은 사람의 수만 표시해줄 뿐, 메세지를 읽지 않은 사람이 누구인지는 표시해주지 않는다. 따라서 이 기능으로 메세지를 몇 명이 읽었는지는 알 수 있지만, 누가 읽었는지는 알 수 없다. 하지만 특정한 조건을 만족한다면, 우리는 메세지를 읽지 않은 사람을 유추해낼 수 있다.그 조건은 다음과 같다. N명이 있는 OAKAK TALK방이 있다. 그리고 그 방에는 K개의 메세지가 있다. 각각의 메세지는 해당 메세지의..
-
백준 1019번 책 페이지 :: 마이구미알고리즘 풀이/수학 2017. 7. 8. 18:56
이번 글은 백준 알고리즘 1019번 "책 페이지" 를 다뤄본다. 모 회사에서도 코딩 테스트로 출제되었다고 한다. 문제 풀이는 규칙을 찾은 후 구현해야하는 수학적인 사고가 필요하다. 지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오. 문제는 보다시피 정말 간단하다. 본인은 백준 사이트의 CEO 백준님의 자료를 통해 문제를 해결했다. 참고 자료 자료를 보더라도, 이해하기가 쉽지 않았다. 참고 자료를 보면 1 ~ N이 아닌 A ~ B를 예로 들었다. 핵심은 A는 일의 자리가 0이 되어야하고, B는 일의 자리가 9가 되어야하고, 각 자릿수를 나누어서 생각한다. (일의 자리에 대한 횟수, 십의 자리에 대한 횟수, 백..
-
백준 14583번 이음줄 :: 마이구미알고리즘 풀이/수학 2017. 5. 28. 10:44
이번 글은 백준 알고리즘 문제 14583번 "이음줄" 을 다뤄본다.최근 고려대학교 프로그래밍 대회에서 출제된 문제이다.본인은 굉장히 신선한 문제라고 생각했다. 문제 풀이는 직사각형, 평행사변형, 피타고라스, 각의 이등분선 등에 대한 이론이 필요하다.학생시절 머리 좀 써야하는 수학문제를 푼다는 느낌을 받을거라 생각한다. 문제는 링크를 통해 확인하길 바란다. 직사각형 종이를 접힌 부분을 표시해보면 아래와 같다. 우리가 구해야할 것은 보라색 영역의 가로와 세로가 된다. 우리는 직사각형의 대각선의 길이인 d를 먼저 구할 수 있다.h, v 가 주어진 상태이기 때문에 △ABC를 피타고라스의 정리를 이용할 수 있다. double d = Math.sqrt(h * h + v * v); 그 다음, 각의 이등분선의 성질을 ..
-
백준 2942번 퍼거슨과 사과 [최대공약수] :: 마이구미알고리즘 풀이/수학 2017. 5. 23. 22:49
이번 글은 백준 알고리즘 2942번 "퍼거슨과 사과" 를 다뤄본다.문제 풀이는 GCD, 즉 최대공약수를 활용하여 문제를 해결할 수 있다. 맨체스터 유나이티드의 감독 퍼거슨은 빨간 사과를 R개, 초록 사과를 G개 가지고 있다. 훈련장에 있는 선수들 중 몇 명에게 나누어 주려고 한다. 단, 선수들이 서로 같은 개수의 사과를 받지 못하면 경기력 저하가 나타날 수 있으므로 모든 선수에게 같은 개수를 주려고 한다. 퍼거슨 감독은 사과를 싫어한다. 따라서 사과가 남으면 안된다.예를 들어, 퍼거슨이 빨간 사과를 4개, 초록 사과를 8개 가지고 있다면, 다음과 같이 세가지 방법으로 나누어 줄 수 있다.선수 1명에게 빨간 사과 4개와 초록 사과 8개를 줄 수 있다.선수 2명에게 빨간 사과 2개와 초록 사과 4개를 각각 ..
-
백준 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마리의 돼지들의 요구를 들어줄 수 없..