알고리즘

에라토스테네스의 체중요한 포인트가 두개 있다. sqrt(n)까지만 탐색하는 것과, 소수 p를 발견하고 n까지 p의 배수들을 지울 때, p\*p부터 시작한다는 점이다.sqrt(n)까지만 봐도 되는 이유는, isPrime의 기본값이 true이기 때문이다. 따라서 우리는 합

실제로는 문제에 맞게 필요한 부분만 구현하거나, 변형해서 사용한다.아래서 작성할 코드들을 간결하게 하기 위해 필요한 기능을 대부분 구현해놓았다. (종만북)2차원 벡터이며, 잘 이해하면 n차원으로 그대로 확장이 가능하다.ccw(Counter Clock Wise)외적의 성

Convex Hull 알고리즘에서 사용할 클래스Graham Scan O(NlogN)볼록껍질에 포함된다는게 보장되기만 한다면 기준점 및 정렬 기준을 바꿔도 되지만, 신경쓸게 많다.정렬 기준을 제일 아래점중 제일 왼쪽점으로 하면 편리한 점이 많다. 기준점과 임의의 다른 점

segmentIntersect 코드 참고(선분 교차 여부 판별)기본 아이디어는, 외부의 한점 q와 p를 이은 선분이 다각형의 변과 교차하는 횟수가 홀수인지 짝수인지에 따라 내부 외부가 결정된다는 것이다. 외부의 점은 잡기 나름이다. 문제의 조건에 따라 다양하게 결정할

BASIC오른쪽에 1만 남기기 (최소 원소 남기기)log2(LSB) -> 오른쪽에 있는 0의 개수오른쪽 1만 지우기 (최소원소 지우기)결과과 0이라면 2의 거듭제곱이겠다.비트카운트 (1의 개수)내장 함수가 있다면 내장함수를 사용하면 된다. 하드웨어적으로 최적화가 되어있

문자열 s의 접미사들을 사전순대로 정렬한 것이다. 정확히는, 접미사들의 시작 인덱스들이 저장된다. 접미사들을 싸그리 저장할 수는 없기 때문에.. > Suffix Array구현 브루트포스 O(n^2logn) 말 그대로 idx번째부터 문자열을 포인터로 받아서 비교하

PS에서 사용하기 좋은 균형잡힌 이진검색트리 treap. 구현이 상대적으로 간편하다 > 구현

Range Minimum Query. 배열이 있을 때, 배열의 i~j의 최소값을 물어보는 쿼리이다. 구간에 관한 질의(query)문제의 대표격이다. 구간에 관해 다루는 알고리즘을 배우면서 처음 공부하게 되는데, 이 문제는 다양하게 응용할 수 있다. (최소값, 최대값,

트리의 LCA를 찾아보자. 깊이에 비례하는 시간이 걸린다.희소배열의 성질을 이용해 log N만에 lca 쿼리를 해결할 수 있다.같이 올릴 때 직전까지만 올리는 이유를 이해한다면 희소배열을 완벽히 이해한 것? 지금까지는 주어진 그래프 정보를 이용해 bfs로 트리를 만들

문자열 s에서 문자열 p를 찾는다고 하자. 여러개 문자열로 이루어진 문자열 집합에서, 특정 문자열 하나가 존재하는지 찾고 싶을 때 사용하는 알고리즘이다. 정렬 + 이분탐색을 사용한다면 이분탐색으로만O(N^2logN)의 시간복잡도가 걸리게된다. 하지만 트라이는 O(N).

모든 정점에 연결된 간선이 짝수개이고 모든 간선이 한 Componenet에 있으면 오이러 서킷이 존재함을 보일 수 있다.아이디어를 요약하자면, 남은 간선이 있으면 계속 그려나가는 식으로 trail을 그려보자. 어떻게 그려도 시작점 외의 다른 곳에서 끝나는 것이 불가능함

무향 그래프에서 한 정점, 그리고 그 정점과 인접한 간선들을 제거했을 때 그래프가 둘 이상으로 나뉘는 정점을 의미한다. 비슷하게, 간선이 없어지면 그래프가 둘 이상으로 나뉘는 간선을 절단선이라고 한다.관련문제BOJ 11266관련문제BOJ 11400BCC내 한 정점과 그

SCC 구현 타잔 알고리즘 BCC 구할 때와 비슷하게, 각 정점이 방문할 수 있는 정점 중, 가장 방문순서가 앞서는 정점을 반환한다. 만약 그게 본인 자신이라면, SCC를 끊어야 한다. 재귀 호출이 곧 스택이기 때문에, DFS호출순서 = 스택 저장순서이다. 스택을

$(a \\vee b)$ $\\wedge$ $(c \\vee d)$ ..$\\wedge$ $(\\sim a \\vee \\sim b)$같은 논리식을 만족시키는 진리표를 찾는것이 2-SAT 문제이다. 일반적으로 SAT문제는 NP군에 속하는 지수시간 복잡도를 갖는다.