알고리즘 풀이
-
백준 2014번 소수의 곱 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 16. 00:42
이번 글은 백준 알고리즘 문제 2014번 "소수의 곱" 을 다뤄본다.문제 풀이는 큐 중에서도 우선순이 큐를 활용하여 해결할 수 있다.정답 비율과 제출 수를 보면 어려운 문제에 속한다. K개의 소수가 있다. 이 때, 이 소수들 중에서 몇 개를 곱해서 얻게 되는 수들이 있을 것이다. 소수들을 선택할 때에는 같은 수를 선택해도 되며, 주어지는 소수 자체도 포함시키자.예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다.K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자. 단 정답은 32-bit integer 이내이다. 본인은 처음에 K개가 100개밖에 안되기..
-
백준 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가 되어야하고, 각 자릿수를 나누어서 생각한다. (일의 자리에 대한 횟수, 십의 자리에 대한 횟수, 백..
-
백준 2841번 외계인의 기타 연주 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 6. 00:38
이번 글은 백준 알고리즘 문제 "외계인의 기타 연주" 를 다뤄본다.문제 접근법은 스택을 활용한다.정답 비율과 제출수를 보면 어려운 문제에 속한다.하지만 문제를 이해하기 어려운 것이지, 쉬운 문제로 해당된다. 상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누..
-
백준 1005번 ACM Craft :: 마이구미알고리즘 풀이/정렬 2017. 7. 2. 23:06
이번 글은 백준 알고리즘 문제 1005번 "ACM Craft" 를 다뤄본다.문제 번호를 보다시피, 오래된 문제로 제출량이 만건이 넘은 문제이다.정답률이 17%밖에 안되지만, 어려운 문제가 아닌, 쉬운 문제로 속한다.1년 전 풀었지만, 재채점으로 인해 런타임에러가 떴기에, 복습 겸 다시 풀어보았다.문제 풀이의 접근은 위상 정렬을 활용한다. 이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 ..
-
백준 1725번 히스토그램 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 2. 20:42
이번 글은 백준 알고리즘 문제 1725번 "히스토그램"을 다뤄본다.6549번 "히스토그램에서 가장 큰 직사각형" 또한 거의 동일한 문제가 된다. 문제의 접근은 스택을 활용한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오. 처음에는 도저히 생각이 나지 않아, 순수하게 접근했다.시간초과가 발생할 것을 알았지만, 일단 풀어보았다.단순히, 하나의 막대를 기준으로, 왼쪽 오른쪽에 대..
-
백준 10942번 팰린드롬? :: 마이구미알고리즘 풀이/동적계획법 2017. 6. 30. 19:55
이번 글은 백준 알고리즘 문제 10942번 팰린드롬? 을 다뤄본다.로켓처럼 빠른 회사인 쿠* 개발자 코딩 테스트에서 출제된 문제이기도 하다.문제 풀이의 최적의 접근법은 동적계획법이다.여기서는 동적계획법과 순수한 다른 방법을 다룬다. 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.각 질문은 두 정수 S와 E로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우..
-
백준 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) 로 계산된다.예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘..