Algorithm
1.알고리즘 정리 - 분할 정복을 이용한 거듭제곱
nk 을 계산할 때, n을 k번 곱하면 k번의 연산이 필요. k가 작다면 시간이 적게 걸리겠지만, k가 1012 같이 매우 큰 수로 주어지는 경우 시간 초과가 발생. 이 때, 분할 정복 거듭제곱을 이용하면 연산을 크게 줄일 수 있음. 일반적인 nk 시간 복잡도는 n을
2.알고리즘 정리 - 누적 합
특정 수열이 주어지고, 그 수열에서 특정 구간의 값을 구하는 쿼리가 반복적으로 들어올 때 주로 사용하는 개념.일반적으로 문제 풀이를 진행할 경우 O(n2)의 시간 복잡도이나, 누적 합을 사용하게 될 시 O(n)의 시간 복잡도를 가지게 된다.백준 10986https&#x
3.알고리즘 정리 - 투 포인터
리스트에 순차적으로 접근해야 할 때 두 개의 점 위치를 기록하면서 처리하는 알고리즘정렬되어있는 두 리스트의 합집합에도 사용된다.merge sort의 기초가 되기도 함.해당 알고리즘으로 단순 반복문 사용보다 메모리, 소요 시간을 아낄 수 있음.크게 두 가지의 포인터 사용
4.알고리즘 정리 - 연결 리스트와 런너
연결 리스트와 런너 연결 리스트 대표적인 선형 자료구조 중 하나. 다양한 추상 자료형 구현의 기반이 된다. 동적으로 새로운 노드 삽입 및 삭제가 용이함. 탐색에는 O(n) 시간 소요 시작, 끝 아이템 추가 및 삭제는 O(1) 소요 런너(Runner) 연결 리스트를
5.알고리즘 정리 - 스택과 큐
LIFO 구조 (Last In First Out)push() : 요소를 컬랙션에 추가pop() : 아직 제거되지 않은 가장 최근에 삽입한 요소를 제거FIFO 구조 (First In First Out)Deque, Priority Queue(우선순위 큐) 같은 변형 존재p
6.알고리즘 정리 - 데크, 우선순위 큐
양쪽에서 삭제와 삽입을 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 갖고 있는 추상 자료형(ADT).어떠한 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형ex) 최댓값 추출Heap 구조와 관련이 깊으며, Dijkstra 알고리즘 등에 영향을 끼침.p
7.알고리즘 정리 - 해시 테이블
해시 맵과 같은 표현키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형(ADT)을 구현하는 자료구조가장 큰 특징 : 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1).=> 덕분에 데이터 양에 관계 없이 빠른 성능 기대 가능임의 크기 데이터를 고점 크기
8.알고리즘 정리 - 그래프
그래프 탐색깊이 우선 탐색 (Depth First Search) \- Stack, 재귀로 구현백트래킹을 통해 뛰어난 효과를 보여줌너비 우선 탐색 (Breadth First Search) \- Queue로 구현그래프 최단 경로 구하는 문제백트래킹(Backtrackin
9.알고리즘 정리 - 최단 경로 문제
각 간선의 가중치 합이 최소가 되는 두 정점 사이의 경로를 찾는 문제노드 주변의 최단 경로만 택하는 대표적인 그리디 알고리즘 중 하나노드 주변을 탐색할 때 BFS 사용가중치가 음수인 경우에는 사용 불가능heap과 같이 쓰임(우선순위 큐)시간 복잡도 : O(ElogV)
10.알고리즘 정리 - 분리 집합
분리 집합(Disjoint Set) 서로 중복되지 않는 집합들로 나눠진 원소들에 대한 정보를 저장 및 조작하는 자료구조. 서로소 집합이라고도 불리움 [분리집합 규칙] 전체 집합 U A, B는 U의 분리 집합 A, B는 공통 원소를 가지지 않음 A, B의 합집합이 곧
11.알고리즘 정리 - heap
트리 기반의 자료 구조최소 힙 : 부모가 항상 자식보다 작거나 같음 최대 힙 : 부모가 항상 자식보다 크거나 같음힙은 좌우 정렬되어 있는 것은 아님단지 최대, 최소 힙에 따라 부모 - 자식간의 관계만 정의 되어 있음이진 힙(Binary Heap) : 자식이 둘인 힙최소
12.알고리즘 정리 - 트라이
트라이(Trie) 정의 검색 트리의 일종 일반적으로 키가 문자열인 동적 배열 or 연관 배열을 저장하는 데 사용되는 정렬된 트리 구조 NLP(자연어 처리)분야에서 문자열 탐색을 위한 자료구조로 널리 사용됨 전형적인 다진 트리(M-ary Tree)의 형태 찾고자 하는
13.알고리즘 정리 - 백트래킹(Backtracking)
정의 백트래킹 : 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시후보를 포기(백트랙, Backtrack)해 정답을 찾아가는 알고리즘 DFS는 백트래킹의 한 예 백트래킹은 주로 재귀로 표현됨. 최악의 경우 모든 경우를 다 거친 다음에 목적지에
14.알고리즘 정리 - 정렬
n번의 라운드로 이뤄진 상황에서, 각 라운드마다 배열의 아이템을 한번씩 쭉 살펴봄 => n번 검색연달아 있는 2개의 아이템의 순서가 잘못되어 있는 경우 두 아이템을 바꾼다=> O(n^2) 시간복잡도를 항상 가짐최선과 최악 모두 O(nlogn)의 시간복잡도를 가짐대부분의
15.알고리즘 정리 - 소수 판정[에라토스테네스의 체]
기존의 소수 판정