딥러닝 공부방

백준 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) # 부모 테이블 초기화 # 부모 테이블 상에서 자기 자신을 ..

백준 11657번 타임머신 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 파이썬 풀이 음의 간선이 존재하는 그래프 내에서 최단 경로를 찾는 문제입니다. 벨만-포드 알고리즘을 이용했습니다. # 최단 거리를 찾는 알고리즘 # 시간복잡도 O(VE) V: 정점 수, E: 간선 수 # 방향 그래프에서 음의 가중치를 지닌 간선이 존재할 때 사용 # 음의 순환이 있는 경우에는 최단 거리를 찾지 못함 # 작동 원리 # 시작 노드에 대해서 거리를 0으로 초기화, 나..

1753번 최단경로 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 문제 파이썬 풀이 다익스트라 알고리즘을 활용하여 최단 경로를 찾습니다. 다익스트라 알고리즘은 1) 모든 가중치가 양수, 2) 방향 그래프 인 경우 활용할 수 있습니다. 가중치가 음수인 경우는 벨만포드 알고리즘을 사용합니다. import sys import collections import heapq sys.setrecursionlimit(10**6) input = ..

9466번 텀 프로젝트 파이썬 풀이 그래프 내에 순환이 존재하면, 순환이 되는 부분 그래프에 속하는 정점이 한 팀을 이루는 문제입니다. 따라서 유향 그래프 내에 (1) 순환을 찾고, (2) 순환에 해당하는 정점들의 수 체크하여 풉니다. import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline K = int(input()) # test 수 def dfs(v): global result visited[v] = 1 # 방문한 정점 기록 traced.append(v) # 탐색 경로 저장 w = graph[v] # 다음 방문할 정점 if visited[w] == 1: # 방문 가능한 곳이 끝났는지 체크 if w in traced: # 탐색 경로에 ..

백준 1707번 이분 그래프 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 문제 풀이 코드 1) dfs 풀이 import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline # dfs def dfs(v, group): visited[v] = group # 방문한 노드에 group 할당 for i in graph[v]: if visited[i] == 0: # 아직 안 가본 곳이면 방문 i..

2150번 Strongly Connected Component www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 문제 풀이 import sys sys.setrecursionlimit(10**6) V, E = map(int, input().split()) visited = [0] * (V+1) # visitied 초기화 graph = [[] for i in range(V + 1)] # 빈 ..

2252번 줄 세우기 풀이 학생들의 키 비교 정보로 유향 그래프를 생성합니다. 그리고 위상정렬 알고리즘으로 풀었습니다. import collections v, e = map(int, input().split()) in_degree = [0] * (v+1) graph = [[] for i in range(v+1)] for _ in range(e): a, b = map(int,input().split()) graph[a].append(b) in_degree[b] += 1 result = [] q = collections.deque() for i in range(1, v+1): if in_degree[i] == 0: q.append(i) while q: node = q.popleft() result.appen..

백준 2606번 바이러스 풀이 dfs로 탐색하고 탐색 결과의 개수를 출력하도록 풀었습니다. n = int(input()) m = int(input()) matrix = [[0] * (n+1) for i in range(n+1)] seen = [0] * (n+1) for _ in range(m): a, b = map(int, input().split()) matrix[a][b] = matrix[b][a] = 1 result = [] def dfs(v): seen[v] = 1 for i in range(1, n+1): if matrix[v][i] == 1 and seen[i] == 0: result.append(i) dfs(i) return len(result) print(dfs(1))

백준 1260번 DFS와 BFS DFS, BFS 탐색 알고리즘은 안보면 계속 까먹게 되네요..ㅎㅎㅎ 풀이 n, m, v = map(int, input().split()) import collections matrix = [[0] * (n+1) for i in range(n+1)] seen = [0] * (n+1) for _ in range(m): a, b = map(int, input().split()) matrix[a][b] = matrix[b][a]= 1 def dfs(v): seen[v] = 1 print(v, end=' ') for i in range(1, n+1): if matrix[v][i] == 1 and seen[i] == 0: dfs(i) def bfs(v): queue = collect..