목록전체 글 (86)
Hikenny25
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net - 그래프 탐색 (BFS 사용) import sys input = sys.stdin.readline from collections import deque class Graph: def __init__(self, size): self.size = size self.matrix = [[0] * size for _ in range(size)] self.visited = [0] * size def addEdg..
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net - 재귀 (메모이제이션) import sys input = sys.stdin.readline def step(x): if x
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net - Dynamic Programming import sys input = sys.stdin.readline n = int(input()) dp = [0] * (n+4) dp[2] = dp[3] = 1 for i in range(4, n+1): if i % 3 == 0 and i % 2 == 0: dp[i] = min(dp[i-1], dp[i//2], dp[i//3]) + 1 elif i % 3 == 0: dp[i] = min(dp[i-1], dp[i//3]) + 1 elif i % 2 == 0: dp[i] = ..
https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net - 구현 import sys input = sys.stdin.readline n, m = map(int, input().split()) d = dict() for _ in range(n): ip = input().split() d[ip[0]] = ip[1] for _ in range(m): ip = input()[:-1] print(d[ip]) dict를 안다면 브론..
https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net - Dynamic Programming import sys input = sys.stdin.readline n = int(input()) p = list(map(int, input().split())) p.sort() dp = [0] * (n+1) dp[0] = 0 dp[1] = p[0] for i in range(2,n+1): dp[i] = dp[i-1] + sum(p[:i]) print(dp[n]) 보니까 디피로 안풀어도 ..
https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net - Greedy import sys input = sys.stdin.readline n,k = map(int, input().split()) a = list() for _ in range(n): a.append(int(input())) cnt = 0 while n >= 0: coin = a[n-1] cnt += (k // coin) ..
https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net - 구현 import sys input = sys.stdin.readline n,m = map(int, input().split()) d,a = dict(), list() for _ in range(n+m): i = input()[:-1] try: d[i] += 1 if d[i] == 2: a.append(i) except: d[i] = 1 a.sort() print(len(a)) for i i..
https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net - 구현 import sys input = sys.stdin.readline n, m = map(int, input().split()) a = list() for _ in range(n): a.append(input()[:-1]) for _ in range(m): i = input()[:-1] if i.isdigit(): print(a[int(i)-1]) else: p..
https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net - 구현 import sys input = sys.stdin.readline n = int(input()) k = 1 for i in range(1, n+1): k *= i cnt = 0 while k > 0: if k % 10 == 0: cnt += 1 k //= 10 else: break print(cnt) 그냥 팩토리얼 구하고 10씩 나누면서 구하면 된다
https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net - 구현 - 비트마스킹 import sys input = sys.stdin.readline m = int(input()) s = set() for _ in range(m): c = input().split() if c[0] == 'add': s.add(c[1]) elif c[0] == 'remove': try: s.remove(c[1]) except: pass elif c[0] == 'check': print(1 if c[1] in..