딥러닝 공부방

백준 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..

프림 알고리즘(Prim Algorithm) 오늘은 프림 알고리즘에 대해 공부했습니다. 프림 알고리즘은 주어진 무방향 그래프내에서 MST를 찾는 알고리즘입니다. 프림 알고리즘은 다익스트라 알고리즘과 거의 유사하다고 생각합니다. 차이점은 프림 알고리즘은 인접 간선을 추출하여 우선순위 큐에 삽입할 때, 순환이 발생하면 안되므로 방문한 노드인지 확인을 하고 우선순위 큐에 삽입을 합니다. 파이썬 코드 import heapq import collections import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n, m = map(int,input().split()) # 노드 수, 간선 수 graph = collections.defaultdict(l..

백준 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..

크루스컬 알고리즘(Kruskal Algorithm) 가중치가 있는 무방향 그래프를 최소 신장 트리로 만드는 알고리즘입니다. 최소 신장 트리는 가중치가 최소인 순환이 없는 무방향 그래프 입니다. 순환이 없으므로 간선 수는 정점 수 - 1이 됩니다. 크루스컬 알고리즘은 Greedy Algorithm에 속하며, 매 번 순환이 되지 않도록 가중치가 가장 적은 다음 간선을 선택합니다. 시잔복잡도 O(ElogN) 작동 원리 (1) 간선을 가중치를 기준으로 정렬합니다. (2) 가장 가중치가 작은 간선(u, v)을 선택합니다. (3) union find 알고리즘을 통해 u와 v를 병합합니다. (4) union find 알고리즘은 각 정점을 분리 집합으로 만들고 서로 다른 집합에 속해있는 정점을 하나의 집합으로 병합합니..

백준 1717번 집합의 표현 www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 파이썬 풀이 union-find 알고리즘을 사용하여 풀었습니다. import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N, M = map(int,input().split()) parent = [0] * (N+1) # 부모 테이블 생성 for i in range(N+1): # 자..

1976번 여행가자 www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 파이썬 풀이 union-find 알고리즘으로 풀 수 있는 문제입니다. import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N = int(input()) # 노드 수 입력 받기 M = int(input()) # 정점 수 입력 받기 parent = [0] * (N+1) # 부모 테이블 초기화 # 부모 테이블 상에서 자기 자신을 ..