알고리즘 풀이
-
백준 2468번 안전 영역 [DFS] :: 마이구미알고리즘 풀이/그래프 2017. 6. 18. 22:48
이번 글은 백준 알고리즘 문제 2468번 "안전 영역" 을 다뤄본다.정올 초등부에서 출제된 문제이다.초등부이지만, 정답률은 30%인 것을 볼 수 있다.DFS, BFS - http://mygumi.tistory.com/102 문제 접근은 DFS 또는 BFS를 활용할 수 있다.기본적인으로 DFS 및 BFS 기본 지식을 가지고 있다면 충분히 풀 수 있다.여기서는 DFS를 통해 문제를 풀어보겠다. 위 그림은 높이가 4와 6의 경우를 나타내고 있다. 흰색 영역의 수를 찾는 문제가 된다.그래프에서는 이 영역을, 연결 요소의 개수라고 볼 수 있다.즉, DFS 탐색이 이루어지는 횟수 중 가장 큰 수가 정답이 된다. 높이를 1부터 100까지 경우 각각 DFS 탐색을 하면 된다. public static void dfs(..
-
백준 14585번 사수빈탕 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 5. 30. 23:38
이번 글은 백준 알고리즘 문제 14585번 "사수빈탕" 을 다뤄본다.문제는 2017 고려대학교 프로그래밍 대회에서 출제된 문제이다.문제 풀이는 동적계획법으로 접근할 수 있다. 수빈이는 좌표평면 위에 앉아있다. "나는 좌표평면이 너무 좋아!!" 라고 수빈이가 말했다. 좌표평면에는 N개의 사탕바구니가 있고, 각 사탕 바구니에는 M개의 사탕이 있다. 각 사탕 바구니는 (x1, y1), (x2, y2), …, (xn, yn)에 있고, 수빈이는 (0, 0)에 있다.오늘은 날씨가 덥다. 따라서 시간이 1만큼 지날 때마다 모든 사탕바구니에서 사탕은 1만큼 줄어든다. 수빈이는 매우 배가 고프기 때문에, 사탕바구니에 있는 사탕을 순식간에 모두 먹을 수 있다. 수빈이가 1만큼 움직일 때, 시간은 1만큼 지나간다. 수빈이는..
-
백준 14583번 이음줄 :: 마이구미알고리즘 풀이/수학 2017. 5. 28. 10:44
이번 글은 백준 알고리즘 문제 14583번 "이음줄" 을 다뤄본다.최근 고려대학교 프로그래밍 대회에서 출제된 문제이다.본인은 굉장히 신선한 문제라고 생각했다. 문제 풀이는 직사각형, 평행사변형, 피타고라스, 각의 이등분선 등에 대한 이론이 필요하다.학생시절 머리 좀 써야하는 수학문제를 푼다는 느낌을 받을거라 생각한다. 문제는 링크를 통해 확인하길 바란다. 직사각형 종이를 접힌 부분을 표시해보면 아래와 같다. 우리가 구해야할 것은 보라색 영역의 가로와 세로가 된다. 우리는 직사각형의 대각선의 길이인 d를 먼저 구할 수 있다.h, v 가 주어진 상태이기 때문에 △ABC를 피타고라스의 정리를 이용할 수 있다. double d = Math.sqrt(h * h + v * v); 그 다음, 각의 이등분선의 성질을 ..
-
백준 14582번 오늘도 졌다 [그리디] :: 마이구미알고리즘 풀이/그리디 2017. 5. 25. 22:40
이번 글은 백준 알고리즘 문제 "오늘도 졌다" 를 다뤄본다.2017년 고려대학교 프로그래밍 대회에서 출제된 문제이다.문제 풀이는 그리디 알고리즘으로 접근할 수 있다. 야구 지식이 하나도 없다면, 문제가 헷갈릴 수 있다.그 이유로 아마 정답률이 30%대이지 않을까 생각한다.14582번 오늘도 졌다. - https://www.acmicpc.net/problem/14582그리디 알고리즘 - http://mygumi.tistory.com/121 프로야구팀 울림 제미니스는 오늘도 졌다. 이번에는 스타트링크 걸리버스의 4번타자가 끝내기 홈런을 쳐서 졌다. 울림 제미니스의 열렬한 팬인 지수는 속으로 화를 참으며 어떤 선수 때문에 졌는지 생각해보았다. 지수는 팀이 역전패를 했다면 불펜 투수의 책임이고, 그렇지 않다면 ..
-
백준 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마리의 돼지들의 요구를 들어줄 수 없..