백준
12582_1로 만들기 2
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이전에 풀어보았었던 내용이지만 값이 엄청 커졌다. dp를 활용해서 푸니까 잘 풀렸다. 1부터 시작해서 *2, *4, +1 을 해서 저장된 값보다 길이가 적으면 그 값들을 리스트형태로 전달하게 해주었다. n = int(input()) dp = [ [] for i in range(n+1) ] dp[1].append(1) for i in range(1,n+1): LEN = len(dp[i]) if i*3
1450_냅색문제
https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net Meet in Middle알고리즘을 이용해보라고 힌트가 주어져 있는 문제이다. 위 문제같은 경우, 쉽게 생각하면 주어진 배열중에서 합이 c가 넘지않는 부분배열의 개수를 구하는 문제라고 생각해ㅗㄷ 좋을 것이다. 예를들어 [ 1, 2, ,3 , 4, 5,6 ] 해당 6개의 짐이 있다면 합이 10을 넘지않는 부분집합의 개수를 구하는 문제로 봐도 될 것이다. 이런 경우 모든 배열을 한번씩 탐색하면 굉장히..
1644_소수의 연속합
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 이전에 소수구하기 문제를 풀었던 경험이 있는데 소수를 구하는 리스트를 만든 후에, 저번문제에서 다뤘던 방식을 사용해서 문제를 풀면 된다. 두가지의 문제가 합쳐진 형태이다. n = int(input()) lst = [True] * (n+1) for i in range(2,int((n+1)**0.5)+1): if lst[i]: for j in range(i*2,n+1,i): lst[j] = False sosu = [0] for i in range(2,n+1): if lst[i]: sosu.append(i) start,e..
1806_부분합
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 이역시 투포인터로 풀 수 있었다! 단 이전까지는 start포이터와 end 포인터가 끝에서 시작했는데 이번에는 둘다 시작점에서 출발하게 하는것이 달랐다. 10 15 5 1 3 5 10 7 4 9 2 8 먼저 start포인터와 end 포인터를 둘다 0이라 생각하고 시작한다. 그리고 두 포인터 가 지칭하는 사이의 값들을 더한게 S보다 작다면 end 포인터를 증가시키고, 그렇지 않다면 st..
3273_두수의 합
https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 처음 문제를 보면 for문을 두번 돌려서 문제를 풀었을 것 같다. 하지만 문제에서도 나와있듯이 투 포인터 알고리즘을 사용해서 풀라고 한다! 투 포인터 알고리즘이란 1차원 배열에서 공간을 가리키는 두개의 포인터를 지니는 방식으로 특정값을 추출해내는 알고리즘이다. 인터넷을 좀 뒤져서 공부를 해보니 투 포인터에는 몇가지 방법이 있다. 크게 두가지가..
1956_운동
https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 이제 그래프를 활용해서 최단거리를 구하는 것은 익숙해졌다! 사이클을 구하기 위해서 어떻게 해야할까 고민하다가 결국 사이클이란 것은 본인에서 시작해서 본인으로 돌아오는 최단거리라고 생각했다. 지금까지 코드를 구현할때는 1번에서 1번으로 가는것은 0으로 두었었는데, 이를 그냥 설정하지 않고 코드를 진행시키고, INF가 아닌 최솟값을 찾는 코드를 구현하면 될것같아서 해..