yeongminb의 PS 블로그

비트마스크 알고리즘 $(Bit Mask)$은 0,1로만 이루어진 이진수를 사용하여 집합과 같은 자료구조를 표현하는 알고리즘이다.  AND연산이나 OR, XOR과 같이 기본연산만 사용하기 때문에 대부분 $O(1)$ 으로 구현되어 시간적으로도 효율적이고, 배열을 사용하지 않기 때문에 메모리 측면에서도 효율적이다.  1. 기본 연산 비트마스크에 사용되는 대표적인 기본 연산자는 AND$(\space \& \space)$, OR$(\space | \space)$, XOR$(\space \sim \space)$ , NOT$(\space \wedge \space)$, Shift$(\space  1) AND -> 모두 1일 때만 1AND10110000 2) OR -> 1이 존재하면 1OR10111010 3) XOR -..

SCC는 모든 정점에서부터 모든 정점까지로의 경로가 존재하는 그래프를 의미한다. 주어진 그래프에서 SCC들을 찾아내는 알고리즘은 타잔 알고리즘과 코사라주 알고리즘이 있다. 아직 정확히는 모르지만 타잔 알고리즘이 더 활용도가 높다고 하므로 타잔 알고리즘을 공부했다.  1) 타잔 알고리즘의 동작기본 원리는 dfs와 같다. 어떤 정점에서 시작해 dfs를 하는데 방문하는 정점마다 서로 다른 idx를 부여한다.  dfs 결과 자기 자신의 idx가 나온다면 cycle(SCC)가 존재한다는 것을 알 수 있다. 2) 타잔 알고리즘의 구현구현은 dfs와 stack을 이용하여 한다.1> dfsint v, e, id;int d[MAX];int sccNum; int sn[MAX]; vector a[MAX];bool finis..

Segment Tree는 어떤 배열에서 구간에 관한 정보를 저장해 놓는 자료구조이다. 누적합 배열을 사용할 때에는 $O(N)$으로 비교적 빠르긴 하지만 배열의 원소를 교체할 때에도 $O(N)$이므로 원소를 교체하는 쿼리가 많이 주어지는 경우에는 시간초과가 나기 쉽다.  반면에 Segment Tree는 이진트리의 형태의 자료구조이므로, 원소 교체나 구간합을 구할 때의 시간복잡도가 $O(logN)$으로 매우 빠르다. 1. Segment Tree의 구조  위 그림은 {1,9,3,8,4,5,5,9,10,3,4,5}라는 배열에 대한 구간합을 저장한 'Segment Tree'를 나타낸 것이다. 이진트리 형식으로 구성되어있으며 어떤 노드에 적혀 있는 숫자는 자식 노드들의 적혀 있는 숫자들의 합이라는 것을 알 수 있다..

Topolgy Sort(위상 정렬)는 유향그래프에서 정점들의 순서를 정할 때 사용하는 알고리즘이다. 유향그래프에서 진입차수를 기준으로 쉽게 구현할 수 있다. 1) 위상 정렬의 동작위상정렬은 다음과 같이 동작한다.1) 진입차수가 0인 노드 선택한다.2) 1)의 노드와 연결된 모든 노드들의 진입차수를 1씩 뺀다.3) 1)의 과정을 반복한다. 2) 위상 정렬의 구현 진입 차수가 0인 노드들을 queue에 넣음으로써 구현한다. void topology(){ queue q; for(int i=1;i 여기서 $inDegree$ 배열은 각 노드들의 진입차수를 저장하는 배열이고, result는 위상정렬 결과 노드들의 순서를 저장하는 벡터이다.

Floyd Warshall 알고리즘은 다익스트라 알고리즘의 진화(?) 버전으로 가중치가 주어진 그래프에서 모든 정점으로부터 모든 정점으로까지의 최소 거리를 구하는 알고리즘이다. Floyd Warshall 알고리즘은 모든 거쳐가는 정점을 기준으로 DP처럼 동작해 구현이 매우 간단하다. 1) Floyd Warshall 알고리즘의 동작 floyd warshall 알고리즘은 다음과 같이 동작한다.let) $d[i][j] :=$ ($i$부터 $j$까지의 최소거리 배열)let) $graph[i][j] :=$ ($i$와 $j$를 연결한 간선의 가중치) -> 연결이 안될 경우 INF(∞)1) $d[i][j]$ 초기화 $$d[i][j] = \begin{cases}0 & i=j\\graph[i][j] & otherwise..

다익스트라 알고리즘은 양의 가중치만 있는 그래프에서 어떤 정점으로부터 모든 정점까지의 최소 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 최단거리를 구할 때 매우 유용해서 GPS등에서도 사용한다고 한다(정확히는 모르지만,,). 쉽게 설명되어있는 유튜브 영상 : https://www.youtube.com/watch?v=EFg3u_E6eHU  아주 예전에 다익스트라 알고리즘을 처음 알았을 때 아주 똑똑한 친구가 위의 영상을 추천해줘서 봤었다. 이해하기 쉽게 설명되어있어서 다익스트라 알고리즘을 배우려고 하거나 까먹었을 때 보면 좋은 영상이다.  1. 다익스트라 작동 과정다익스트라는 다음과 같이 작동한다.1) pair형태로 {0, 시작정점}을 priority queue에 넣는다.2) priority queu..

