ZUO LAB

알고리즘

수학적 알고리즘

소수 판별	에라토스테네스의 체
유클리드 알고리즘	모듈러 연산
확장 유클리드 알고리즘	거듭제곱
중국인의 나머지 정리

정렬 알고리즘

선택 정렬	버블 정렬
삽입 정렬	퀵 정렬
병합 정렬	힙 정렬
계수 정렬	기수 정렬

탐색 알고리즘

선형 탐색	이진 탐색
이진 탐색 트리	해시 탐색
삼분 탐색	(문자열) KMP 알고리즘
(문자열) 라빈-카프 알고리즘

그래프 알고리즘

(기본) 깊이 우선 탐색(DFS)	(기본) 너비 우선 탐색(BFS)
(최단 경로) 다익스트라 알고리즘	(최단 경로) 벨만-포드 알고리즘
(최단 경로) 플로이드-워셜 알고리즘	(MST) 크루스칼 알고리즘
(MST) 프림 알고리즘	(위상 정렬) 위상 정렬
(위상 정렬) 칸 알고리즘

동적 계획법

메모이제이션	탑다운 방식
바텀업 방식	피보나치 수열
배낭 문제	최장 공통 부분 수열(LCS)
최장 증가 부분 수열(LIS)	행렬 곱셈 순서 결정

그리디 알고리즘

동전 거스름돈 문제	회의실 배정 문제
최소 신장 트리(크루스칼, 프림)	허프만 인코딩

분할 정복 알고리즘

최근접 점 쌍 문제

행렬 곱셈 알고리즘

비트 마스킹

부분 집합 생성	비트마스크 DP
해밍 거리 계산

문자열 알고리즘

KMP 알고리즘	라빈-카프 알고리즘
아호-코라식 알고리즘	트라이(Trie)
접미사 배열	롤링 해시

기하 알고리즘

회전 방향 판별(CCW)	볼록 껍질(최소한의 다각형)
최근접 점 쌍(가장 가까운 두 점)

자료구조

기본 개념

배열(Array)	포인터
구조체(Struct)&클래스(Class)	템플릿

선형 자료구조

연결 리스트(단일,이중,원형)	스택(Stack)
큐(Queue)	덱(Deque)

비선형 자료구조

트리(Tree)

그래프(Graph)

해시&집합 자료구조

해시 테이블

집합(Set)&맵(Map)

고급 자료구조

비트마스크	트라이(Trie)
세그먼트 트리	펜윅 트리
유니온 파인드	스킵 리스트

STL

STL 컨테니어

STL 알고리즘

소수 판별

개요

분류 : 수학적 알고리즘

설명

소수를 판별하는 기본적인 방법은 2부터 n-1까지 모든 수로 나누어 보는 것이지만 비효율적이다. 시간복잡도 O(n)
그래서 n이 소수인지 판별하기 위해 2부터 sqrt(n)까지만 검사한다. 시간복잡도 O(sqrt(n))
n이 소수가 아니라면 n을 나눌 수 있는 두 개 이상의 약수가 반드시 존재한다.
즉 n=a*b 형태로 나타낼 수 있는 a와 b가 존재해야 하고, a와 b중 하나는 반드시 sqrt(n)보다 작은 것이 존재한다.

코드