요약
알고리즘은 어떤 종류의 문제를 풀 수 있는 정확한 방법이며, 일련의 작업을 정확하게 정의해 놓은 규칙들입니다.
B - 입문자, A - 숙련자
주제별 알고리즘
- Math
BBit Manipulation - set/get/update/clear bits, 2의 곱 / 나누기, 음수로 만들기 etc.B팩토리얼B피보나치 수B소수 판별 (trial division 방식)B유클리드 호제법 - 최대공약수 (GCD)B최소 공배수 - LCMB에라토스테네스의 체 - 특정수 이하의 모든 소수 찾기B2의 거듭제곱 판별법 - 어떤 수가 2의 거듭제곱인지 판별 (naive 와 bitwise 알고리즘)B파스칼 삼각형A자연수 분할A리우 후이 π 알고리즘 - N-각형을 기반으로 π 근사치 구하기
- Sets
B카티지언 프로덕트 - 곱집합BFisher–Yates 셔플 - 유한 시퀀스의 무작위 순열A멱집합 - 집합의 모든 부분집합A순열 (반복 유,무)A조합 (반복 유,무)A최장 공통 부분수열 (LCS)A최장 증가 수열AShortest Common Supersequence (SCS)A배낭 문제 - “0/1” 과 “Unbound”A최대 구간합 - “브루트 포스” 과 “동적 계획법” (Kadane’s) 버전A조합 합 - 특정 합을 구성하는 모든 조합 찾기
- Strings
B해밍 거리 - 심볼이 다른 위치의 갯수A편집 거리 - 두 시퀀스 간위 최소 편집거리A커누스-모리스-프랫 알고리즘 (KMP 알고리즘) - 부분 문자열 탐색 (패턴 매칭)AZ 알고리즘 - 부분 문자열 탐색 (패턴 매칭)A라빈 카프 알고리즘 - 부분 문자열 탐색A최장 공통 부분 문자열A정규 표현식 매칭
- Searches
- Sorting
- Trees
- Graphs
B깊이 우선 탐색 (DFS)B너비 우선 탐색 (BFS)B크루스칼 알고리즘 - 최소 신장 트리 찾기 (MST) 무방향 가중 그래프A다익스트라 알고리즘 - 한 점에서 다른 모든 점까지 최단 거리 찾기A벨만-포드 알고리즘 - 한 점에서 다른 모든 점까지 최단 거리 찾기A플로이드-워셜 알고리즘 - 모든 종단 간의 최단거리 찾기A사이클 탐지 - 유방향, 무방향 그래프 (DFS 와 Disjoint Set 에 기반한 버전)A프림 알고리즘 - 무방향 가중치 그래프에서 최소 신장 트리 (MST) 찾기A위상 정렬 - DFS 방식A단절점 - 타잔의 알고리즘 (DFS 기반)A단절선 - DFS 기반 알고리즘A오일러 경로 와 오일러 회로 - Fleury의 알고리즘 - 모든 엣지를 한번만 방문A해밀턴 경로 - 모든 꼭짓점을 한번만 방문A강결합 컴포넌트 - Kosaraju의 알고리즘A외판원 문제 - 각 도시를 다 방문하고 다시 출발점으로 돌아오는 최단 경로 찾기
- Uncategorized
패러다임별 알고리즘
알고리즘 패러다임 이란, 알고리즘이 주어진 문제를 해결하기 위해 채택한 기초가 되는 일반적인 방법 혹은 접근법입니다. 알고리즘이 해결하는 문제나 알고리즘의 동작 방식이 완전히 다르더라도,알고리즘의 동작 원칙이 같으면 같은 패러다음을 사용했다고 말할 수 있으며, 주로 알고리즘을 구분하는 기준으로 쓰인다. 알고리즘이 일반적인 컴퓨터의 프로그램에 대한 개념보다 보다 더 추상적인 개념인 것처럼 알고리즘의 패러다임은 명확히 정의된 수학적 실체가 있는 것이 아니기 때문에 그 어떤 알고리즘의 개념보다도 훨씬 추상적인 개념입니다.
- 브루트 포스(Brute Force) - 가능한 모든 경우를 탐색한 뒤 최적을 찾아내는 방식입니다.
- 탐욕 알고리즘(Greedy) - 이후를 고려하지 않고 현재 시점에서 가장 최적인 선택을 하는 방식입니다.
B점프 게임A쪼갤수 있는 배낭 문제A다익스트라 알고리즘 - 모든 점 까지의 최단거리 찾기A프림 알고리즘 - 무방향 가중치 그래프에서 최소 신창 트리 (MST) 찾기A크루스칼 알고리즘 - 무방향 가중치 그래프에서 최소 신창 트리 (MST) 찾기
- 분할 정복법(Divide and Conquer) - 문제를 여러 작은 문제로 분할한 뒤 해결하는 방식입니다.
- 동적 계획법(Dynamic Programming) - 이전에 찾은 결과를 이용하여 최종적으로 해결하는 방식입니다.
B피보나치 수B점프 게임BUnique PathsB빗물 담기 문제 - trapping rain water problemA편집 거리 - 두 시퀀스 간의 최소 편집 거리A최장 공통 부분 수열 (LCS)A최장 공통 부분 문자열A최장 증가 수열AShortest Common SupersequenceA0/1 배낭 문제A자연수 분할A최대 구간합A벨만-포드 알고리즘 - 모든 점 까지의 최단 거리 찾기A플로이드-워셜 알고리즘 - 모든 종단 간의 최단거리 찾기A정규 표현식 매칭
- 백트래킹(Backtracking) - 모든 가능한 경우를 고려한다는 점에서 브루트 포스와 유사합니다. 하지만 다음 단계로 넘어갈때 마다 모든 조건을 만족했는지 확인하고 진행합니다. 만약 조건을 만족하지 못했다면 뒤로 돌아갑니다 (백트래킹). 그리고 다른 경로를 선택합니다. 보통 상태를 유지한 DFS 탐색을 많이 사용합니다.
B점프 게임BUnique PathsA해밀턴 경로 - 모든 점을 한번씩 방문AN-Queens 문제A기사의 여행A조합 합 - 특정 합을 구성하는 모든 조합 찾기
- 분기 한정법 - 백트래킹으로 찾은 각 단계의 최소 비용이 드는 해를 기억해 두고 있다가, 이 비용을 이용해서 더 낮은 최적의 해를 찾습니다. 기억해둔 최소 비용들을 이용해 더 높은 비용이 드는 해결법을 탐색 안함으로써 불필요한 시간 소모를 줄입니다. 보통 상태 공간 트리의 DFS 탐색을 이용한 BFS 탐색 방식에서 사용됩니다.
상세
알고리즘 (algorithm [ǽlɡərìðm])은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다.
알고리즘은 연산, 데이터 진행 또는 자동화된 추론을 수행한다. 산법(算法), 셈법, 계산 절차 등으로 번역되기도 한다.
명칭
알고리즘은 9세기 페르시아의 수학자인 무하마드 알콰리즈미(Muhammad al-Kwarizmi)의 이름을 라틴어화한 algorismus에서 따온 말이다.
정의
정지 문제의 결과로 알고리즘이 정지하는 데 걸리는 시간을 일반적으로 측정할 수 없다.
그러므로 알고리즘에 대해 단순한 직관을 만족하는 형식적인 정의는 불가능하다.
따라서 알고리즘의 공식적인 정의는 없다.
대부분의 알고리즘은 유한한 수의 규칙에 따라 구별 가능한 기호들을 조작하여 입력 정수에서 출력 정수를 생성하기 위한 일반화된 작업을 정의한다. 다음은 좋은 알고리즘의 특징이다.
- 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다.
- 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다.
- 타당성 : 구현할 수 있고 실용적이어야 한다.
- 입력 : 정의된 입력을 받아들일 수 있어야 한다.
- 출력 : 답으로 출력을 내보낼 수 있어야 한다.
- 유한성 : 특정 수의 작업 이후에 정지해야 한다.
- 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다.
구현
알고리즘은 자연어, 의사코드, 순서도, 프로그래밍 언어, 인터프리터가 작업하는 제어 테이블, 유한 상태 기계의 상태도 등으로 표현할 수 있다. 다음은 알고리즘 개발의 정형적인 단계이다.
문제 정의 → 모델 고안 → 명세 작성 → 설계 → 검증 → 분석 (복잡도 등) → 구현 → 테스트 → 문서화
알고리즘을 설계하는 기술에는 운용 과학의 방법, 설계 패턴을 이용하는 방법 등이 있다. 대부분의 알고리즘은 컴퓨터 프로그램으로 구현되지만, 전기 회로나 생물학적 신경 회로를 사용하기도 한다.
분류
- 구현 : 재귀적 알고리즘, 연역적 알고리즘, 결정론적 알고리즘, 근사 알고리즘, 양자 알고리즘 등.
- 설계 : 무차별 대입 공격, 분할 정복 알고리즘, 그래프 순회, 분기 한정법, 확률적 알고리즘, 리덕션, 백트래킹 등.
- 최적화 문제 : 선형 계획법, 동적 계획법, 탐욕 알고리즘, 휴리스틱 함수 등.
- 이론적 분야 : 검색 알고리즘, 정렬 알고리즘, 수치 알고리즘, 그래프 알고리즘, 문자열 알고리즘, 암호학적 알고리즘, 기계 학습, 데이터 압축 등.
Materials
[wikipedia](https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#:~:text=%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98(%EB%9D%BC%ED%8B%B4%EC%96%B4%2C%20%EB%8F%85%EC%9D%BC%EC%96%B4%3A%20Algorithmus,%ED%95%98%EA%B8%B0%20%EC%9C%84%ED%95%9C%20%EB%8B%A8%EA%B3%84%EC%A0%81%20%EC%A0%88%EC%B0%A8%EB%A5%BC)