기본 알고리즘 썸네일형 리스트형 네트워크 플로우 네트워크 플로우의 기본 정의는 위키에 나와있듯, 'In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge.' 즉, 유향 그래프이고 가중그래프 G 가 각각의 노드를 연결한 에지들의 유량을 통해서 문제를 모델링하는 과정인 셈이다. 실제로, 네트워크 플로우 문제는 직접 봐서는 네트워크플로우로 풀어야 하는건가? 라고 알 수 있을 만큼 직관적이지 않다. (물론 내공이 쌓이면.. 더보기 이분탐색 'N개의 배열안에 특정 M이라는 숫자가 존재하는지 알아내라' 라는 문제를 처음 봤을 때,단순히 "배열 인덱스를 하나씩 증가하면서 탐색하라는 거 아닌가?" 라고 생각할 수 있다. 하지만, 백준 1920 번 문제 https://www.acmicpc.net/problem/1920 와 같이 찾고자 하는 수의 범위가 크고, 배열의 크기 또한 큰 경우 시간초과가 날 수 있다. 이 경우 쿼리가 M개, 배열이 최대 N개 이기 때문에 O(NM) 이 발생하여 시간초과. 즉 다른 방법을 찾아보아야 한다. 이때, 방법을 절반을 나누어가면서(이등분) 탐색하는 건..? 이라는 접근을 통해 풀이해볼 수 있으며, 방법은 다음과 같다. 1) 배열을 우선 오름차순으로 정렬한다. 2) 현재 배열의 중심(MIDDLE) 을 파악한다. 3) .. 더보기 세그먼트 트리 (Segment Tree) 세그먼트 트리 Segment Tree 는 주어진 query 수행을 빠르게 하기 위한 이진트리 구조로, 트리를 만드는데 O(nlogn), (전체 메모리 사용량 O(nlogn)) 특정 query를 수행하는데 O(logn) 이 수행된다. 그러면 앞서 펜윅트리를 살펴보았는데, 세그먼트 트리와의 차이점은 무엇일까? 세그먼트 트리는 범위를 통해 나누어지기 때문에, 여러값을 동시에 업데이트할 수 있다. 세그먼트 트리의 경우 이진트리 구조로 아래와 같이 범위로 노드들이 쪼개져 깊이 내려가는 구조이다. 보통은 line sweeping 문제에 사용되고 이 경우 선분의 개수 n 만큼의 리프노드가 생성, 높이 logn 의 형태로 이진트리가 나타난다. 간단하게 그림으로 아래와 같이 나타남을 확인해볼 수 있다. 범위에 따른 SU.. 더보기 펜윅트리 (Fenwick Tree) 펜윅트리 Fenwick Tree 는 Binary Indexed Tree (BIT) 라고도 한다. 설명하기 위해, 대표적으로 사용되는 그림을 통해 이해해보도록 하자. 아래에 해당하는 배열은, 각 인덱스를 2진수로 나타내었을 때 마지막 1의 위치를 통해 현재배열 이전에 몇개의 배열을 포함할것인가를 파악할 수 있다. 예를 들어, 인덱스가 10인 위치에서 생각해보면, 10을 2진수로 나타내었을 때 1010(2) 즉 마지막 1의 위치가 2번째에 있기 때문에 현재 10의 위치에서 앞으로 1칸 총 2개의 배열을 포함하는 값이 위 그림에 나와있는 하늘색 10에 포함되게 된다. 12 까지의 SUM을 구한다고 한다면, 하늘색으로 칠해진 8과 12를 더하면 12까지의 SUM 을 구할 수 있다. 그렇다면, Segment Tr.. 더보기 RMQ RMQ = Range Minimum Query 보통 범위가 작게 나올 경우, Bruteforce 방식으로 O(n^2) (n은 배열의 길이) 으로 가능하지만, 배열의 범위가 큰 경우에 시간초과가 날 수 있다. 이러한 경우, 1) (전처리 O(n)) O(루트n)시간안에 쿼리를 수행 : 배열의 구간을 루트n으로 나누어 각각의 구간마다 최소값을 구한다. 2) 전처리과정에서 O(nlogn), O(1) 쿼리 수행 가능 : 이 경우 배열을 각 2의 승수 만큼의 인덱스 구간마다 정답을 모두 구해놓는 것으로 만일 RMQ(X,Y) (X~Y 인덱스 사이의 최소값) 를 구하기 위해서 RMQ(X,Z) 와 RMQ(P,Y) (P < Z 라는 조건) 를 구한 후 더 작은 최소값이 정답이 된다. 예를 하나 더 들자면 현재값에서 +1 .. 더보기 유클리드 호제법(GCD) 유클리드 호제법 은 최대공약수, 최소공배수를 구하는 외워두면 편리한 공식(?) 과도 같은 알고리즘이다. 자세한 설명은 https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95위키를 보면 이해할 수 있지만, 간단하게 설명하자면 A라는 숫자와 B 라는 숫자가 있을 때, 한 숫자를 다른 숫자로 모듈러 연산(%) 하다보면 한 숫자가 0이 되는 경우가 발생하고이때의 다른 숫자가 A,B의 최대공약수가 된다. 예시로 (88,42) -> (42, 4) -> (4, 2) -> (2, 0) 이때 2가 최대공약수. (88과 42의 최대공약수는 2) #include int gcd(int a, int b) { return a%b .. 더보기 DFS와 BFS DFS와 BFS 는 보통 함께 배우는 개념이므로, 기본 알고리즘에서도 같이 다루어보도록 한다. DFS는 깊이우선탐색(Depth-First Search), BFS는 너비우선탐색(Breadth-First Search) 이다. 깊이와 너비? 간단하게 글로 설명하기에는 이해가 안가실 분이 있을 수 있으니, 그림으로 표현해보았다. 첫번째 그림을 통해 DFS 를 설명해보겠다. 깊이우선탐색의 경우, 출발점에서부터 다른 한점으로 깊이를 늘려가면서 탐색하는 방식이다. 즉 현재있는 위치의 점에서 연결된 다른 위치의 점으로 하나씩 이동하면서 탐색한다. DFS와 BFS는 공통적으로 이미 방문한 지점에 대해서는 재방문하지 않도록 변수를 통해 판단하며 탐색한다. 여기서는 A를 출발점으로 가정한다. 물론 이 방식외에 B보다 C를 .. 더보기 아스키코드표 알고리즘은 아니지만, 기본적으로 많이 쓰이는 아스키코드표를 올려놓았다.알파벳 대문자처리나, 소문자 처리와 같은 유용하게 쓰이는 부분에 사용하면 좋을것같다 :) 출처 : http://cafe.naver.com/ilovenover/1990884 더보기 에라토스테네스의 체 "에라토스테네스의 체" 를 첫번째 기본 알고리즘으로 선택한 이유는 간단하다.지워나가는 규칙만 알면 손쉽게 풀 수 있기 때문, 우선 1의 배수란 모든 수를 의미하기 때문에, 에라토스테네스의 체는 2부터 시작한다.아래 그림과 같이 숫자 2부터 시작해서 2의 배수를 제거해나간다. (물론 이때, 2는 포함하지 않게된다. 2는 소수!) 그다음, 다음 수인 3부터 또 다시 지워지며 쭉~ 해당되는 N(임의의 수) 까지 진행되게 된다.물론 위에 그림처럼 같은 수를 중복해서 제거해 주어도 되지만, 최대한 중복된 계산을 피하기 위해서 우리는 visit라는 임의의 bool 변수를 이용하여 중복된 것은 건너 뛰도록 한다. 임의의 N 수에 대한 에라토스테네스의 체는 아래와 같은 소스코드로 작성가능하다. (문제 예시로 보려면, .. 더보기 이전 1 다음
