알고리즘 풀이
-
백준 14890번 경사로 :: 마이구미알고리즘 풀이/수학 2018. 4. 6. 18:41
이 글은 백준 알고리즘 문제 14890번 "경사로" 를 풀이한다.접근 방법은 단순 문제 이해를 통한 구현이 된다.2017 삼성 SW 역량 테스트 기출문제이다.문제 링크 - https://www.acmicpc.net/problem/14890 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.경사로는 낮은..
-
백준 14891번 톱니바퀴 :: 마이구미알고리즘 풀이/스택, 큐 2018. 4. 1. 21:46
이 글은 백준 알고리즘 문제 14891번 "톱니바퀴" 를 풀이한다.2017 삼성 SW 역량 테스트 기출 문제이다.시뮬레이션을 통한 하드코딩으로 풀 수도 있다.본인의 접근 방법은 덱(dequeue) 과 같은 개념과 재귀를 활용해 문제를 해결한다.문제 링크 - https://www.acmicpc.net/problem/14891 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞..
-
백준 10837번 동전 게임 :: 마이구미알고리즘 풀이/수학 2018. 4. 1. 21:46
이 글은 백준 알고리즘 문제 10837번 "동전 게임" 을 다뤄본다.정올(KOI) 중등부, 고등부 출제 문제이다.규칙을 찾아 단순한 구현을 통해 해결할 수 있다.문제 링크 - https://www.acmicpc.net/problem/10837 영희와 동수는 동전 던지기 게임을 하고 있다. 이 게임은 K번 라운드로 구성되고 다음과 같은 규칙들을 따른다:한 라운드에서 영희와 동수는 한 번씩 동전을 던지고 항상 영희가 먼저 던진다. 동전을 던져 앞면이 나오면 1점을 얻고, 뒷면이 나오면 점수를 얻지 못한다. 한 명이 남은 기회에 모든 점수를 얻더라도 상대방이 현재까지 얻은 점수보다 작게 되면 게임 도중 어떤 시점에서도 게임은 바로 끝난다. 위 표에서 영희와 동수의 점수가 0과 2가 되는 것이 불가능한 이유는 ..
-
백준 2110번 공유기 설치 :: 마이구미알고리즘 풀이/이진 탐색 2018. 3. 16. 20:24
이 글은 백준 알고리즘 2110번 "공유기 설치" 를 풀이한다.풀이 방법으로는 이분(이진) 탐색을 사용한다.문제 링크 - https://www.acmicpc.net/problem/2110이분 탐색 - http://mygumi.tistory.com/72 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이..
-
백준 1244번 스위치 켜고 끄기 :: 마이구미알고리즘 풀이/수학 2018. 3. 6. 19:59
이 글은 백준 알고리즘 문제 1244번 "스위치 켜고 끄기" 를 풀이한다.정올 초등부에서 출제된 문제로써, 단순 문제 이해를 통한 구현이다.문제 링크 - https://www.acmicpc.net/problem/1244 1부터 연속적으로 번호가 붙어있는 스위치들이 있다. 스위치는 켜져 있거나 꺼져있는 상태이다. 에 스위치 8개의 상태가 표시되어 있다. ‘1’은 스위치가 켜져 있음을, ‘0’은 꺼져 있음을 나타낸다. 그리고 학생 몇 명을 뽑아서, 학생들에게 1 이상이고 스위치 개수 이하인 자연수를 하나씩 나누어주었다. 학생들은 자신의 성별과 받은 수에 따라 아래와 같은 방식으로 스위치를 조작하게 된다.스위치 번호 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 스위치 상태 0 1 0 1 0 0 0 1 남학생은 스위치 번호가 ..
-
백준 1236번 성 지키기 :: 마이구미알고리즘 풀이/수학 2018. 3. 6. 00:36
이 글은 백준 알고리즘 1236번 "성 지키기" 를 풀이한다.접근 방식은 단순 문제 이해를 통한 수학적 접근이다.문제 링크 - https://www.acmicpc.net/problem/1236 영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다.성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오. 본인은 행과 열을 기준으로 무언가를 한다고 했을 때, DFS 또는 BFS 를 생각한다.이 문제의 경우에도 그렇게 생각했다.하지만 N의 크기 때문에 다소 무리가 있어, 다른 접근을 생각했다. 문제의 핵심은 모든 ..
-
백준 2505번 두 번 뒤집기 :: 마이구미알고리즘 풀이/수학 2018. 2. 5. 18:55
이 글은 백준 알고리즘 문제 2505번 "두 번 뒤집기" 를 풀이한다.정올 출제 문제로써, 문제 이해를 통한 구현으로 해결할 수 있다.문제 링크 - https://www.acmicpc.net/problem/2505 1부터 N까지의 숫자가 각 칸에 차례대로 들어있는 놀이판이 있다. 예를 들어 10 칸을 가진 놀이판의 초기 상태는 다음과 같다. 12345678910구간[i,j]는 놀이판의 왼쪽 i번째 칸부터 j번째칸 사이에 있는 모든 숫자를 말한다. 단 구간[i,j]에서 항상 라고 가정한다. 우리는 이 놀이판의 한 구간을 잡아서 그 구간을 완전히 뒤집을 수 있다. 만일 초기상태에서 구간[3,8]을 뒤집으면 놀이판은 다음과 같이 변한다.12876543910이어 이 상태에서 구간[1,5]를 다시 뒤집으면 놀이판..
-
백준 2591번 숫자카드 :: 마이구미알고리즘 풀이/동적계획법 2018. 1. 31. 20:50
이 글은 백준 알고리즘 문제 2591번 "숫자카드" 를 풀이한다.정올 출제 문제로써, 풀이 방법은 동적계획법을 통해 해결한다.문제 링크 - https://www.acmicpc.net/problem/2591 1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다.나중에, 적어 놓은 것에 맞게 다시 카드를 늘어놓으려고 보니, 방법이 여러 가지일 수 있다는 것을 알았다. 예를 들어 27123의 경우 아래와 같이 여섯 가지 다른 방법이 있다.카드의 숫자를 차례로 적어 놓은 것이 주어질 때, 위와 같이 그것을 가지고 거꾸로 카드의 배열을 찾으려고 한다. 가능한 카드의 배열이..