내가 기억하려고 만든 블로그 내가 기억하려고 만든 블로그

답안 예시 # 데이터의 개수 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) # 구간 합 계산(세 번째 수부터 번째 수까지) left = 3 right = 4 print(prefix_sum[right] - prefix_sum[left-1]) 작성한 답안 # 데이터의 개수 N과 데이터 입력받기 n = 5 m = [10, 20, 30, 40, 50] # 접두사 합 배열 계산 p = [0] * (n+1) sumNum = 0 for i in range(n): sumNum +..

답안 예시 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 and end < n: interval_sum += data[end] end += 1 # 부분합이 m일 때 카운트 증가 if interval_sum == m: count += 1 interval_sum -= data[start] print(count) 작성한 답안 m = 5 # 찾고자 하는 부분합M listNum = [1, 2, 3, 2, 5] # 전체..

다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘 답안 예시 import math n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별 # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외) array = [True for i in range(n+1)] # 에라토스테네스의 체 알고리즘 수행 # 2부터 n의 제곱근까지의 모든 수를 확인하며 for i in range(2, int(math.sqrt(n))+1): if array[i] == True: # i가 소수인 경우(남은 수인 경우) # i를 제외한 i의 모든 배수를 지우기 j = 2 while i * j

답안 예시 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 연산)의 개수 입력 받기 v, e = map(int, input().split()) parent = [0] * (v+1) # 부모 테이블 초기화하기 # 모든 간선을 담을 리스트와 최종 비용을 담을 변수 edge..

답안 예시 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드를 찾을 때까지 재귀 호출 if parent[x] != 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) # 부모 테이블 초기화 # 부모 테이블상에서, 부모를 자기 자신으로 초기화 for i in ..

답안 예시 # 특정 원소가 속한 집합을 찾기 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) 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번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다. ● 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 공중 미래 도시에서 특정 회사와 다른 회사가 도로로 연결되어 있다면, 정확히 1만큼의 시간으로 이동할 수 있다. ● 또한 오늘 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다. 소개팅의 상대는 K번 회사에 존재한다. 방문 판매원 A는 X번 회사에 가서 물건을 판매하기 전에 먼저 소개팅 상태의 회사에 찾아가서 함께 커피를 마실..