알고리즘 풀이
-
백준 17822번 원판 돌리기 :: 마이구미알고리즘 풀이/그래프 2019. 12. 28. 20:11
이 글은 백준 알고리즘 문제 17822번 "원판 돌리기" 를 풀이한다. 2019 삼성 SW 테스트 문제 중 하나이다. 단순히 시뮬레이션으로 풀 수도 있으나, DFS 또는 BFS 를 활용할 수 있는 문제이다. DFS, BFS - https://mygumi.tistory.com/102 문제 링크 - https://www.acmicpc.net/problem/17822 본인은 처음 이 문제를 접근할 때, 많은 고민을 했다. 그런데 사실 이 문제는 사실 정답률에 비해, 크게 어렵지도 복잡하지도 않다. 그 이유는 고민할 게 크게 없었고, 테스트 케이스도 작아서, 어떻게 구현해도 시간 초과를 초래하지 않을 거라 판단했다. 그래서 "어떤 함정이 있을까?" 라는 의심에 시간을 좀 썼다. 사실 의심할 건 크게 없고, 이해..
-
백준 2602번 돌다리 건너기 :: 마이구미알고리즘 풀이/동적계획법 2019. 11. 10. 23:18
이 글은 백준 알고리즘 문제 2063번 "돌다리 건너기" 를 풀이한다. 정올 고등부 문제이자, 동적계획법(DP) 문제이다. 문제 링크 - https://www.acmicpc.net/problem/2602 절대반지를 얻기 위하여 반지원정대가 출발한다. 원정대가 지나가야할 다리는 두 개의 인접한 돌다리로 구성되어 있다. 하나는 이고 다른 하나는 이다. 아래 그림 1은 길이가 6인 다리의 한 가지 모습을 보여준다. 그림에서 위의 가로줄은 를 표시하는 것이고, 아래의 가로줄은 를 표시한다. 두 돌다리의 길이는 항상 동일하며, 각 칸의 문자는 해당 돌에 새겨진 문자를 나타낸다. 두 다리에 새겨진 각 문자는 {R, I, N, G, S} 중 하나이다. 출발 R I N G S R 도착 G R G G N S 반지원정대가..
-
백준 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개 위 결과를 수의 등장..
-
백준 17142번 연구소 3 :: 마이구미알고리즘 풀이/그래프 2019. 6. 3. 20:31
이 글은 백준 알고리즘 문제 17142번 "연구소 3" 를 풀이한다. 삼성 SW 역량 테스트 문제이다. 문제 해결을 위해 DFS, BFS 2가지 모두 요구한다. 문제 링크 - https://www.acmicpc.net/problem/17142 DFS, BFS - https://mygumi.tistory.com/102 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 모두 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며,..
-
백준 17144번 미세먼지 안녕! :: 마이구미알고리즘 풀이/스택, 큐 2019. 6. 1. 21:29
이 글은 백준 알고리즘 문제 17144번 "미세먼지 안녕!" 을 풀이한다. 삼성 SW 역량 테스트 문제이다. 특정 알고리즘을 요구하는 것보다는 정확한 문제 이해를 통한 구현이다. 문제 링크 - https://www.acmicpc.net/problem/17144 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는..
-
백준 17143번 낚시왕 :: 마이구미알고리즘 풀이/수학 2019. 5. 30. 16:48
이 글은 백준 알고리즘 문제 17143번 "낚시왕" 을 풀이한다. 삼성 SW 역량 테스트 문제이다. 특정 알고리즘을 요구하는 것보다는 정확한 문제 이해를 통한 구현이다. 문제 링크 - https://www.acmicpc.net/problem/17143 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 가장 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이..
-
백준 16236번 아기 상어 :: 마이구미알고리즘 풀이/그래프 2018. 12. 7. 17:27
이 글은 백준 알고리즘 문제 16236번 "아기 상어" 를 풀이한다.삼성 SW 출제 문제로써, 탐색 문제이다.문제 링크 - https://www.acmicpc.net/problem/16236BFS, DFS - http://mygumi.tistory.com/102 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신..