저장한 비밀번호를 찾아 출력하는 문제로,사전 자료형을 쓰면 간단하게 해결되는 문제였다. import sysinput = sys.stdin.readline# 저장된 사이트의 주소 수 N, 비밀번호 찾으려는 사이트 주소 수 MN, M = map(int, input().split())memo = dict()for _ in range(N): key, value = input().split() memo[key] = valuefor _ in range(M): find = input().rstrip() print(memo[find])
분류 전체보기
풀이 1: 플로이드-워셜플로이드-워셜: 모든 정점 쌍 최단 거리 계산시간 복잡도는 O(N^3) - 이 문제는 N 최댓값 100이므로 이 문제에서 사용할 수 있다.import sysinput = sys.stdin.readlineN, M = map(int, input().split())# 거리 배열 초기화INF = sys.maxsizedist = [[INF] * (N+1) for _ in range(N+1)]# 자신과의 거리는 0으로for i in range(1, N+1): dist[i][i] = 0# 친구 관계 입력for _ in range(M): A, B = map(int, input().split()) dist[A][B] = 1 dist[B][A] = 1# 플로이드-워셜for k ..
문제 요약한번 입었던 옷들의 조합 다시 안 입는 해빈이 - 알몸이 아닌 상태로 며칠 돌아다닐 수 있는가 풀이간단한 조합 문제이다.import sysinput = sys.stdin.readlineresult = []testcases = int(input()) # 테스트케이스 개수def combi(clothes_dict): count = 1 # 곱셈을 위한 초기값 for clo_type in clothes_dict: count *= (len(clothes_dict[clo_type]) + 1) # + 1 은 선택하지 않는 경우 포함 return count - 1 # 알몸인 경우 제외for _ in range(testcases): n = int(input()) # 의상 수 ..
문제 요약듣 명단, 보 명단 각각 주어지면듣 & 보 명단 구하기.이름 길이는 20 이하, 명단은 각각 500,000 이하.듣보잡의 수와 그 명단을 사전순으로 출력 아이디어명단을 사전순으로 출력해야한다 -> 출력할 때는 set(집합)을 쓰면 안 된다.set은 순서를 보장하지 못하기 때문.집합으로 입력 저장하고, 교집합 구한 후 리스트로 정렬 후 출력하면 된다. 풀이import sysinput = sys.stdin.readlinen, m = map(int, input().split())n_list = {input() for _ in range(n)}m_list = {input() for _ in range(m)}total = n_list & m_listresult = sorted(list(total))p..
문제 요약높이 H 지정 (0~양의 정수)H보다 큰 나무는 H 위의 부분이 잘리고, 낮은 나무는 잘리지 않는다.적어도 M미터의 나무를 집에 가져가기 위한 절단기 높이의 최댓값나무의 수 N (1 ≤ N ≤ 1,000,000)가져가야 하는 길이 M (1 ≤ M ≤ 2,000,000,000)-> input값이 매우 크다. 시간 복잡도를 신경 써야 한다는 힌트이다. 첫번째 시도: 브루트 포스(완전탐색) - 시간 초과import sysinput = sys.stdin.readlineN, M = map(int, input().split())trees = list(map(int, input().split()))trees.sort(reverse=True)h = trees[0]-1for i in range(h, 0, -1)..
아이디어괄호를 적절히 쳐서 식의 값을 최소로 만들기. 식은 0~9, +, -로만 이루어져있다.-> 첫번째 '-' 기호를 기준으로, 이후에 나오는 모든 수를 괄호로 묶어 최대한 많이 빼면 된다. -> 그리디! 풀이str = input()parts = str.split('-')result = sum(map(int, parts[0].split('+')))for part in parts[1:]: result -= sum(map(int, part.split('+')))print(result) 문자열 다루는 게 익숙치 않아 꽤 헤맸던 문제이다.split을 잘 쓰는 게 관건이었다! parts = str.split('-') split('-')을 하게 되면, -을 기준으로 분리하여 리스트를 반환한다. sum(m..
주어진 삼각형 그림을 보면, 작은 삼각형의 합으로 다음 삼각형이 채워진다.-> DP 주어진 그림을 그려보며 생각해보면, 점화식을 어렵지 않게 찾을 수 있다.N12345678P(N)11122345P(8) = P(7) + P(3)P(7) = P(6) + P(2)P(6) = P(5) + P(1-> P(N) = P(N-1) + P(N-5)이다. 풀이dp = [0] * 101dp[1] = dp[2] = dp[3] = 1dp[4] = dp[5] = 2for i in range(6, 101): dp[i] = dp[i-1] + dp[i-5]t = int(input()) # 테스트 케이스 개수for _ in range(t): n = int(input()) print(dp[n])
방향 없는 그래프 주어짐 -> 연결 요소(connected component) 개수 구하는 프로그램 아이디어그래프 탐색 (DFS/BFS)방문 못한 노드 하나라도 있다면 카운트 증가하고그 방문 못한 노드 (false 노드)에서 시작해서 다시 그래프 탐색false 노드 없을 때까지 그래프 탐색 반복 풀이 - DFS 사용import sysinput = sys.stdin.readlineN, M = map(int, input().split())graph = [[] for _ in range(N+1)]for _ in range(M): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u)visited = [False] * (N+..
문제 요약수빈 현재 위치 N, 동생 현재 위치 K, 0부터 100,000 까지의 정수수빈이가 동생을 찾을 수 있는 가장 빠른 시간 구하기.수빈이가 이동할 수 있는 건 3가지 : X-1, X+1, 2*X 풀이시작 노드에 연결된 노드는 3개, 각 노드에서 1초가 지날 때마다 하나씩 이동하다가,목표 노드에 도착하면 걸린 시간 리턴-> BFS로 풀이할 수 있다 def bfs(n, k): if n == k: # 같다면 걸린 시간 0 return 0 visited = [False] * 100001 # 입력 값 범위보다 크게 queue = deque([(n, 0)]) # n에는 현재 노드 위치, 0에는 걸린 시간 저장 while queue: cur, time = queu..
문제 요약n * m 사이즈 토마토 보관 상자익은 토마토 인접한 곳에 있는 건 영향 받아 익게 됨.창고에 보관한 토마토들이 최소 며칠 지나면 다 익게 되는지!단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다. M,N은 2부터 10001은 익은 토마토, 0은 안 익은 토마토, -1은 토마토 없음토마토는 최소 하나 있다고 한다. 모두 익을 때까지의 최소 날짜를 출력하되,모든 토마토가 익어있다면 0 출력, 모두 익지 못하는 상황이라면 -1을 출력한다. 풀이이 문제는 BFS로 풀어야 하는 문제다. 하루가 지날 때마다 영향을 받아 익게 되기 때문. from collections import dequem, n = map(int, input().split()) # 가로, 세로graph = []for i in..
