live the life you love

가끔 알고리즘 문제에 나오는 소수계산을 위해 정리하는 글이다.소수란, 1과 자기 자신 이외에 약수를 가지지 않는 1보다 큰 자연수 이다. 1은 소수가 아니다 소수 판별 알고리즘은 대표적으로 두가지 방법으로 구현 할 수 있다. 일반적인 방법 우선, 반복문을 사용하는 것이다. 이 방법은 1개의 숫자가 소수인지 아닌지 판별하는데 사용하면 좋다. 여러 숫자를 소수 판별해야하는 경우는 아래 있는 에라토스테네스의 체가 더 유용하다. n이라는 숫자가 소수인지 확인하기 위해서는 2부터 n-1까지 나눠보면서 나머지가 0이 나오는 숫자가 한개도 없으면 n은 소수이다. 하지만 n-1까지 나눠보지 않더고 √n 까지만 확인해봐도 된다. 소스코드 import sys, math # 소수 판별 알고리즘 : 제곱근까지 구하기 def ..

문제를 풀다보면 배열을 시계방향으로 90도로 회전하는 문제들이 많다. ex) 백준 18808번 스티커 붙이기 예를 들어 3x4 리스트를 시계방향으로 90도씩 회전하면 아래와 같이 만들어진다. 총 4번의 회전이 끝나면 360도가 되어 원래 모양으로 되돌아 온다. 이를 파이썬에서는 2가지 방법으로 구현할 수 있다. 일반적인 방법 import copy _list = [[1,2,3], [4,5,6], [7,8,9], [10,11,12]] n = len(_list) m = len(_list[0]) result = [[0]* n for _ in range(m)] for i in range(n): for j in range(m): result[j][n-i-1] = _list[i][j] _list = copy.deep..

MST(Minimum Spanning Tree) - Kruskal MST는 최소 신장 트리로, 신장 트리를 의미하는 Spanning Tree는 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 이 중 가중치가 최소가 되는 트리가 최소 신장 트리 MST 이다. MST를 구현하는 방법에는 대표적으로 Prim 알고리즘과 Kruskal 알고리즘이 있다. 여기서는 Kruskal 알고리즘을 사용하였다. 통신망, 도로망, 유통망 등에서 길이, 구축 비용, 전송 시간등을 최소로 구축하려는 경우 사용된다 최소 스패닝 트리란? 스패닝 트리란 방향이 없는 그래프에서 모든 노드를 포함하면서, 순환되는 경로를 제거한 형태이다. 이 스패닝 트리에서 가중치의 합을 최소로 만드는 스패닝 트리를 '최소 스패닝 트리(Minim..

MST(Minimum Spanning Tree) MST는 최소 신장 트리로, 신장 트리를 의미하는 Spanning Tree는 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 이 중 가중치가 최소가 되는 트리가 최소 신장 트리 MST 이다. MST를 구현하는 방법에는 대표적으로 Prim 알고리즘과 Kruskal 알고리즘이 있다. 여기서는 Prim 알고리즘을 사용하였다. 통신망, 도로망, 유통망 등에서 길이, 구축 비용, 전송 시간등을 최소로 구축하려는 경우 사용된다 관련 문제 백준 1197번 최소 스패닝 트리 백준 1922번 네트워크 연결 기본 개념 하나의 정점에서 시작 간선의 가중치의 합이 최소이다 사이클이 포함되어서는 안된다. 시간 복잡도 O(ElogV) --> E : 간선의 개수, V : 정점의 ..

최장증가부분수열 Longest Increasing Subsequence 문제 예시) 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 관련 문제 백준 11055번 가장 큰 증가 부분 수열 백준 1965번 상자 넣기 백준 11053번 가장 긴 증가하는 부분 수열 LIS를 해결하는 방법은 두가지가 있다. N의 크기, 문제의 조건에 따라 아래 두 방법중 적절한 것을 사용하면 된다. 방법 1 : 이중 for-loop 시간복잡도 : O(n^2) dp 배열은 i 번째 원소가 가질 수 있는 최대증가..

