백준
11779_최소비용 구하기 2
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이전의 다익스트라 알고리즘을 활용하면 풀 수 있다. 이전과 다른점은 어디를 방문했는지 기록을 해둬야 할것이다. 그래서 visited란 배열을 하나 만든 후에, 새로운 노드에 값을 기록할때마다 어느 노드에서 왔는지 기록하도록 하였다. import sys import heapq input = sys.stdin.readline INF = int(1e9) n = int(i..
9019_DSLR
https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net bfs를 활용하면 되는 문제이다. 결국 이전 숨바꼭질 문제들과 비슷하게 풀 수 있다. D,S,L,R 연산을 한번씩 한 후에 dp에 넣어주면서 풀면 된다. 만약 어떠한 연산으로 200이란 수가 나왔다면 그 다음에 200이 나온 경우에는 queue에 추가하지 않는 방식으로 문제를 풀면 될 것이다. 이때 역추적또한 해야하는데, 이전의 데이터를 굳이 넣진 않고 큐 구조에 답을 저장하는 공간을..
13913_숨바꼭질
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질의 연장선 문제이다. bfs를 통해서 카운트를 통해 몇초가 걸리는지 걸리는건 해볼 수 있다. 이때 0~100000까지의 배열을 만들어두고 해당하는 초를 새기면서 카운팅을 한다. 그렇다면 이 배열을 기록해나갈때 어느 점에서 나왔는지도 기록을 하면 쉽게 역추적을 할 수 있다. 이배열의 이름을 cnt라고 해보자 예를 들어 5 17인경우 5 10 9 18 17 5..
9252_LCS2
https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이전에 LCS문제를 풀어봤다면 비슷하게 풀 수 있다. 해당 예제를 dp에 넣을때 위처럼 쌓여지게 된다. 첫째줄부터 살펴보면 C를 가지고 A, AC , ACA, ACAY, ACAYK, ACAYKP 랑 순서대로 비교하면서 배열을 찾는 것이다. 두번재줄은 A,C를 가지고 A, AC , ACA, ACAY, ACAYK, ACAYKP 랑 비교하면서 길이를 찾는..
14003_ 가장 긴 증가하는 수열
https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 이전에 dp를 이용해서 for문을 두번 돌리는 방식으로 가장 긴 증가하는 수열을 구했었다. 하지만 위 문제는 같은 시간복잡도를 가지고는 풀 수 없다. 시간복잡도를 줄이기 위해서 기록을 위한 dp를 두개를 사용할 것이다. 하나는 해당 숫자가 가진 가장 긴증가하는 부분 수열의 길이를 저장할 것이고 하나는 수열을 증가시킬지 이전 수열과 비교할지를 판독하는데 사용할 임시 배..
14002_가장 긴 증가하는 수열
https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 다시 돌아온 dp파트이다. 이전에 가장 긴 증가하는 부분수열의 개수만 구하는 코드를 짠 적이 있는데 이번에는 그 수열자체를 구하는 코드이다. 하지만 첫번째 줄부터 기록해나가면서 작성하는 방법인데는 변함이 없다 1 2 1 3 2 5 라고 생각해보자. 그리고 dp를 [ [1] [2] [1] [3] [2] [5] ] 이렇..