Q : Write a query to print all prime numbers less than or equal to 1000 . Print your result on a single line, and use the ampersand ( & ) character as your separator (instead of a space).For example, the output for all prime numbers would be: 2&3&5&7문제 : 1000 과 같거나 작은 모든 소수를 출력하는 쿼리문을 작성하시오. 한 줄에 출력하되 숫자간 구분은 문자 '&' 을 사용하시오. 예를 들어 10보다 작은 소수를 출력하면 2&3&5&7 이 출력되어야 합니다. 간단히 재귀 함수를 떠올려서 이를 쿼리문으로 바..
알고리즘
Convex Hull 알고리즘은 2차원 평면에 여러 개의 점이 주어졌을 때 모든 점을 포함하는 볼록 껍질을 이루는 점들을 구하는 알고리즘입니다. 이 알고리즘의 구현에는 CCW 알고리즘이 사용됩니다.이 알고리즘의 구현 방법은 Graham’s scan이라는 방법을 사용합니다. 이 방법의 순서는 다음과 같습니다.(1) 2차원 평면의 점들을 정렬하고 가장 아래에 있는 점 P0를 고르고 스택에 넣습니다.(여러 개일 경우 가장 왼쪽에 있는 점)(2) 해당 점과 나머지 점들의 기울기를 구해 x축과의 각도를 구합니다.(3) 해당 각도를 기준으로 오름차순 정렬합니다.(4) P0와 각도가 가장 작은 P1과 그 다음으로 작은 P2를 고릅니다. P0, P1, P2에 대해서 CCW 알고리즘을 사용하고 만약에 양수 값(반시계방향..
1. Network Flow란유량 그래프란 간선의 가중치가 정점에서 정점으로 보낼 수 있는 최대 유량을 의미하는 그래프입니다. 최대 유량이란 해당 간선을 통해 동시에 흘려보낼 수 있는 물의 최대치입니다. 이러한 유량 그래프에서 Source로 정의된 정점에서 Sink로 정의된 정점까지 최대 얼마만큼의 유량이 지나갈 수 있는지에 관한 문제를 Network Flow 혹은 Maximum Flow라고 정의합니다. 아래는 유량 그래프의 예시입니다.각 간선을 유한 번 사용할 수 있는 통로라고 생각하고, 한 사람이 통로를 지나가면 사용할 수 있는 횟수가 한 번 줄어드는 문제를 생각해봅시다. 이때 무한히 많은 사람들이 Source에서 출발할 때, 최종적으로 Sink에 도달할 수 있는 사람의 수는 최대 몇 명일까요? 사람..
슬라이딩 윈도우(Sliding Window) 알고리즘은 투 포인터(Two Pointers) 알고리즘과 유사하게 동작하지만, 두 개의 포인터 사이의 길이가 고정되어 있다는 차이점이 존재합니다.위의 그림과 같이 모든 영역을 고정된 영역을 만든 후, 한 칸씩 밀면서 테스팅 해보는 방법입니다.이를 통해 길이가 고정된 모든 연속 부분집합들의 누적합, 최댓값, 최솟값을 구할 수 있습니다.간단히 누적합을 생각해보면, 윈도우를 한 칸 밀 때마다 기존 윈도우의 합에서 윈도우의 오른쪽 방향의 값을 더하고 윈도우에서 빠진 한 칸을 빼주면 각 창마다의 누적합을 구할 수 있습니다.이 경우의 시간 복잡도는 O(N)이 됩니다.길이가 고정된 모든 연속 부분집합들의 최댓값을 구하는 방법은 우선순위큐(Priority Queue, 또는 ..
투 포인터(Two Pointers) 알고리즘은 주로 순차적 접근이 요구되는 조건 등의 특수한 경우에 사용되는 알고리즘입니다.예를 들면, 정렬된 두 배열이 주어질 때 두 배열을 하나의 정렬된 배열로 합치는 경우, 어떤 배열의 연속 부분집합(contiguous subarray)의 원소의 합이 k인 경우의 수를 찾는 경우 등이 있습니다.투 포인터 알고리즘의 기본 동작원리는 이름 그대로 두 개의 지점(포인터)를 옮겨가면서 구하고자 하는 답을 구하는 것입니다.정렬된 두 개의 배열 A, B가 주어집니다. 이를 정렬된 하나의 배열로 합치는 문제를 투 포인터 알고리즘으로 해결해보겠습니다.이미 정렬이 되었기 때문에, 각 배열의 0번지는 각 배열의 최솟값이 있습니다.합친 배열의 0번지에는 A[0]과 B[0]중 작은 값이 ..
1. 경우의수경우의 수란 '일어날 수 있는 사건의 가짓수'입니다. 예를 들어 정육면체 주사위를 던져서 나올 수 있는 경우의 수는 {1, 2, 3, 4, 5, 6}의 6가지가 있습니다. 이때 '정육면체 주사위를 던지는 사건'은 6개의 경우의 수를 가집니다. 이를 확장시켜보면, 정육면체 주사위 두 개를 던졌을 때 합이 3이 되는 경우의 수는 두 주사위의 눈이 (1, 2)거나 (2, 1)일 때의 2가지가 됩니다. 이는 ‘정육면체 주사위 두 개를 던졌을 때 합이 3이 되는 사건'은 2개의 경우의 수를 가진다는 말과 같습니다.N개의 경우의 수를 가진 사건 A와 M개의 경우의 수를 가진 사건 B가 있을 때를 생각해봅시다. 두 개의 사건은 따로 일어나거나, 동시에 일어날 수 있습니다. 먼저 두 개의 사건이 따로 일어..
플레인 스위핑(Plane sweeping)은 직각 도형의 넓이를 구할 때 주로 쓰이는 알고리즘입니다.작은 범위는 flood-fill 을 사용하여 배열을 원하는 격자만큼 그린 후, 도형의 넓이를 직접 배열에 칠해가며 해결할 수 있지만, 범위가 커진다면 메모리와 시간 모두 문제가 생기기 때문에 다른 방법을 찾아야만 합니다. 플레인 스위핑은 이를 해결할 수 있는 방법 중 하나입니다.먼저 2개의 직사각형의 그림자의 넓이를 구해보겠습니다. 먼저 직사각형은 왼쪽 아래와 오른쪽 위 두 점으로 주어집니다. 두 개의 직사각형은 겹친 부분이 있기 때문에, 단순 공식에 의한 직사각형 넓이의 합으로 구하기 어렵습니다.플레인 스위핑은 위 문제에서 사용되는 좌표들은 한정됨을 이용합니다.각 직사각형들은 4개의 꼭짓점을 가지고, 이..
CCW 알고리즘은 한 선과 한 점의 위치 관계를 구할 때 사용하는 알고리즘입니다. 한 선분 AB와 점 C가 일직선 상에 있는지, 반시계 방향에 있는지, 시계방향에 있는지를 알려줍니다. 이 알고리즘은 기하 문제를 푸는데 사용이 되며 이 알고리즘을 이용하는 알고리즘에는 대표적으로 Convex Hull이라는 알고리즘이 있습니다. 이 알고리즘의 구현 방법은 점 A, B, C에서 AB와 BC 벡터의 외적을 통해 음수 값이 나오면 시계 방향, 0값이 나오면 일직선, 양수 값이 나오면 반시계 방향으로 판단하는 것입니다. 두 벡터의 외적은 두 벡터 Vx={Xx,Xy}, Vy={Yx,Yy}라고 했을 때 Xx*Yy-Xy*Yx입니다. 따라서 점 A, B, C가 A(x1,y1), B(x2,y2), C(x3,y3)라면 CCW값..
두 그룹으로 구분된 정점과, 서로 다른 그룹의 정점을 연결하는 간선들로 이루어진 그래프를 이분 그래프(Bipartite Graph)라고 합니다. 그룹 A에 속하는 정점 Ai와 그룹 B에 속하는 정점 Bj를 연결하는 간선 (Ai, Bj)을 선택하는 것을 매칭이라고 합니다. 이때 모든 정점은 단 하나의 매칭에만 속해야 합니다. 즉, 선택한 모든 매칭은 같은 정점이 중복되어서는 안 됩니다. 최대 매칭이란 이분그래프에서 선택할 수 있는 매칭의 최대 개수를 의미합니다. 이러한 문제를 이분매칭(Bipartite Matching) 혹은 최대이분매칭(Maximum Bipartite Matching)이라고 합니다.위는 이분그래프의 예제입니다. 오른쪽 그래프에서 파란색으로 칠해진 것보다 많은 간선을 주어진 조건에 맞도록 ..
KMP 알고리즘은 문자열 탐색 알고리즘입니다. KMP는 Knuth–Morris–Pratt의 줄임말로 KMP 알고리즘을 제안한 Donald Knuth, Vaughan Pratt 그리고 James H. Morris의 이름을 따서 이름 지어졌습니다. 기본적으로 가장 간단한 문자열 탐색 알고리즘은 완전 탐색으로 찾았을 때, 문자열 M,N에 대하여 O(|M|*|N|)의 시간 복잡도를 갖게 됩니다. 하지만 KMP 알고리즘은 약간의 메모리 공간을 이용하여 불필요한 비교 연산 횟수를 줄여 시간 복잡도를 줄입니다.예를 들어 설명하자면 samsamsung이라는 단어가 있고 samsamsong라는 단어를 찾는다면 맨 앞부터 탐색하여 u와 o에서 차이가 발생하게 됩니다. 간단한 알고리즘 같은 경우 다음 2번째 문자인 a부터 ..
플로이드-워샬 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 정점 사이의 최단 거리를 구하는 알고리즘으로 O(V^3)의 시간 복잡도를 가집니다.하나의 정점으로부터 다른 모든 정점사이의 최단 거리를 구하는 다익스트라 알고리즘(Dijkstra Algorithm)과 유사하며 다익스트라를 모든 정점에서 동작시키면 플로이드-워샬 알고리즘과 똑같이 동작하지만, 플로이드-워샬 알고리즘이 훨씬 간결하게 구현됩니다. 또한 다익스트라 알고리즘은 음수 간선치가 있을 시 제대로 동작하지 않지만, 플로이드-워샬 알고리즘은 음의 사이클만 없다면 음수 간선치가 있더라도 잘 동작합니다.플로이드-워샬 알고리즘은 정점 N개의 그래프가 주어졌을 때, 모든 정점쌍 (i,j)에 대하여 k라는 경유지를 거쳤을 때, ..
벨만 포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 어느 한 정점에서 나머지 정점까지 거리를 구하는 알고리즘입니다. 하지만 다익스트라와는 다르게 음수 가중치를 갖는 그래프에서도 동작을 하며, 음수 사이클을 찾아내는 기능도 가지고 있습니다.이러한 장점을 갖는 대신에 알고리즘의 수행 시간은 일반적으로 다익스트라보다 느린 단점을 가지고 있습니다.이 알고리즘의 기본적인 아이디어는 다익스트라와 비슷합니다.dist배열을 만들어서 최단 거리에 근접하게 계속 갱신시켜주는 방식입니다.하지만 우선순위 큐를 이용하여 간선에 연결된 정점의 최단 거리를 갱신하는 것이 아니라, 모든 정점의 최단 거리를 구할 때까지 모든 간선들을 여러 번 확인하여 최단 거리를 구한다는 것이 차이점입니다.벨만 포드 알고리즘의 구현 방법은 다익스트..
다익스트라 알고리즘은 그래프의 한 노드에서 연결된 다른 노드들로 가는 최단 거리를 구하는 알고리즘입니다.만약 모든 노드 쌍간의 최단 거리를 구하고 싶다면 N개의 각 정점에 대해 해당 정점을 출발점으로 하는 다익스트라 알고리즘을 수행해야 합니다.이러한 상황에서는 이후에 다룰 플로이드 워셜 알고리즘 알고리즘이 다익스트라를 N번 수행하는 것보다 유효합니다.다익스트라 알고리즘은 한 노드에서 다른 노드로 가는 최단 경로를 구성하는 간선들은 항상 최단 거리를 갖는다는 아이디어를 기반으로 하며 이는 귀류법으로 간단하게 증명 가능합니다.다익스트라의 동작 과정에 대해서 설명하면, 너비 우선 탐색 방법과 비슷합니다.먼저, 해당 노드까지의 최단 거리를 저장할 dist 배열이 필요합니다.또한 이 값은 처음에 방문하지 않았다는..
서로소 집합(Disjoint-Set)은 집합, 혹은 그룹을 관리하는 효율적인 알고리즘입니다.각각의 그룹을 트리 구조로 관리하는 이 알고리즘은 크게 두 가지의 연산을 가집니다. find(x): x번 노드의 최고 조상(루트)을 찾는 함수link(x, y): x노드가 속한 그룹과 y노드가 속한 그룹을 합치는(잇는) 함수또한 위 연산들을 구현하기 위해 par[i]: i번 노드의 부모로 정의되는 배열을 가집니다.예를 들어 1~5번의 번호를 가진 사람이 있다고 합시다.처음에 5명의 사람들은 모두 각자 독립적인 1인 그룹이 됩니다.각 그룹을 정점으로 표현하면 아래와 같습니다.또한 초기 par배열은 다음과 같습니다.이 상태에서 1번이 속한 그룹과 2번이 속한 그룹을 합치는 link(1, 2) 연산을 수행해봅시다.두 정..
Binary Indexed Tree(또는 fenwick tree, 이하 BIT)는 Segment Tree와 비슷하게 구간에 대한 정보를 저장할 수 있는 자료구조입니다. 기본적으로 아래의 그림과 같은 1-based 구조를 가지며, 구간합 등을 알아내는데 사용됩니다.BIT는 위의 그림처럼 세그먼트트리보다 조금 더 단순화된 구조를 가지지만, 구간에 대한 정보를 [1,X]으로 알아낼 수 있다는 점이 다릅니다.위 그림의 2번지에 그려진 1번지~2번지의 박스는 [1,2]의 구간의 정보를 [2,2]에 가지고 있다는 것을 의미합니다. 마찬가지로 12번지는 [9,12]의 구간의 정보를 가지고 있는 것입니다. 이를 적절히 이용하여 원하는 구간의 정보들을 구하는 것입니다.BIT로 구간의 합을 알아보겠습니다.트리의 구성은 먼..
