알고리즘 풀이/스택, 큐
-
백준 13415번 정렬 게임 :: 마이구미알고리즘 풀이/스택, 큐 2019. 6. 20. 18:51
이 글은 백준 알고리즘 문제 13415번 "정렬 게임" 을 풀이한다 2016 국민대학교 교내 경시대회 문제이다. Deque 를 이용하여 문제를 해결하지만, 그 외에도 고려해야하는 것들이 까다로운 문제라고 생각한다. 많은 힌트를 얻었지만, 그래도 까다로운 문제였다. 문제 링크 - https://www.acmicpc.net/problem/13415 즐거운 컴퓨터 프로그래밍 시간! 이번 시간의 수업 내용은 정렬이었다. 학생들은 오름차순 또는 내림차순으로 입력받은 값을 정렬해보기 시작하였다. 수업이 끝나갈 무렵, 오늘도 어김없이 조교의 과제가 주어졌다. 과제 이름은 정렬 게임. 과제 내용은 다음과 같다. 처음에 임의의 수열이 있고, 처음 위치부터 지정된 위치까지 오름차순, 내림차순, 오름차순, 내림차순, .....
-
백준 17140번 이차원 배열과 연산 :: 마이구미알고리즘 풀이/스택, 큐 2019. 6. 9. 00:36
이 글은 백준 알고리즘 문제 17140번 "이차원 배열과 연산" 을 풀이한다. 삼성 SW 역량 테스트 문제이다. 큐와 정렬을 이용해서 문제를 해결한다. 문제 링크 - https://www.acmicpc.net/problem/17140 크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 = 열의 개수라면 R 연산, 그렇지 않으면 C 연산을 실행한다. 2번이 의미하는 것은 다음과 같다. 1 2 1 1 3 4 4 => 1의 개수 => 3, 2의 개수 => 2, 3의 개수 => 1, 4의 개수 2개 위 결과를 수의 등장..
-
백준 17144번 미세먼지 안녕! :: 마이구미알고리즘 풀이/스택, 큐 2019. 6. 1. 21:29
이 글은 백준 알고리즘 문제 17144번 "미세먼지 안녕!" 을 풀이한다. 삼성 SW 역량 테스트 문제이다. 특정 알고리즘을 요구하는 것보다는 정확한 문제 이해를 통한 구현이다. 문제 링크 - https://www.acmicpc.net/problem/17144 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는..
-
백준 14891번 톱니바퀴 :: 마이구미알고리즘 풀이/스택, 큐 2018. 4. 1. 21:46
이 글은 백준 알고리즘 문제 14891번 "톱니바퀴" 를 풀이한다.2017 삼성 SW 역량 테스트 기출 문제이다.시뮬레이션을 통한 하드코딩으로 풀 수도 있다.본인의 접근 방법은 덱(dequeue) 과 같은 개념과 재귀를 활용해 문제를 해결한다.문제 링크 - https://www.acmicpc.net/problem/14891 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞..
-
백준 7662번 이중 우선순위 큐 :: 마이구미알고리즘 풀이/스택, 큐 2017. 9. 22. 11:21
이 글은 백준 알고리즘 문제 7662번 "이중 우선순위 큐" 를 풀이한다.문제명과 같이 우선순위 큐를 이용해서 문제를 해결할 수 있다.본인은 풀고나서도 문제가 무엇을 원하는 것인지 잘 모르는 문제이기도하다.7662번 - https://www.acmicpc.net/problem/7662 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데..
-
백준 1935번 후위표기식2 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 16. 21:36
이번 글은 백준 알고리즘 문제 1935번 "후위표기식2" 를 다뤄본다.1918번 "후위표기식" 문제는 중위표기식에서 후위표기식으로 변환하는 문제였다. - 관련 링크이번 문제는 후위표기식을 계산하는 문제로써, 1918번 문제를 푼 후, 풀어보면 좋은 문제가 된다. 중위표기식에서 후위표기식 변환 문제도 사실상 방법만 알면 간단했다.후위표기식의 계산 또한, 단순하다. 피연산자는 스택에 push 한다.연산자가 나오면 스택에 있는 수를 2번 pop 한다.pop한 두 수를 연산자에 맞게 계산한 후, 다시 push 한다.모든 계산이 끝나면, 스택의 top이 최종 계산 값이 된다. for (int i = 0; i < len; i++) { char ch = s[i]; switch(ch) { case '+': case '..
-
백준 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..