알고리즘 풀이
-
백준 7570번 줄 세우기 :: 마이구미알고리즘 풀이/동적계획법 2017. 12. 24. 18:42
이 글은 백준 알고리즘 문제 7570번 "줄 세우기" 를 풀이한다.정올 초등부, 중등부에서 출제된 문제이다.동적계획법과 구현을 통한 2가지 풀이를 다뤄본다.문제 링크 - https://www.acmicpc.net/problem/7570 예를 들어, 5명의 어린이들에게 1부터 5까지의 번호가 주어져 있고, 다음과 같은 순서로 줄서 있다고 하자. 5 2 4 1 3위 방법을 이용해서 다음과 같이 번호순서대로 줄을 세울 수 있다. (1) 1번 어린이를 제일 앞으로 보낸다. (5 2 4 1 3 → 1 5 2 4 3)(2) 4번 어린이를 제일 뒤로 보낸다. (1 5 2 4 3 → 1 5 2 3 4)(3) 5번 어린이를 제일 뒤로 보낸다. (1 5 2 3 4 → 1 2 3 4 5)위의 예에서는 세 명의 어린이를 제일..
-
백준 10800번 컬러볼 :: 마이구미알고리즘 풀이/수학 2017. 12. 21. 00:05
이 글은 백준 알고리즘 문제 10800번 "컬러볼" 을 풀이한다. 정올 초등부, 고등부에서 출제된 적이 있다. 본인의 푼 방식은 다른 풀이보다 속도면에서는 떨어진다. 문제 링크 - https://www.acmicpc.net/problem/10800 2019.10.10 수정 완료 지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종하여 게임에 참여한다. 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않는다. 다음 예제는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다. 공 번호색크기 ..
-
백준 2980번 도로와 신호등 :: 마이구미알고리즘 풀이/수학 2017. 12. 17. 12:59
이 글은 백준 알고리즘 문제 2890번 "도로와 신호등" 을 풀이한다.시뮬레이션 문제로써, 시나리오를 정확히 이해한 후 그대로 구현하면 된다.문제 링크 - https://www.acmicpc.net/problem/2980 상근이는 트럭을 가지고 긴 일직선 도로를 운전하고 있다. 도로에는 신호등이 설치되어 있다. 상근이는 각 신호등에 대해서 빨간 불이 지속되는 시간과 초록 불이 지속되는 시간을 미리 구해왔다. (빨강색과 초록색 불빛은 무한히 반복된다)상근이의 트럭이 도로에 진입했을 때, 모든 신호등의 색상은 빨간색이고, 사이클이 막 시작한 상태이다. 상근이는 1초에 1미터를 움직인다. 신호등의 색상이 빨간색인 경우에는 그 자리에서 멈추고 초록색으로 바뀔때 까지 기다린다.상근이가 도로의 끝까지 이동하는데 걸..
-
백준 2512번 예산 :: 마이구미알고리즘 풀이/수학 2017. 12. 17. 11:58
이 글은 백준 알고리즘 문제 2512번 "예산" 을 풀이한다.시뮬레이션 문제로써, 시나리오를 정확히 이해한 후, 그대로 구현하면 된다.문제 링크 - https://www.acmicpc.net/problem/2512 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그..
-
백준 11559번 Puyo Puyo :: 마이구미알고리즘 풀이/그래프 2017. 12. 11. 11:10
이 글은 백준 알고리즘 문제 11559번 "Puyo Puyo" 를 풀이한다.시뮬레이션 문제로써, 시나리오를 정확히 이해한 후 그대로 구현하면 된다.본인은 그 과정속에 DFS를 통해 해결했다.문제 링크 - https://www.acmicpc.net/problem/11559 뿌요뿌요의 룰은 다음과 같다.필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다.뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이..
-
백준 5623번 수열의 합 :: 마이구미알고리즘 풀이/수학 2017. 12. 5. 21:03
이 글은 백준 알고리즘 문제 5623번 "수열의 합" 을 풀이한다.방법으로는 수학을 이용한 풀이가 된다.문제 링크 - https://www.acmicpc.net/problem/5623 양의 정수 N개로 이루어진 수열 A가 있다. 상근이는 수열 A의 모든 두 수의 합을 알고 있다. 이 때, 수열 A를 구하는 프로그램을 작성하시오. 다음 N개 줄에는 100,000보다 작거나 같은 양의 정수가 N개씩 주어진다. 이 숫자들은 S를 이루는 숫자이며, S(i,j) = A[i] + A[j] (i≠j), S(i,j) = 0 (i=j) 이다. S(i,j)는 i번째 줄, j번째 숫자를 의미하며, A[i]는 A의 i번째 수이다. S(i,j) = A[i] + B[j] 이 부분만 이해하면 쉽게 문제를 해결 할 수 있다. 4 0..
-
백준 2698번 인접한 비트의 개수 :: 마이구미알고리즘 풀이/동적계획법 2017. 11. 30. 20:21
이 글은 백준 알고리즘 문제 2698번 "인접한 비트의 개수" 를 풀이한다.풀이 방법으로는 동적계획법을 이용한다.문제 링크 - https://www.acmicpc.net/problem/2698 0과 1로 이루어진 수열 S가 있다. S의 첫 수는 s1이고, 마지막 수는 sn이다. S의 인접한 비트의 개수는 다음과 같이 구할 수 있다.s1*s2 + s2*s3 + s3*s4 + ... + sn-1 * sn위의 식을 이용하면 수열 S에서 인접한 1의 개수를 구할 수 있다. 예를들어, 011101101의 인접한 비트의 개수는 3이 되고, 111101101은 4, 010101010은 0이 된다.수열 S의 크기 n과 k가 주어졌을 때, 인접한 비트의 개수가 k인 수열 S의 개수를 구하는 프로그램을 작성하시오.예를 들..
-
백준 10844번 쉬운 계단 수 :: 마이구미알고리즘 풀이/동적계획법 2017. 11. 27. 20:33
이 글은 백준 알고리즘 문제 10844번 "쉬운 계단 수" 를 풀이한다.풀이 방법으로는 동적계획법으로 설명한다.문제 링크 - https://www.acmicpc.net/problem/10844 45656이란 수를 보자.이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 인접한 모든 자리수의 차이가 1인 수를 어떻게 찾을까?직접 적어보면 쉽게 점화식을 만들어낼 수 있다. N = 1=> 1, 2, 3, 4, 5, 6 ......N = 2=> 10, 12, 21, 23, 32, 34, 43, 45 ....