Algorithms/알고리즘 개념 (11) 썸네일형 리스트형 [알고개념] 10. 이분탐색 1. 이분탐색 이분탐색은 우리가 익히 잘 알고 있는 up down 숫자 맞추기 게임과 매우 유사하다. 예를 들어 3을 생각하고 1~100까지의 수 중에서 하나를 생각해서 맞춰보라고 하면 50 -> 25 -> 12 -> 6 -> 3 과 같은 식으로 2씩 나눠서 답을 구할 것이다. 이 과정이 바로 이분탐색이다. 이분 탐색을 하기 위한 전제 조건은 "데이터들이 정렬"되어 있어야 한다. 이분 탐색 코드는 아래와 같이 짤 수 있다. 재귀 호출을 이용해도 되고 while (l = l) { int mid = l + (r - l) / 2; // If the element is present at the middle if (arr[mid] == x) return mid; // If element is smaller th.. [알고개념] 9. Backtracking 1. 백트래킹의 개념 백트래킹은 완전 탐색의 한 종류로, 탐색을 하다가 중간에 답이 나올 수 없는 상황이 생기면 다시 이전 상태로 되돌려서 다른 답을 탐색하는 기법을 의미한다. 백트래킹 문제의 종류에는 아래 3가지가 존재한다. 1. Decision Problem – In this, we search for a feasible solution. 2. Optimization Problem – In this, we search for the best solution. 3. Enumeration Problem – In this, we find all feasible solutions. 백트래킹이 일반적인 재귀와 다른 점은 재귀는 "Base Case"에 도달할 때까지 호출을 반복하지만, 백트래킹은 가장 Best .. [알고개념] 8. 자료구조 1. Stack 스택은 FILO(First In Last Out) 구조로, 새로운 데이터가 기존의 데이터 위에 차곡차곡 쌓이는 자료구조이다. push X: 정수 X를 스택에 넣는 연산 pop: 스택에서 가장 위에 있는 정수를 빼는 연산 size: 스택에 들어있는 정수의 개수 empty: 스택이 비어있는지 여부 top: 스택의 가장 위에 있는 정수 2. Queue 큐는 FIFO(First In First Out) 구조로, 줄세우기와 같은 자료구조이다. push X: 정수 X를 큐에 넣는 연산 pop: 큐에서 가장 앞에 있는 정수를 빼는 연산 size: 큐에 들어있는 정수의 개수 empty: 큐가 비어있는지 여부 front: 큐의 가장 앞에 있는 정수 back: 큐의 가장 뒤에 있는 정수 3. Array, .. [알고개념] 7. Lazy Propagation 이 글은 백준에서 제공하는 공식 북을 참고하였습니다. https://book.acmicpc.net/ds/segment-tree-lazy-propagation 1. Lazy Propagation 기존 세그먼트 트리에서 하나의 값을 업데이트하는 것은 쉽게 가능했다. 리프 노드의 값을 업데이트한 후 그 부모들을 따라가서 업데이트만 해주면 되기 때문이다. 그러나 하나의 값이 아닌 "구간의 값을 변경"하는 경우에는 단순히 update 함수를 여러번 반복하기만 할 경우 무조건 시간초과가 난다. 대표적으로 https://www.acmicpc.net/problem/10999 이 문제를 보면 100만개의 수에 대해서 구간이 총 10000번 변할 수 있는데 하나하나 업데이트를 하면 최악의 경우 1000억번 update 함.. [알고개념] 6. KMP Algorithm 1. 문자열 찾기 알고리즘의 개요 워드 프로세서에서 단어 찾기와 같은 검색은 저장되어 있는 문자열을 대상으로 검색어가 포함된 문자열을 찾는 것이다. 검색이 가능하기 위해서는 검색어를 저장되어 있는 문자열의 부분 문자열과 비교하는 알고리즘이 필요하다. 예를 들어 ‘우리글’이라는 검색어를 ‘한글:⏘우리나라에서⏘창제된⏘우리글’ 이라는 띄어쓰기(⏘)가 포함된 18글자의 대상 문자열에서 검색한다고 가정해 보자. 가장 간단히 떠올릴 수 있는 방법은 ‘우리글’이 3글자이므로 대상 문자열을 3글자씩 잘라 1글자 씩 비교하는 것이다. ‘한글:’, ‘글:⏘’, ‘:⏘우’ 등과 같이 16개의 비교 대상을 만들고 이를 검색어와 각각 비교하여 모두 같은지 확인한다. 하나의 비교 대상을 확인하기 위해서는 3글자를 각각 비교해야 .. [알고개념] 5. Strongly Connected Component 이 글은 https://blog.naver.com/kks227/220802519976 을 참고하여 작성하였습니다. 1. SCC의 개념 SCC는 그래프 내의 모든 두 정점에 대해서 도달할 수 있는 경로가 존재하는 그래프를 의미한다. 아래 그래프에 대해서 {a, b, e}, {f, g}, {c, d, h}가 각각 하나의 SCC를 이룬다. SCC는 Maximal한 성질을 갖는다. 즉, 아래에서 c, d만 포함해도 경로가 존재한다는 성질은 만족되지만 h까지 포함해야 최대 크기의 SCC이기 때문에 반드시 h를 포함해야 한다. 2. 타잔 알고리즘 그래프에서 SCC를 찾는 알고리즘에는 코사라주 알고리즘과 타잔 알고리즘이 존재한다. 그 중에서 타잔 알고리즘을 알아보자. 그래프의 각 컴포넌트에 대하여 DFS를 돌려서 D.. [알고개념] 4. 트리 1. 트리의 기초 용어 Internal node: nodes with at least one child External node (Leaf): nodes without children Ancestor of a node: parent, grandparent, grand grandparent, and so on (including itself) Descendant of a node: child, grandchild, grand grandchild, and so on (including itself) Sibling : nodes that have the same parent Subtree : a tree that consists of a node of the original tree as the root an.. [알고개념] 3. 유클리드 호제법 1. 유클리드 호제법 두 수 m, n의 최대공약수 GCD(m, n) 를 구할 때 사용하는 알고리즘으로, 실제 계산기에도 이 알고리즘을 이용하여 구현되어 있다고 한다. 유클리드 호제법은 다음과 같이 작성할 수 있다. a를 b로 나눈 몫과 나머지를 각각 매개변수로 갖는 GCD 함수를 다시 호출한다. a를 b로 나눈 나머지가 0이면 b를 답으로 리턴한다. int GCD(a, b) { if (a % b == 0) return b; return GCD(b, a % b); } 이 때 a와 b의 대소관계는 따질 필요가 없다. a가 b보다 항상 커야 할 것 같지만 b가 a보다 클 경우 자동으로 GCD(a, b)를 호출하기 때문이다. 2. 유클리드 호제법의 역산 두 수 x, y에 대하여 GCD(x, y)를 구하는 유클리.. 이전 1 2 다음
