백준
-
백준 17822번 원판 돌리기 :: 마이구미알고리즘 풀이/그래프 2019. 12. 28. 20:11
이 글은 백준 알고리즘 문제 17822번 "원판 돌리기" 를 풀이한다. 2019 삼성 SW 테스트 문제 중 하나이다. 단순히 시뮬레이션으로 풀 수도 있으나, DFS 또는 BFS 를 활용할 수 있는 문제이다. DFS, BFS - https://mygumi.tistory.com/102 문제 링크 - https://www.acmicpc.net/problem/17822 본인은 처음 이 문제를 접근할 때, 많은 고민을 했다. 그런데 사실 이 문제는 사실 정답률에 비해, 크게 어렵지도 복잡하지도 않다. 그 이유는 고민할 게 크게 없었고, 테스트 케이스도 작아서, 어떻게 구현해도 시간 초과를 초래하지 않을 거라 판단했다. 그래서 "어떤 함정이 있을까?" 라는 의심에 시간을 좀 썼다. 사실 의심할 건 크게 없고, 이해..
-
백준 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열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는..
-
백준 17143번 낚시왕 :: 마이구미알고리즘 풀이/수학 2019. 5. 30. 16:48
이 글은 백준 알고리즘 문제 17143번 "낚시왕" 을 풀이한다. 삼성 SW 역량 테스트 문제이다. 특정 알고리즘을 요구하는 것보다는 정확한 문제 이해를 통한 구현이다. 문제 링크 - https://www.acmicpc.net/problem/17143 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 가장 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이..
-
백준 4158번 CD :: 마이구미알고리즘 풀이/수학 2017. 9. 2. 14:36
이 글은 백준 알고리즘 문제 4158번 "CD" 에 대한 문제를 풀이한다.이 문제를 풀기위해 특정 알고리즘에 대한 지식은 필요하지 않다.정답 비율이 20%대뿐만 아니라, 제출수가 많지 않은 문제이다.하지만 단순히 문제를 이해하고, 그것에 대해 논리적 사고만으로 충분히 풀 수 있는 문제이다. 상근이와 선영이는 동시에 가지고 있는 CD를 팔려고 한다. CD를 몇 개나 팔 수 있을까?입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄부터 N개 줄에는 상근이가 가지고 있는 CD의 번호가 오름차순으로 주어진다. 다음 M개 줄에는 선영이가 가지고 있는 CD의 번호가..
-
백준 1535번 안녕 :: 마이구미알고리즘 풀이/동적계획법 2017. 8. 26. 14:21
이 글은 백준 알고리즘 문제 1535번 "안녕" 을 풀이에 대해 작성된다.백트래킹과 동적계획법 2가지 풀이를 다뤄볼 것이다. 세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하게 되면 L[i]만큼의 체력을 잃게 되고, J[i]만큼의 기쁨을 얻게 된다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이 되거나, 음수가 되면, 죽게되서 아무런 기쁨을 못 느낀 것..
-
백준 1987번 알파벳 :: 마이구미알고리즘 풀이/그래프 2017. 7. 22. 22:36
이번 글은 백준 알고리즘 문제 1987번 "알파벳" 을 다뤄본다.문제 풀이는 DFS를 응용하여 해결할 수 있다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있..