본문 바로가기

분류 전체보기

 (84)
백준 1507 궁금한 민호 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 이 문제는 플로이드 와샬을 역으로 활용하면 된다. 조금 생각해보면 직관적으로 그 아이디어가 떠오를 것이다. 그리고 그게 맞다! 플로이드 와샬 알고리즘을 이용해 최단경로를 구할 때, 최소값으로 계속 갱신해준다. 이번에는 그러한 경우가 발생할 때마다 해당 경로를 지워주면 된다. 각 정점들을 연결하는 도로정보가 주어지는데, 이들을 모두 더할 경우, 모든 도로의 가중치 합의 2배가 된다. 그러므로 중..
백준 1633 최고의 팀 만들기 https://www.acmicpc.net/problem/1633 1633번: 최고의 팀 만들기 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플 www.acmicpc.net 또다시 전형적인 다이나믹 프로그래밍 문제이다. 문제들 중에는 매 번 또는 매 정점마다 어떠한 처리를 하며 나아갈 때 가장 마지막에 어떤 결과값을 갖는지를 찾는 형식의 문제가 많이 있다. 앞서 말한 '매 번 또는 매 정점마다' m가지의 처리를 할 수 있고 정점이 총 n개 있다면 마지막의 결과값은 무엇인지를 찾는 문제. 이런 문제에 대한 풀이를 나이브(naive)하게 생각해본다면 그 시간복잡도..
다이나믹 프로그래밍 (동적 계획법) - Dynamic Programming 다이내믹이라고 할지 다이나믹이라고 할지 참 고민이 된다... 다이나믹 프로그래밍은 정말 많은 곳에 쓰이며, 정말 유용하고 때로는 정말 '다이나믹'하게 어렵기도 하다. 문제를 풀다보면 다이나믹 프로그래밍으로 풀리는 문제들에 대한 느낌 같은 것이 있다. 주로 연속된 정점들이 각각 동일한 옵션을 가질 때이다. 옵션이 m이고 정점의 갯수가 n이라면, 모든 케이스를 완전 탐색하기 위해 O(m^n) 이 걸릴 것 같은 문제들. 하지만 다이나믹 프로그래밍은 이것을 O(nm) 에 해결해준다. 즉, 각 옵션이 행이 되고, 각 정점들이 열에 배치되는 형태가 된다. 각 정점에서 어떤 옵션을 택했을 때 어떤 결과가 되는지를 기록해 나가는 것이다. 그리고 중요한 점은 그 결과들이 누적될 때 어떻게 처리해야 하는지이다. 필자가 생..
백준 2293 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍의 필수적인 문제이다. 예제를 보면 3가지의 동전으로 10을 만들어야 한다. 문제를 풀 때, 머릿속으로 골똘히 생각해 보는 것도 중요하지만, 빈 종이에 케이스를 한번 어느 정도 쭈욱 써보는 것도 큰 도움이 된다. 쓰고 나면 경향성이나 패턴을 읽어낼 수 있는 경우가 있기 때문이다. 10을 만들기 위해서는 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 ..
백준 1238 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 이 문제는 다익스트라와 역방향 그래프의 응용법? 사용법?을 한 가지 더 익힐 수 있는 좋은 문제다. 그리고 이 문제는 플로이드와샬을 사용하기는 힘들다 -> O(n^3)이기 때문이다. 위의 그림을 보자. 보통 다익스트라 최단경로 문제에서는 1번에서 출발하여 6번까지 가려고 할 때 소모되는 비용이나 경로를 출력하라고 한다. 그러면 보통 1번 정점에서 시작하여 우선순위 큐..
백준 1019 책 페이지 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 숫자 N이 주어졌을 때 1(첫 페이지)부터 N까지 쭉 순회하면서 등장한 숫자를 세는 건 당연히 안된다. 그 방법으로는 절대로 안된다는 걸 직관적으로 알려주기 위해 N의 상한이 10억이다... 그러면 당연히 숫자가 주어졌을 때 그 숫자만 보면서 답을 구할 수 있지 않을까라는 생각을 해봐야 한다. 필자가 생각한 방법은 주어진 숫자를 첫자리, 중간자리, 끝자리 이렇게 3개의 파트로 나누는 것이다. 예를 들어, 3516라는 숫자가 주어졌다고 하자. 그러면 첫자리는 3이고..
백준 20040 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 본 문제는 전형적인 유니온 파인드 문제이다. 혹시라도 유니온-파인드 알고리즘이 생소하신 분은 이 링크를 참조하여 훑어보기 바란다. 유니온-파인드를 이해하고 잘 적용할 수 있다면 비교적 평이한 문제일 수 있지만, 주의해야 할 부분이 있어서 포스팅하게 되었다. 파이썬 언어를 사용할 경우, 스택 깊이가 1000으로 기본 설정되어있는데, 이 깊이를 키우기 위해서는 아래와 같이 해야 한다. sys.s..
백준 11883 생일수 I https://www.acmicpc.net/problem/11883 11883번: 생일수 I 승현이는 1998년 3월 5일에 태어났습니다. 그래서 승현이는 자신의 생년월일에 있는 수들 중에서 3, 5, 8을 굉장히 좋아합니다. 이에 승현이는 10진수로 표현했을 때 3, 5, 8로만 구성되어 있는 자연 www.acmicpc.net 전형적인 다이나믹 프로그래밍 문제이다. 다만 몇 가지 신경 쓸 부분이 있다. 예제에서 주어진 11을 보자. 11은 3+8=11 이어서 38로 생일수를 만들 수 있다. 이 문제를 풀기 위해서는 3, 5, 8을 차례대로 활용하여 합산 해나가 11을 완성하면 된다고 생각할 수 있다. dp[i]자리에 3, 5, 8등을 넣어주고, dp[목표값]을 읽어서 그 자리에 8이 있다면, dp[목표..

티스토리툴바