For Programmer

소스 코드 #데이터의 개수 N과 데이터 입력받기 n =5 data = [10,20,30,40,50] #접두사 합(prefix Sum) 배열 계산 sum_value = 0 prefix_sum = [0] for i in data: sum_value += i prefix_sum.append(sum_value) print(prefix_sum) # [0, 10, 30, 60, 100, 150] 출력 #구간 합 계산(세 번째 수부터 네 번째 수까지) left = 3 right = 4 print(prefix_sum[right] - prefix_sum[left-1]) #70출력

소스 코드 n = 5 #데이터의 개수 N# m = 5 #찾고자 하는 부분합 M# data = [1,2,3,2,5] #전체 수열 count = 0 interval_sum = 0 end = 0 #start를 차례대로 증가시키며 반복 for start in range(n): # end를 가능한 만큼 이동시키기 while interval_sum = m 상태로 while문을 빠져 나온다. print(count) # 3출력

소스코드(시간복잡도 O(X)) def oldIs_prime_number(x): #시간복잡도가 X # 2부터 x의 제곱근까지의 모든 수를 확인하며 for i in range(2,x): #x가 해당 수로 나누어 떨어진다면 if x % i == 0: return False #소수가아님 return True #소수임 시간복잡도 개선하기 개선된 소스코드(시간복잡도 X의 1/2승) def newIs_prime_number(x): #시간복잡도가 N의 1/2승 # 2부터 x의 제곱근까지의 모든 수를 확인하며 for i in range(2,int(math.sqrt(x))+1): #x가 해당 수로 나누어 떨어진다면 if x % i == 0: return False #소수가아님 return True #소수임 print(ne..

소스 코드 from collections import deque #노드의 개수와 간선의 개수를 입력 받기 v,e = map(int,input().split()) #모든 노드에 대한 진입차수는 0으로 초기화 indegree = [0] * (v+1) #각 노드에 연결된 간선 정보를 담기 위한 연결 리스트를 초기화 graph=[[] for i in range(v+1)] #방향 그래프의 모든 간선 정보를 입력 받기 for _ in range(e): a,b = map(int,input().split()) graph[a].append(b) #정점 A에서 B로 이동 가능 #진입 차수를 1 증가 indegree[b] += 1 #위상 정렬 함수 def topology_sort(): result = [] #알고리즘 수행 ..

-> 신장트리 = 모든 노드가 연결되면서 사이클을 이루지 않는 그래프 -> 최소신장트리 - 신장트리중에 간선의 합이 최소인 신장트리 소스코드 # 특정원소가 속한 집합을 찾기 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) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b #노드의 개수와 간선(Union 연산)의 개..

시간 복잡도를 개선한 서로소 집합 자료구조 #특정 원소가 속한 집합을 찾기 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) b = find_parent(parent,b) if a < b: parent[b] = a else: parent[a] = b #노드 개수와 간선(Union연산)의 개수 입력 받기 v,e = map(int,input().split()) parent = [0] * (v+1) #부모 ..

문제1. 전보문제(다익스트라 알고리즘) 소스코드 import heapq import sys input = sys.stdin.readline INF = int(1e9) #무한을 의미하는 값으로 10억을 설정 #노드의 개수, 간선의 개수를 입력 받기 n,m = map(int,sys.stdin.readline().split()) #시작 노드 번호를 입력 받기 start = int(sys.stdin.readline()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for i in range(n+1)] #최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n+1) #모든 간선 정보를 입력 받기 for _ in range(m): a,b,c = ..

소스코드 INF = (1e9) #무한을 의미하는 값으로 10억 설정 #노드의 개수 및 간선의 개수를 입력 받기 n = int(input()) m = int(input()) #2차원 리스트를 만들고, 무한으로 초기화 graph = [[INF]*(10) for _ in range(10)] #자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in range(1,10): for b in range(1,10): if a == b: graph[a][b] = 0 #각 간선에 대한 정보를 입력 받아, 그 값으로 초기화 for _ in range(m): #A에서 B로 가는 비용은 C라고 설정 a,b,c = map(int,input().split()) graph[a][b] = c #점화식에 따라 플로이드 ..