알고리즘 풀이
-
백준 2624번 동전 바꿔주기 :: 마이구미알고리즘 풀이/동적계획법 2017. 11. 21. 20:18
이 글은 백준 알고리즘 문제 2624번 "동전 바꿔주기" 를 풀이한다.풀이 방법으로는 동적계획법을 통해 진행된다.문제 링크 - https://www.acmicpc.net/problem/2624 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다.20 = 10×2 20 = 10×1 + 5×2 20 = 10×1 + 5×1 + 1×5 20 = 5×3 + 1×5입력으로 지폐의 금액 T, 동전..
-
백준 6378번 디지털 루트 :: 마이구미알고리즘 풀이/수학 2017. 11. 12. 22:31
이 글은 백준 알고리즘 문제 6378번 "디지털 루트" 를 풀이한다.문제는 단순한 구현이지만, 디지털 루트란 용어와 관련 공식이 실제로 존재하기 때문에 다루게 되었다.위키 - https://en.wikipedia.org/wiki/Digital_root문제 링크 - https://www.acmicpc.net/problem/6378 양의 정수 N의 디지털 루트를 구하려면 N을 이루고 있는 모든 자리수를 더해야 한다. 이 때, 더한 값이 한 자리 숫자라면, 그 수가 N의 디지털 루트가 된다. 두 자리 이상 숫자인 경우에는 다시 그 수를 이루고 있는 모든 자리수를 더해야 하며, 한 자리 숫자가 될 때 까지 반복한다.24의 디지털 루트를 구해보자. 2+4=6이다. 6은 한 자리 숫자이기 때문에, 24의 디지털 루..
-
백준 4195번 친구 네트워크 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 12. 20:48
이 글은 백준 알고리즘 문제 4195번 "친구 네트워크" 를 풀이한다.풀이 방법으로는 디스조인트-셋을 통해 진행된다.문제 링크 - https://www.acmicpc.net/problem/4195디스조인트 셋 이해 - http://mygumi.tistory.com/246 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 노드를 친구로, 간선을 친구 관계라고 생각할 수 있다.친구 관계라는 것은 같..
-
백준 9938번 방 청소 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 9. 20:55
이 글은 백준 알고리즘 문제 9938번 "방 청소" 를 풀이한다.풀이 방법으로는 디스조인트-셋 자료구조를 이용한다.개인적으로 보면, 굉장히 어려운 문제가 된다.문제 링크 - https://www.acmicpc.net/problem/9938디스조인트 셋 이해 - http://mygumi.tistory.com/246 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다.은기는 술병을 1번부터..
-
백준 13458번 시험 감독 :: 마이구미알고리즘 풀이/그리디 2017. 11. 5. 23:03
이 글은 백준 알고리즘 13458번 "시험 감독" 을 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.문제는 그리디(Greedy)하게 접근할 수 있다.정답 비율과 삼성 기출 문제를 보면 쉽지 않게 느껴지지 않지만, 굉장히 쉬운 문제가 된다.문제 링크 - https://www.acmicpc.net/problem/13458그리디 알고리즘 - http://mygumi.tistory.com/121 총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 방에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 방에서 감시할 수 있는 응시자의 수가 C명이다.각각의 시험장에 총감독관은 오직 1명만..
-
백준 1717번 집합의 표현 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 5. 22:23
이 글은 백준 알고리즘 문제 1717번 "집합의 표현" 을 풀이한다.문제는 디스조인트-셋(disjoint-set)을 이용하여 해결할 수 있다.문제 링크 - https://www.acmicpc.net/problem/1717디스조인트-셋 이해 - http://mygumi.tistory.com/246 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오. 이 문제는 디스조인트-셋에 대해 기초를 다지기 위한 가장 기본적인 문제가 된다.0일 때, 유니온(union) 을 호출하고, 1일 때, 파인드(find) 를 호출하면 된다. 다음 예제를 통해 ..
-
백준 10775번 공항 :: 마이구미알고리즘 풀이/디스조인트-셋 2017. 11. 5. 00:34
이 글은 백준 알고리즘 문제 10775번 "공항" 을 풀이한다.문제 풀이는 유니온-파인드(union-find) 또는 디스조인트-셋(disjoint-set) 이라고 불리는 자료구조를 이용한다.유니온-파인드 이해 - http://mygumi.tistory.com/246문제 링크 - https://www.acmicpc.net/problem/10775 오늘은 신승원의 생일이다.박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착..
-
백준 14499번 주사위 굴리기 :: 마이구미알고리즘 풀이/수학 2017. 10. 29. 16:35
이 글은 백준 알고리즘 문제 14999번 "주사위 굴리기" 를 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.특정한 알고리즘을 요구하지 않고, 단순히 문제의 이해를 통한 구현이다.https://www.acmicpc.net/problem/10775 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5 6주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (x, y) 이다. 가장 처음에 주사위에는 모든 면에 0이..