Floyd-Warshall Floyd-Warshall은 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 다 구하는 것이다. 또한, 음수 가중치의 경우도 구할 수 있다. 알고리즘은 비교적 간단하다. 관련 문제 백준 11404번 플로이드 기본 개념 3중 for loop 사용 방향, 무방향 그래프 둘다 사용가능, 사이클이 생기면 안된다 음의 가중치 적용 가능 a->b로 가는 최단거리가 a->c->b보다 크면 그 값을 갱신한다 아래의 조건문이 핵심이다 if (arr[i][k] + arr[k][j] < arr[i][j]) { // k를 거쳐가는게 더 작으면 arr[i][j] = arr[i][k] + arr[k][j]; // arr[i][j] 값 갱신 } 시간 복잡도 O(n^3) floyd 구현 각 반복문의 ..

DijkstraDijkstra는 비용이 있는 그래프에서 최단 거리를 찾는 알고리즘이다.최단 거리와 관련된 그래프 알고리즘에는 대표적으로 다음의 3개의 알고리즘도 존재한다.다익스트라 알고리즘 : 하나의 시작점에 대해 다른 모든 정점들까지의 최단 경로를 구함벨만포드 알고리즘 : 음의 가중치 고려플로이드 와샬 알고리즘 : 모든 정점에 대해 다른 모든 정점에 대한 최단경로를 구함이 중 기본이 되는 다익스트라 알고리즘을 정리해보았다.참고자료 관련 문제백준 1753번 최단경로SWEA 1249 보급로기본 개념다익스트라 알고리즘은 하나의 시작점에 대해 최단 경로를 찾는다.다시 말해 A에서 시작하면 B,C,D,E,F에 대한 최단 경로를 구한다는 것이다.음의 가중치는 고려하지 않는다.(음의 가중치를 고려한 최단거리 그래프..

Union-Find Union-Find에 대해 알아보자 유니온 파인드는 자료구조 이므로 단독으로 쓰이기 보다, 알고리즘(크루스칼 등)에 활용된다 관련 문제 백준 1717번 집합의 표현 백준 1976번 여행 가자 기본 개념 유니온 파인드는 '집합'을 관리하는 자료구조이며 서로소 집합(Disjoint Set) 이라고도 불린다. 유니온 파인드를 활용하면 다음과 같은 작업을 할 수 있다. 원소 A와 원소 B가 같은 집합에 속하는지 확인 -- Find 함수 원소 A가 속한 집합과 원소 B가 속한 집합을 병합 -- Union 함수 방식 초기화 for (int i = 0; i n >> m; for (int i = 1; i n1 >> n2 >> cost; graph.push_back({cost,{n1,n..

우선순위 큐 사용자 정의 비교함수 작성 우선순위 큐에 넣어서 비교해야할 요소가 3개 이상 있을 경우, 연산자 오버라이딩을 해야 한다. 이 때, 중요한 것은 단순히 리턴타입이 단순히 bool 인 함수를 만드는 것이 아닌 연산자 오버라이딩이다. struct INFO{ int y; int x; int z; }; struct cmp{ bool operator()(INFO a, INFO b){ if(a.y == b.y){ if(a.x == b.x){ return a.z b.x; // x는 오름차순 } return a.y < b.y; // y는 내림차순 } }; int main() { priority_queuepq; pq.push({1,2,3}); pq.p..

순열, 조합은 정말정말 많이 나오는데 cpp의 stl 라이브러리 중 next_permutation으로 구할 수 있다. 하지만 next_permutation은 N이 20만 넘어가도 터질 위험에 처한다.. 시간복잡도가 크기 때문이다. N이 10 언저리일때 쓰면 좋다. 재귀를 사용하여 DFS탐색을 통해 순열, 조합을 구하는 것이 가장 안전하고 깔끔하다.순열 구하기#include #include #include #define MAX 5 using namespace std; vectorarr; vectorresult; int visit[MAX]; /* 순열 구하기 */ void prt_permu() { for (int i = 0; i < result.size(); i++) { cout