Github & Portfolio
📚 Problem Solving/Baekjoon(73)
-
[백준-2960] 에라토스테네스의 체 / Python
2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net import sys input = sys.stdin.readline n, k = map(int, input().split()) cnt = 0 nums = [True] * (n + 1) for i in range(2, n + 1): for j in range(i, n + 1, i): if nums[j] == True: nums[j] = False cnt += 1 if cnt == k: print(j) break 해설 flag 리스트를 사용해 해결했다. 나머지는 주어진 조건대로 코드를 짜니 해결됐다.
-
[백준-11052] 카드 구매하기 / Python
11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) card = list(map(int, input().split())) d = [0] * (n + 1) d[1], d[2] = card[0], max(card[0] * 2, card[1]) for i in range(3, n + 1): d[i] = card[i - 1] for j in range(1, i // 2 + 1): d[i] = max(d[i], d[j] + d[i -..
-
[백준-18353] 병사 배치하기 / Python
18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) data = list(map(int, input().split())) d = [1] * n for i in range(n): for n in range(len(data[:i])): if data[i] < data[n] and d[i] < d[n] + 1: d[i] = d[n] + 1 print(len(d) - max(d)) 해설 dp 문제. 생각해야하는 경..
-
[백준-2407] 조합 / Python
https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net import sys import math input = sys.stdin.readline n, m = map(int, input().split()) print(math.factorial(n) // (math.factorial(n - m) * math.factorial(m))) 해설 공식만 알면 간단히 해결!
-
[백준-1629] 곱셈 / Python
1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net import sys input = sys.stdin.readline a, b, c = map(int, input().split()) def func(length): if length == 1: return a % c if length % 2 == 0: temp = func(length // 2) return temp * temp % c else: temp = func(length // 2) return temp * temp * a % c print(func(b)) 해설 기본 연산이나 반복문으로 풀면 시간 초과가 걸린다. 분할정..
-
[백준-1991] 트리 순회 / Python
1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) tree = {} for _ in range(n): root, left, right = map(str, input().split()) tree[root] = [left, right] def preorder(root): if root != ".": print(root, end="") preorder(tree[root][0]) preorder(tree[root][..