백준
-
백준 1918번 후위표기식 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 9. 15:21
이번 글은 백준 알고리즘 문제 1918번 "후위표기식" 을 다뤄본다.자료구조 수업을 들어봤다면, 문제 제목을 보자마자, 스택을 활용하는 문제라는 걸 알 수 있다.먼저 이론을 이해하고 푼다면, 쉬운 문제가 된다. (참고 자료) 문제는 중위 표기식을 후위 표기식으로 바꾸는 문제가 된다. 중위 표기식이란, 우리가 사용하는 수식이 된다. ex) a * (b + c) 후위 표기식이란, 컴퓨터가 사용하는 수식이 된다. ex) abc+* 중위 표기식에서 후위 표기식으로 바꾸는 과정은 아래와 같다. 피연산자(a,b,c)는 출력한다. 연산자는 앞 연산자(스택의 맨 위)를 살펴서 출력하거나 대기한다(스택에 넣는다, 대기 된 자료들은 나중에 대기 된 연산자가 먼저 나온다, LIFO, 스택을 이용) 연산자의 대기(스택에 pu..
-
백준 1019번 책 페이지 :: 마이구미알고리즘 풀이/수학 2017. 7. 8. 18:56
이번 글은 백준 알고리즘 1019번 "책 페이지" 를 다뤄본다. 모 회사에서도 코딩 테스트로 출제되었다고 한다. 문제 풀이는 규칙을 찾은 후 구현해야하는 수학적인 사고가 필요하다. 지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오. 문제는 보다시피 정말 간단하다. 본인은 백준 사이트의 CEO 백준님의 자료를 통해 문제를 해결했다. 참고 자료 자료를 보더라도, 이해하기가 쉽지 않았다. 참고 자료를 보면 1 ~ N이 아닌 A ~ B를 예로 들었다. 핵심은 A는 일의 자리가 0이 되어야하고, B는 일의 자리가 9가 되어야하고, 각 자릿수를 나누어서 생각한다. (일의 자리에 대한 횟수, 십의 자리에 대한 횟수, 백..
-
백준 2504번 괄호의 값 [Stack] :: 마이구미알고리즘 풀이/스택, 큐 2017. 6. 25. 22:22
이번 글은 백준 알고리즘 문제 2504번 "괄호의 값"을 다뤄본다.정올 2008년 초등부, 중등부 문제로써, 스택을 응용한 문제가 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. ‘()’ 인 괄호열의 값은 2이다.‘[]’ 인 괄호열의 값은 3이다.‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘..
-
백준 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개를 각각 ..