본문 바로가기

Algorithms

 (42)
[알고개념] 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, ..
[PS] 백준 #19535. ㄷㄷㄷㅈ 문제 정보 난이도: 골드 III 문제 주소: https://www.acmicpc.net/problem/19535 이 문제를 푼 이유: 알고리즘 스터디 - 트리, dp 문제 어느 날, 트리를 물끄러미 보고 있던 동현이는 엄청난 사실을 하나 발견했다. 바로 정점이 네 개인 트리는 ‘ㄷ’과 ‘ㅈ’의 두 종류밖에 없다는 사실이다! 정점이 네 개 이상 있는 임의의 트리에 대해, 그 트리에서 정점 네 개로 이루어진 집합을 고르자. 전체 트리의 간선들 중 집합에 속한 두 정점을 잇는 간선만을 남겼을 때, 네 개의 정점이 하나의 트리 형태로 이어지게 된다면 ‘ㄷ’ 모양이거나 ‘ㅈ’ 모양일 것이다. 트리에서 ‘ㄷ’의 개수와 ‘ㅈ’의 개수를 각각 트리에서 ‘ㄷ’ 모양, ‘ㅈ’ 모양을 이루는 정점 네 개짜리 집합의 개수라고..
[PS] 백준 #3977. 축구 전술 문제 정보 난이도: 플래티넘 IV 문제 주소: https://www.acmicpc.net/problem/3977 이 문제를 푼 이유: 알고리즘 스터디 - SCC 문제 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A, B)로 표현한다. 모든 도현이의 팀 선수들이 이 움직임만을 따라서 이동한다면 승리하리라고 도현이는 확신한다. 도현이는 선수들에게 자신의 전술을 말해주며, 다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다. 그러나 도현이..
[알고개념] 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..

티스토리툴바