차곡차곡.

N개의 인덱스를 가지는 배열 arr가 있을 때, 배열의 i~j 인덱스의 합을 구하려고 한다. 딱 한개의 구간합을 구하는 문제가 주어진다면 단순히 반복문에서 arr[i]~arr[j]까지의 합을 더해나가면 되겠지만, 주어진 배열에서 여러 구간합을 구해야한다면, 반복되는 작업을 피하기 위해 누적합을 저장하는 배열을 하나 만들어 놓는 것이 좋다. (i

먼저, 신장트리(Spanning Tree)란 방향성이 없는 N개 정점의 가중치 그래프에서 모든 정점을 연결하는 N-1개의 간선으로 구성된 트리를 말한다. 즉, 최소신장트리(MST: Minimum Spanning Tree)는 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 신장트리를 찾는 것이다. MST를 구할 때 대표적으로 쓰이는 프림(Prim), 크루스칼(Kruskal) 알고리즘에 대해 알아보자. 프림(Prim) : 정점을 선택/미선택 집합으로 구별하고, 선택된 정점 미선택된 정점 사이의 간선 중 가장 작은 간선을 택하면서 정점을 연결해나가는 방법의 풀이이다. => 정점 중심 풀이 [풀이 순서] 1. 임의의 정점을 하나 선택. 2. 선택된 정점들로부터 인접한 아직 선택되지 않은 정점까지의 가장 ..

알고리즘 문제를 풀다보면 자주 나오는 유형이 바로 최단경로(Shortest Path) 구하기 문제이다. 이 때 대표적으로 쓰이는 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), 플로이드-워셜(Floyd-Warshall)에 대해서 문제의 유형별로 어떤 알고리즘을 사용하면 좋을지, 그리고 각각의 특징과 풀이방법을 알아보자. 다익스트라(Dijkstra) : 다익스트라는 특정 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다. (single source shortest path problem) A->B의 최단거리 = A->b의 최단거리 + b->B의 가중치 임을 활용하여 문제를 푸는 방식으로, 대체로 다음과 같은 유형에서 사용한다. 시간복잡도 = O(ElogE) (E: 간선의 갯수) o..

- 최적화 문제 풀이에 쓰임 (= 최대값 or 최소값 구하기) - 현재 시점에서 최적이라고 생각되는 값을 선택하는 알고리즘. 하지만 전체 시점에서 추출된 해가 항상 최적이라는 보장이 없다. * 풀이 단계 1. 해 선택 : 가장 좋은 해 선택 2. 실행 가능성, 해 검사 : 선택한 해가 조건을 충족하는지 확인. 충족하지 않을 경우, 1번의 해에서 값을 수정한 뒤 다시 반복 * EX) 동전 거스름 돈 문제 [CASE1] 800원의 거스름돈을 500, 100 원 동전을 사용하여 줄 수 있는 최 소 동전의 갯수 구하기 1) 제일 적은 갯수로 주기 위해 가장 큰 금액의 동전 (500)을 선택. 2) 나머지 금액 (800-500) 은 100원 짜리 동전을 사용 ==> 답: 4개 (500원 1개 , 100원 3개) ..

소수 (Prime Number) 란, 1과 자기 자신으로만 나누어지는 숫자 (단, 1은 소수가 아님) (1) 특정 N 이 주어졌을 때, 이 숫자가 소수인지 아닌지 판별하기 : N이 n * m (n N: break li[i*j-2] = False answer = filter(lambda x: x == True, li) return len(list(answer)) [참고] velog.io/@koyo/python-is-prime-number [내가 보려고 적는 파이썬] 소수 판별(에라토스테네스의 체) 소수를 판별하는 방식에 대해 정리해보았다. 다양한 수를 판별하는 경우에 활용할 수 있는 에라토스테네스의 체도 알아두자. velog.io

N과 M의 숫자가 주어졌을 때, - 최대공약수(GCD) --> 유클리드호제법 : N(=큰수), M(=작은수) 가 있을 때 N%M를 X라고 한다. X가 0이 아니면 M%X 를 수행하고,,, 나머지가 0일 때까지 반복한다. 나머지가 0이 되었을 때 n%m 의 m 값이 최대공약수가 된다. - 최소공배수(LCM) --> 최대공약수를 통한 계산 : N = ab, M = bc 일때, 최대공약수는 b, 최소공배수는 abc 이다. 이 때 최소공배수는 NM (=ab^2c) 에서 최대공약수(b) 를 나눈 값과 같다. [Python코드] def solution(N, M): # 최대공약수 (gcd) ### 유클리드 호제법 ### N(=큰수), M(=작은수) 가 있을 때 N%M를 X라고 한다. ### X가 0이 아니면 M%X ..