Hanbit the Developer

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제를 분석해보면, 전형적인 냅색 문제이다. 아래 사진을 보자. 각 열은, 해당 물건을 필수적으로 가져간다고 했을 때의 총 가치를 나타낸다. 점화식은 아래와 같다. DP[i][j] = DP[i][j-1] 또는 (현재 물건의 가치) + DP[0~i-1][j-(현재 물건의 무게)]의 최댓값 즉, dp[2][7]을 구할 때, 위의 사진과..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net import sys input = sys.stdin.readline def getMaxScore(stickers, n): for j in range(n): for i in range(2): if j == 0: continue elif j == 1: stickers[i][j] += stickers[(i+1) % 2][j-1] else: stickers[i][j] += max( sticke..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net import sys input = sys.stdin.readline INF = 1000000000 def bellmanFord(): global isAvailable for i in range(1, n+1): for j in range(1, n+1): for target, wasted in info[j]: if dp[target] > wasted + dp[j]: dp[target] =..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net import sys input = sys.stdin.readline def getRemainderRecursively(curB): if curB == 1: return a % c halfRemainder = getRemainderRecursively(curB//2) toReturn = halfRemainder*halfRemainder if curB % 2 != 0: toReturn *= a return toReturn % c if __name__ == '__ma..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net import sys input = sys.stdin.readline def setDistances(node): global distances for n, d in tree[node]: if distances[n] == -1: distances[n] = distances[node] + d setDistances(n) if __name__ == '__main__': V = int(in..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net import sys input = sys.stdin.readline def getParents(tree, N): parents = [-1 for _ in range(N+1)] todo = [1] while todo: cur = todo.pop(0) for node in tree[cur]: if parents[node] == -1: todo.append(node) parents[node] = cur return parents if __name__ == '__ma..

https://www.acmicpc.net/problem/2923 2923번: 숫자 게임 창영이와 현우는 새로운 게임을 하고 있다. 이 게임은 여러 라운드로 이루어져 있다. 매 라운드가 시작할 때, 현우는 창영이에게 100보다 작은 두 숫자 A와 B를 말해준다. 그러고 난 뒤, 창영이는 www.acmicpc.net Pypy3로 맞은 사람이 총 6명이긴 하지만 그 중에 시간복잡도와 공간복잡도가 마지막 등수인 풀이입니다.(참고로 Python으로 통과한 사람은 1명도 없습니다.) 이 점 참고해주시길 바랍니다. import sys input = sys.stdin.readline def getMinMaxSum(): # a, b를 변형시키고 다시 원상복구하기 위함 originalA = [a[i] for i in r..

https://www.acmicpc.net/problem/2785 import sys input = sys.stdin.readline def getChainCount(chains, N): chains.sort() chainCount = N tiedChains = 1 for chain in chains: if tiedChains + chain >= chainCount: break else: tiedChains += chain chainCount -= 1 return chainCount-1 if __name__ == '__main__': N = int(input()) chains = list(map(int, input().split())) chainCount = getChainCount(chains, N) ..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net #include #include int *parents; int findParent(int x) { if (parents[x] == x) return x; parents[x] = findParent(parents[x]); return parents[x]; } void unionSets(int x, int y) { int parentX = findParent..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net #include #include int *parents; int findParent(int x) { if (parents[x] == x) return x; parents[x] = findParent(parents[x]); return parents[x]; } void unionSets(int x, int y) { int parentX = findParent(x); int parentY = find..