알고리즘 풀이/스택, 큐
-
백준 2841번 외계인의 기타 연주 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 6. 00:38
이번 글은 백준 알고리즘 문제 "외계인의 기타 연주" 를 다뤄본다.문제 접근법은 스택을 활용한다.정답 비율과 제출수를 보면 어려운 문제에 속한다.하지만 문제를 이해하기 어려운 것이지, 쉬운 문제로 해당된다. 상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누..
-
백준 1725번 히스토그램 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 2. 20:42
이번 글은 백준 알고리즘 문제 1725번 "히스토그램"을 다뤄본다.6549번 "히스토그램에서 가장 큰 직사각형" 또한 거의 동일한 문제가 된다. 문제의 접근은 스택을 활용한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오. 처음에는 도저히 생각이 나지 않아, 순수하게 접근했다.시간초과가 발생할 것을 알았지만, 일단 풀어보았다.단순히, 하나의 막대를 기준으로, 왼쪽 오른쪽에 대..
-
백준 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) 로 계산된다.예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘..
-
백준 2493번 탑 [Stack] :: 마이구미알고리즘 풀이/스택, 큐 2017. 1. 18. 23:48
이번 글은 백준 알고리즘 2493번 문제 "탑" 을 다뤄본다.스택을 응용한 문제이다.백준 2493번 탑 문제 - https://www.acmicpc.net/problem/2493 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한..
-
백준 3986번 좋은 단어 [Stack] :: 마이구미알고리즘 풀이/스택, 큐 2017. 1. 16. 21:00
이번 글은 백준 알고리즘 3986번 "좋은 단어" 를 다뤄본다.이 문제는 스택을 통해 접근하는 문제이다.백준 3986번 좋은 단어 - https://www.acmicpc.net/problem/3986 평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 갯수를 세는 것을 도와주자. 문제만 보면, 바로 쉽게 이해하기는 힘들 수 있다.먼저 예를 통해 문제를 이해해보자.ABAB 주어졌을 경우를 보자.1. ABAB => A와 A 위로 아치형 곡선을 그린다.2. ABAB => B와 B 위로 아치형 곡선을 ..
-
백준 1021번 회전하는 큐 [Queue] :: 마이구미알고리즘 풀이/스택, 큐 2016. 10. 19. 20:27
이번 글은 백준 1021번 회전하는 큐를 다룰 것이다.정답률 33%정도이지만 쉬운 문제이다.1021번 회전하는 큐 - https://www.acmicpc.net/problem/1021Github - https://github.com/hotehrud/acmicpc 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.첫번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.오른쪽으로 한 칸 이동시킨..
-
백준 1158번 조세퍼스 문제 :: 마이구미알고리즘 풀이/스택, 큐 2016. 10. 18. 21:04
이번 문제는 백준 1158번 조세퍼스 문제를 다룰 것이다.이미 요세푸스의 문제로 많이 알려져있는 대중화된 문제이다.Github - https://github.com/hotehrud/acmicpc 조세퍼스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 이다.N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오. 본인은 보자마자 그냥 원이니..
-
백준 11279번 최대 힙 [Heap] :: 마이구미알고리즘 풀이/스택, 큐 2016. 8. 7. 14:50
이번 글은 백준 알고리즘 사이트 11279번 '최대 힙' 문제를 알아볼 것이다.자료구조 중 힙 에 관한 문제이다.Github - https://github.com/hotehrud/acmicpc 힙은 트리를 기반으로 된 자료구조다.일단 이것만 기억하면 된다.힙은 완전 이진 트리이다.이진트리는 자식노드가 최대 2개인 트리이지 않느냐?또한 균형이 잡혀있는 트리이다. 힙은 최대 힙과 최소 힙으로 나눌 수 있다.아래 그림처럼 최대 힙은 부모 노드가 자식 노드보다 큰 값을 가지는 구조이다.최소 힙은 당연히 반대이다. 당연히 힙으로 푼다.혹시 이전 글 10814번 나이순 정렬 글을 보면 좋다.http://mygumi.tistory.com/44 이번에도 우선순위 큐로 문제를 해결할 것이다.나는 그냥 최대 힙을 구현해서..