얄루의 개발일기🥑

✏소수 = 1과 자기 자신을 제외하고 나누어 떨어지지 않을 때 소수라고 한다. #소수 판별 함수(1은 소수가 아니기때문에 2이상의 자연수부터) def is_prime_number(x): #2부터 x-1 까지 모든 수를 확인하면서 소수 판별 진행 for i in range(2,x): #x가 해당 수로 나누어 떨어지는 경우 소수가 아니기에 False 리턴해준다. if x%i == 0: return False #자기 자신과 1로만 나누어지는 수이기 때문에 소수 True 리턴 return True ✏소수의 판별: 기본적인 알고리즘 성능 분석 - 2부터 x-1까지 모든 자연수에 대해서 연산을 수행해야 한다 - 모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(x)이고 x의 수에 비례해서 시간 복잡도가 늘어나게..

BFS 알고리즘 추가 정리 1. 노드 탐색은 ROOT NODE로부터 거리가 가까우면서 우선순위가 높은 것부터 방문해준다. 위의 그래프를 살펴보면 거리가 루트 노드에서부터 가까우면서 우선순위가 높은 순으로 탐색이 진행되는 걸 볼수 있다. 💥 BFS는 간선의 비용이 동일한 상황에서 최단거리를 찾는 목적으로도 사용된다.

# 사이클이 없는 방향 그래프에서 방향성을 거스르지 않도록순서대로 나열하는 것을 의미하고 이의 대표적인 경우는 선수과목을 고려한 학습 순서가 있다. # 사이클이 있으면 진입차수가 1이상이 되기 때문에 큐에 들어갈 수 없어서 수행이 불가하다. # 진입차수가 0이 될 때 큐에 삽입해서 다음 노드를 확인해주는 방식으로 실행 # 여러 답이 존재한다고 보는 이유는 위에 예시에서는 1 - > 2 -> 5 순서로 간 이유는 그냥 오름차순으로 했다고 가정했기 때문에 1 - > 5 - > 2.... 순으로 가도 됨 # 큐를 이용한 방법 / 스택을 이용하기 위한 방법 사용 가능 from collections import deque v,e = map(int,input().split()) #모든 노드에 대한 진입차수는 0으로..

# 사이클이 존재하지 않는 것을 의미하고 트리의 조건을 만족해서 신장 트리라고 한다. #일부 간선을 사용하지 않아도 괜찮도록 해주는 이유가 신장 트리의 사용되는 이유이다. # 두 개의 간선만 설치를 하더라도 모든 노드의 도달이 가능해지기 때문에 1 3의 간선을 없어도 됨 # 최소 신장 트리를 이용할 수 있는 알고리즘 = 크루스칼 알고리즘 # 간선을 기준으로 포함 미포함 여부를 결정한다. #특정 원소가 속한 집합을 찾기 def find_parent(parent,x): # 루트 노드를 찾을 때까지 재귀 호출 if parent[x] != x: parent[x] = find_parent(parent,parent[x]) return parent[x] #두 원소가 속한 집합을 합치기 def union_parent(..

#특정 원소가 속한 집합을 찾기 #x = 노드번호 def find_parent(parent,x): #루트노드를 찾을 때까지 재귀호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] #두 원소가 속한 집합을 합치기 def union_parent(parent, a, b): a = find_parent(parent,a) a = find_parent(parent,b) if a 합집합 연산 수행 union_parent(parent,a,b) if cycle: print("사이클이 발생했습니다.") else: print("사이클이 발생하지 않았습니다.")

# 연결성을 통해 서로소 집합 관계를 알 수 있다. #특정 원소가 속한 집합을 찾기 # x = 노드번호 def find_parent(parent,x): #루트노드를 찾을 때까지 재귀호출 if parent[x] != x: return find_parent(parent, parent[x]) return x #두 원소가 속한 집합을 합치기 def union_parent(parent, a, b): a = find_parent(parent,a) a = find_parent(parent,b) if a

# 통로 = 간선 import heapq import sys input = sys.stdin.readline INF = int(1e9)#무한을 의미하는 10억 설정 def dijkstra(start): q =[] #시작 노드로 가기 위한 최단 거리는 0으로 설정하여 큐에 삽입 heapq.heappush(q,(0,start)) distance[start] = 0 while q: #큐가 비어 있지 않을 동안 반복 진행 #가장 거리가 짧은 노드에 대한 정보를 꺼내기 dist, now = heapq.heappop(q) if distance[now] < dist: continue #현재 노드와 연결된 다른 인접한 노드들을 확인 for i in graph[now]: cost = dist + i[1] #현재 노드를 ..

# 다익스트라보다 구현은 쉽지만 시간복잡도가 O(n^3)이다. #초기엔 인접한 노드만 확인해준다. INF = int(1e9) #노드 개수 간선의 개수 입력받기 n = int(input()) m = int(input()) #2차원 리스트(그래프 표현)을 만들고, 무한으로 초기화 graph = [[INF]*(n+1) for _ in range(n+1)] #자기 자신에게 자기자신으로 가는 비용은 0으로 초기화 for a in range(1,n+1): for b in range(1,n+1): if a == b: graph[a][b] = 0 #각 간선에 대한 정보를 입력 받아, 그 값으로 초기화 for _ in range(m): #A에서 B로 가는 비용은 C라고 설정 a,b,c = map(int,input().s..

#우선순위 큐를 구현하기 위해서 사용하는 자료구조 = 힙 #힙 = 내부적으로 트리구조를 사용하기 때문에 삽입과 삭제에 있어서 O(logN) 시간만큼 걸린다. import heapq #오름차순 힙 정렬(Heap Sort) def heapsort(iterable): h = [] result = [] #모든 원소를 차례대로 힙에 삽입 for value in iterable: heapq.heappush(h,value) #힙푸시의 경우 특정 리스트에 어떤 데이터를 넣을 수 있다. #넣는 경우엔 그냥 들어온 순서대로 넣고 나올 때 가장 우선순위가 낮은 것부터 빼낸 #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 for i in range(len(h)): result.append(heapq.heappop(h)) #힙..

# 최단 경로는 DP로 구하는 것이 일반적이지만 다익스트라 최단 경로 알고리즘의 경우엔 그리디 알고리즘으로 분류 된다. # 3번 문항때문에 우리는 다익스트라 최단 경로 알고리즘을 그리디 알고리즘으로 분류한다. # 출발노드로부터 다른 모든 노드까지의 최단 노드 테이블을 구하는 문제가 출제될 가능성이 높고 모두를 출력하라는 경우는 코테에서 자주 나오지 않는다. # 1번 노드의 거리가 0인 이유는 자기 자신에게 돌아가는 거리가 0이기 때문이다. # 그리디 알고리즘에 속한다는 것 import sys input = sys.stdin.readline INF = int(1e9) #무한을 의미하는 값으로 10억을 설정 #노드의 개수, 간선의 개수를 입력받기 n, m = map(int,input().split()) #시..