MST 는 Minimum Spanning Tree (최소신장트리)의 약자로 가중치가 있는 그래프에서 모든 가중치의 합이 최소가 되도록 하는 어떤 트리(정점이 $V$개일 때 간선이 $V-1$ 인 연결그래프)를 의미한다. 예를 들어서 아래의 그래프에서는 찐하게 칠해진 트리가 가능한 모든 트리 중에서 가중치의 합이 최소이므로 MST 가 된다. 주어진 그래프에서 MST 를 구하는 알고리즘은 대표적으로 $Prim's\space Algorithm$ 과 $Kruskal\space Algorithm$ 이 있다. $Kruskal\space Algorithm$ 에 대해 알아보자. 1) $Kruskal\space Algorithm$  의 동작 Kruskal 알고리즘은 다음과 같이 동작한다.1) 모든 간선을 가중치를 기준하여..

Union-Find 알고리즘은 서로소 집합(Disjoint-Set) 알고리즘 이라고도 한다. 어떤 노드들이 서로 같은 그래프에 속해 있는지(두 노드까지의 경로가 존재하는지) 판별하기 위해서 사용되며 그래프를 다룰 때 중요한 알고리즘 중 하나이다.  Union-Find 알고리즘은 자신의 부모 노드를 불러오는 알고리즘, 두 노드를 이어주는 알고리즘(Union), 두 노드가 같은 그래프에 있는지 확인하는 알고리즘(Find)으로 구성된다. 이 알고리즘들은 각 노드의 부모 노드를 기준으로 구현하고 보통 parent라는 일차원 배열에 부모 노드들을 저장한다. 예시)노드12345부모 노드12345  먼저 초기에 아무 간선도 없을 때에는 각 노드의 부모 노드를 자기 자신으로 지정해둔다. $O(N)$ 알고리즘1. Uni..

1. BFS와 DFS의 개념 1) BFS먼저 BFS는 영어로 풀어쓰면 Breath-First-Search로 너비 우선 탐색을 의미한다.  다음과 같은 그래프가 주어졌을 때 BFS의 방식으로 그래프 탐색을 어떻게 하는지 알아보자. 먼저 기준 노드를 잡아야한다. 기준 노드는 쉽게 말하면 탐색을 시작하는 노드을 의미한다. 편의상 1번 노드를 기준으로 탐색을 시작하자. BFS 로 탐색하면 아래와 같은 결과가 나온다.1 - 2 - 4 - 5 - 3 - 6 - 7 BFS는 기준노드와 거리가 가까운 노드들부터 탐색을 한다고 봐도 무방하다.   2) DFS다음으로 DFS는 Depth-First-Search로 깊이 우선 탐색을 의미한다.아까와 같은 그래프가 주어져있고 1번 정점부터 탐색을 시작한다고 할 때 탐색 결과는 ..

예전에 LIS알고리즘을 DP로 $O(N^2)$만에 구현하는 포스팅을 올린 적이 있다. 하지만 이 알고리즘을 쓰기엔 시간복잡도가 크다보니 시간초과가 나는 문제가 많다.LIS $O(N^2)$  이번 포스팅에서는 이분탐색을 활용한 $O(NlogN)$ LIS 알고리즘을 올려보려고 한다. 이분탐색을 써서 푸는 백준 문제는 아래 세 개가 있다.가장 긴 증가하는 부분 수열 2가장 긴 증가하는 부분 수열 3 가장 긴 증가하는 부분 수열 5  LIS 길이 구현 방법 외부 배열이나 벡터에서 각각의 숫자들의 lower bound를 구해 그 인덱스로 넣어주는 방식이다. 아래 그림은 LIS 이분탐색 과정이다. 이렇게 이분탐색으로 배열을 만들고 나면 크기 순서대로 숫자들이 정렬이 되어있다. 여기서 이 배열의 길이는 LIS의 길이..

백준 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net  오늘은 DP를 이용해 최장 증가 부분 수열의 길이를 구하는 코드를 구현해볼 것이다.최장 증가 부분 수열 : 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.$ex)$  $A..

PS를 좋아하는 사람이라면 한 번쯤은 Knapsack Problem에 대해 들어본 적이 있을 것이다. DP를 활용하는 대표적인 문제이기도 하고, 알고리즘을 공부하기에도 좋은 문제이다.Knapsack Problem :  주어진 물건들에 대해 그 가치와 무게가 주어져있을 때,  무게의 합이 담을 수 있는 최대 무게를 넘기지 않고 가치의 합이 최대가 되도록 배낭에 담기 위해서는 어떤 물건을 담아야하는가?자세한 설명  : Knapsack problem - WikipediaFrom Wikipedia, the free encyclopedia Problem in combinatorial optimization Example of a one-dimensional (constraint) knapsack problem: ..

배열을 다루다보면 일정한 기준으로 그 배열을 정렬해야하는 상황이 생긴다. 이럴 때 C++ STL 에서 제공하는 sort()를 이용하면 편하다. sort()는 기본적으로 헤더파일에 속해있다. 그래서 이 함수를 쓰기 전에 먼저 헤더파일을 가져와야한다. #include 1) 배열(array) 배열을 정렬할 때는 sort()를 아래와 같이 사용한다. sort(시작주소, 끝주소 + 1) 시작주소는 (배열의 이름) + (번지수) 로 표기한다. 예를 들어 arr라는 배열의 1번지부터 시작하고 싶으면 arr+1로 나타낸다. 끝주소는 (배열의 이름) + (번지수)+1 로 표기하고, 예를 들어 n-1번지는 arr+n으로 표현한다. 2) 벡터(vector) 벡터를 정렬할 때에도 배열과 비슷한 방식을 사용한다. sort(v...