딥러닝 공부방

백준 2512번 예산 www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 파이썬 풀이 import sys input = sys.stdin.readline N = int(input()) cities = list(map(int, input().split())) budgets = int(input()) # 예산 start, end = 0, max(cities) # 시작 점, 끝 점 # 이분 탐색 while start mid: total += mid else: t..

백준 2805번 나무 자르기 www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 파이썬 풀이 이분 탐색 풀이입니다. 톱날의 높이를 이분 탐색으로 찾습니다. import sys input = sys.stdin.readline N, M = map(int,input().split()) # 나무 수, 필요한 나무 길이 trees = list(map(int, input().split())) start, end = 0, max(tre..

백준 17219번 비밀번호 찾기 www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 파이썬 풀이 import sys import collections input = sys.stdin.readline dic = collections.defaultdict(str) N, M = map(int,input().split()) # 사이트 수, 비밀번호를 찾을 사이트 수 for i in range(N): # 사이트와 비밀번호 저장 site, p..

백준 2751번 수 정렬하기 2 www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 파이썬 풀이 병합 정렬로 풀었습니다. import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N = int(input()) arr = [] for i in range(N): arr.append(int(input())) def merge_sort(arr): if len(arr) R[j]): mer.appe..

백준 2750번 수 정렬하기 www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 파이썬 풀이 삽입 정렬을 이용했습니다. N = int(input()) # 원소 수 입력 받기 arr = [] # 빈 어레이 생성 for i in range(N): arr.append(int(input())) # 숫자 삽입 # 삽입 정렬 for j in range(1, len(arr)): key = arr[j] i = j-1 while i >= 0 and arr[i] > key: # key..

백준 11053번 가장 긴 증가하는 부분 수열 www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 파이썬 풀이 동적 프로그래밍을 활용한 풀이입니다. import sys import collections input = sys.stdin.readline N = int(input()) # 수열 크기 dp = collections.defaultdict(int) # 데이터 저장 stack = ..

백준 2747번 피보나치 수 www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 파이썬 풀이 동적 프로그래밍으로 이전에 계산한 값들을 저장한뒤에, 현재 값을 계산할 때 저장한 값을 불러오도록 풀었습니다. import sys import collections sys.setrecursionlimit(10**6) input = sys.stdin.readline N = int(input()) dp = collections.defaultd..

1197번 최소 스패닝 트리 www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 파이썬 풀이 프림 알고리즘을 사용했습니다. # 프림 알고리즘은 다익스트라 알고리즘과 거의 유사하다고 생각합니다. # 차이점은 프림 알고리즘은 인접 간선을 추출하여 우선순위 큐에 삽입할 때, # 순환이 발생하면 안되므로 방문한 노드인지 확인을 하고 우선순위 큐에 삽입을 합니다. import heapq import collections im..

백준 1647번 도시 분할 계획 www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 파이썬 코드 크루스컬 알고리즘을 사용하여 그래프를 MST로 만들었습니다. 또한 두 개의 집합으로 분리해야 하므로 MST의 간선 개수가 N-2가 될 때 중지되도록 구현했습니다. import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N, M = map(int,input().spli..

백준 1922번 네트워크 연결 www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 파이썬 풀이 크루스컬 알고리즘으로 주어진 그래프를 MST로 만듭니다. MST의 총 가중치를 출력합니다. # 크루스컬 알고리즘 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N = int(input()) # 정점 수 입력 받기 M = int(input()) # 간선 수 입력 받기 parent = [0] * (N+1) # 루트 노드를 저장할 자료구조 rank = [0] * (N+1) # 정점의 rank..