Sangmun

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 다이나믹 프로그래밍으로 해결이 가능한 문제이며 또한 탐색해야되는 범위가 적기 때문에 2중 for문으로도 해결이 가능한 문제이다. 볼륨을 변경해야하는 단계마다 어떠한 볼륨으로 변경이 가능한지를 dp matrix에 저장을 해놓고 모든 경우의 수를 계산하해주면 된다. 문제의 예제 1번은 3 5 10 5 3 7 아래와 같은 형태로 dp matrix의 이전의 상태를 기..

https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net ' ', '+', '-'을 조합하여 만들 수 있는 수식중에서 0이 되는것을 찾는 문제이며 문제에서 제시되는 수의 범위가 굉장히 좁기 때문에 백트래킹을 이용하여 풀어도 시간내에 해결이 되는 문제이다. import sys input = sys.stdin.readline import copy t = int(input()) result = [] def backtracking(i): global s if i == n: s += str(i) tmp = copy..

https://ongveloper.tistory.com/376 [알고리즘] 크루스칼(Kruskal)과 프림(Prim) Goal MST란? 크루스칼이란? 프림이란? 최소 신장 트리에 사용된 최소 비용을 어떻게 구할까? 최소 비용으로 신장 트리를 어떻게 만들 수 있을까? 1. 크루스칼? 프림? MST? 1) MST(Minimum Spanning Tree) 신장 ongveloper.tistory.com 최소신장트리에 사용되는 크루스칼 알고리즘과 프림알고리즘을 알아보았다. 설명은 위의 블로그에서 너무 잘 설명해주셔서 내가 구지 더 할 필요는 없을것 같다. 파이썬 코드가 없어서 파이썬 코드를 추가해보았다. 1. 크루스칼 알고리즘 # 출처 '이것이 취업을 위한 코딩테스트다' def find_parent(parent..