나의 잡다한 노트 및 메모

문제) https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 설명) 평범한 배낭1 문제와 다른 점은 물건 개수가 하나였다면 여기는 여러개가 있다. 그래서 최악의 경우 10000(m) * 100(n) * 10000(k)의 연산을 하게 되고 분명 시간초과가 된다. 그래서 이걸 어찌해야하나 고민했지만 모르겠어서 구글링을 해보았다. k를 log2로 줄이는 방법이 존재했다. 앞으로 log로 줄일 수 있는지에 대해 생각..

문제) https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dp를 만들때 2차원 배열로 만들었다. dp[i][j] 일때, i는 바텀업 방식으로 만들어진 합이고, j는 그 합을 만드는데 사용한 정수의 개수이다. 난 문제풀때 보면 문제의 간단한 예시를 가지고 그걸 바탕으로 알고리즘을 만들어 나가는 것 같다. 이번 문제도 그렇다. dp[4][2]와 dp[4][3]이 올바른 값을 가질려면 어떤 값들이 더해져야 하는지 생각했다. dp 배열의 인덱스는 하나의 목적을 가지고 있고, 그 목적은 문제의 답과 관련이 있다. 문제를 단순화했을 때 키워드는 합, 사용하는 정수의 개수 주의할 점은..

# 문제 https://www.acmicpc.net/problem/15683 # 소스코드 from collections import deque n, m = map(int, input().split()) cctv = [] wall = [] arr = [] ans = n * m dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] left = [-1, 0] right = [1, 0] up = [0, -1] down = [0, 1] two = [[left, right], [up, down]] three = [[up, right], [right, down], [down, left], [left, up]] four = [[left, up, right], [up, right, down], [right..

문제) https://www.acmicpc.net/problem/15897 15897번: 잘못 구현한 에라토스테네스의 체 성원이는 오늘 이산수학 수업 시간에 에라토스테네스의 체에 대해 배웠다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 성원이는 이 방법에 너 www.acmicpc.net 소스코드) n = int(input()) arr = [] ans = n j = 0 i = 2 while n > i: j = (n - 1) // ((n - 1) // i) num = 1 + (n - 1) // i ans += (j - i + 1) * num #print(i, j, num, ans) i = j+1 if n != 1: ans += 1 print(ans) 왤캐 어렵지...

# 문제 https://www.acmicpc.net/problem/1612 1612번: 가지고 노는 1 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 이 원숭이는 수를 이리저리 가지고 노는 것을 매우 좋아한다. 그중에서도 1을 가지고 노는 것을 매우매우매우매우매우 좋아한다. www.acmicpc.net # 소스코드 n = int(input()) temp = 1 ans = 1 if n % 2 == 0 or n % 5 == 0: print(-1) exit() while temp % n != 0: temp = (temp % n) * 10 + 1 ans += 1 print(ans) temp = (temp % n) * 10 + 1이 왤캐 와닿지가 않을까...ㅋㅋㅋ 그냥 1, 11, 111, 111..

# 문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net # 소스코드 import sys from collections import defaultdict n = int(input()) isParent = [1] visited = [False] * (n+1) parent = defaultdict(list) tree = [[] for _ in range(n+1)] for _ in range(n-1): a, b = map(int, sys.stdin.readline().split()) tree[a].append(b..

# 문제 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net # 소스코드 from collections import defaultdict import sys class Node: def __init__(self, root, left, right): self.root = root self.left = left self.right = right self.leftWidth = 0 self.height = 1 def setLeftWidt..

문제) https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 소스코드) from collections import deque n, k = map(int, input().split()) visited = [-1] * 100001 move = [0] * 100001 def path(x, k): ans= [] temp = x for _ in range(visited[k]+1): ans.append(temp) temp = ..