딥러닝 공부방

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)] # 빈 ..

코사라주 알고리즘(kosaraju's algorithm) dfs를 활용하여 그래프 내의 ssc를 찾는 알고리즘 시간 복잡도 O(V+E) 정방향 그래프에서 dfs를 실행하여 post가 높은 정점이 sCc의 source가 되고, 역방향 그래프에서 dfs를 실행하여 post가 높은 정점이 scc의 sink가 된다. 찾은 source와 sink를 묶어 scc를 생성한다. 작동 원리 (1) 방향 그래프 내에서 dfs를 실행하여, dfs 탐색을 마친 정점을 stack에 삽입한다. (2) 역방향 그래프를 생성한다. (3) stack에서 정점을 추출하여, 역방향 그래프에서 dfs를 실행한다. (4) 방문하는 정점을 scc 에 삽입한다. (5) 탐색이 종료되면, scc (6) stack에서 방문하지 않은 정점을 추출하여..

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

위상 정렬 순환이 없는 유향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는것 알고리즘 동작 원리 1. 진입 차수가 0인 노드를 queue에 삽입. 2. 큐에서 노드를 하나씩 꺼내면서 아래의 과정을 진행 꺼낸 노드의 간선을 그래프에서 제거 진입 차수가 0인 새로운 노드를 queue에 삽입 파이썬 코드 from collections import deque # 노드의 개수와 간선의 개수를 입력 받기 v, e = map(int, input().split()) # 진입차수 0으로 초기화 in_degree = [0] * (v+1) # 빈 인접리스트 그래프 생성 graph = [[] for i in range(v+1)] # 방향 그래프의 간선 정보 입력 받기 for i in range(e): a, ..

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

안녕하세요! torch.bernoulli 함수를 활용해서 Stochastic depth 학습 하는 법을 알아보겠습니다. 이 포스팅은 stochastic depth 학습을 구현하는 법을 잊을까봐 기록합니다. 아래 class는 efficientnet에서 사용하는 bottlenet 입니다. class BottleNeck(nn.Module): expand = 6 def __init__(self, in_channels, out_channels, kernel_size, stride=1, se_ratio=4, p=0.5): super().__init__() self.p = torch.tensor(p).float() if stride == 1 else torch.tensor(1).float() self.residual..

안녕하세요! PyTorch로 Swish 함수를 정의해서 사용하는 법을 알아보겠습니다ㅎㅎ Swish 함수는 깊은 신경망에서 ReLU보다 좋은 성능을 나타내는데요, 실제로 EfficientNet은 Swish 활성화 함수를 사용하고 MobileNetV3은 Swish 함수를 수정해서 h-Swish 함수를 사용하고 있습니다. 이 Swish 함수는 파이토치 공식 문서에서 명령어를 제공하고 있지 않아 직접 정의해서 사용해야 합니다. 아래와 같이 Swish 함수 클래스를 정의할 수 있습니다. # Swish activation function class Swish(nn.Module): def __init__(self): super().__init__() self.sigmoid = nn.Sigmoid() def forwa..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 39. 코스 스케줄 leetcode 207. Course Schdule 문제입니다. leetcode.com/problems/course-schedule/ 풀이 코스를 그래프로 만들고, 그래프가 순환 그래프인지 판단하는 풀이입니다. def canFinish(self, numCourses,prerequisites): graph = collections.defaultdict(list) # 그래프 구성 for x, y in prerequisites: graph[x].append(y) traced = set() visited = set() def dfs(i): # 순환 ..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 35. 조합 leetcode 77. Combiantion 문제입니다. leetcode.com/problems/combinations/ 풀이 1. 제가 푼 풀이 def combine(self, n, k): result = [] def dfs(index, path): if len(path) == k: result.append(path) return for i in range(index, n+1): dfs(i+1, path + [i]) dfs(1, []) return result 2. 책에 나와있는 풀이 def combine(n,k): results = [] def ..