본문 바로가기

컴퓨터공학/알고리즘 ˙ 자료구조11

[알고리즘] SAT(Satisfiability Problem) N개의 불리언 값 변수로 구성된 논리식을 참으로 만드는 변수 값들의 조합을 찾는 문제이다. 들어가기 앞서 P문제 : 문제의 해답을 다항 시간 내에 도출할 수 있는 문제의 집합 NP문제 : 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제의 집합 NP-hard : 다항 시간내에 해답을 구할 수 없는 문제 (대표적으로 P=NP 문제) NP-complete : NP-hard 이면서 NP인 문제 SAT-2 두 논리변수의 논리곱 및 논리합 연산식을 주어질 때, 식을 참으로 만드는 조합을 찾거나, 그런 조합이 없음을 찾는 것이 목표이다. SAT-2 문제에서 제시되는 식을 함의 그래프(implication graph)로 나타낼 수 있다. 각 논리변수(a, ~b, ~a 등등)는 그래프의 노드에 .. 2023. 6. 6.
[알고리즘] 강한 연결 요소 Strongly Connected Component | 코사라주 알고리즘, 타잔 알고리즘 강한 결합 방향 그래프의 모든 노드에서 다른 모든 노드로 가는 경로가 있는 경우, 이 그래프가 강하게 연결되어 있다고 한다. [1,2,5], [3,4,8], [6,7]이 강하게 결합된 컴포넌트(이하 SCC)이다. 1에서 출발해 2, 5에 도달할 수 있고, 2에서 출발해도 1, 5에 도착할 수 있고, 5에서 출발해도 1, 2에 도달할 수 있다. 하지만 강결합되지 않은 1과 3을 보자. 1에서 출발하면 3에 도달할 수 있다. 하지만 3에서 출발하면 1에 갈 수 없다. SCC를 찾는 알고리즘 SCC를 구하는 알고리즘은 크게 두 가지가 있다. 코사라주 알고리즘 강결합 컴포넌트를 찾는 유용한 방법이다.이 알고리즘에선 두 번의 DFS를 거친다. 첫 번째 탐색에서 그래프에 따라 노드 리스트를 만들고, 두 번째 탐색에.. 2023. 6. 3.
[알고리즘] 고오급 알고리즘 키워드 *블로그 주인만 알아볼 수 있음 주의* 삼진탐색으로 최솟값 찾기 함수의 최솟값이 x구간 [a,d] 구간 안에 있다고 하자. 구간을 같은 길이 [a,b], [b,c], [c,d]로 나누고 f(b)>f(c)가 성립함을 보인다. (미분) 합 최소화 abs(a1-x)+abs(a2-x)+ ... +abs(an-x) 의 최솟값으로 만드는 x의 최적해는 중앙값이다. 배열 원소가 짝수개라면 두 중앙값 사이 모든 값이 최적해가 된다. 트리의 지름 임의의 노드 a 선택, a에서 가장 먼 노드 b, b에서 가장 먼 노드 c를 구하면 b-c가 트리의 지름 트리 k번째 조상 찾기 ancestor(n,k) : n번 노드의 k번째 부모 가장 쉬운 방법은 k번 거슬러 올라가는 것인데 비효율적이다. k가 2의 거듭제곱인 모든 경우에 .. 2023. 6. 1.
[자료구조] 세그먼트 트리을 이용해 구간 합 구하기 구간 합 구간 합을 구하기 위해 사용되는 방법은 세 가지이다. 1. for문으로 해결하기 int ans = 0; for (int i=l; i 2023. 5. 21.
[알고리즘] 해시 충돌 해결 방법 | Hash Collision Seperate Chaining 추가적인 공간을 활용해 충돌을 해결한다. seperate 뜻에 맞게 Linked-List를 사용한다. 보통 헤드에 삽입한다. (테일에 삽입하면 테일까지 가는 시간이 걸리기 때문) 최악의 경우 하나의 해시에 데이터가 몰리면, 조회할 때 Linked-list를 탐색하는 시간이 걸리게 된다. Open Addressing Linear Probing 해시 충돌 발생 시 충돌이 발생하지 않을 때까지 해시를 linear 하게 탐색한다. 단, clustering 군집현상이 발생할 수 있다. Quadratic Probing 충돌 발생 시 해싱 함수에 특정 연산을 더해 새로운 해시를 제작한다. 보통 제곱연산을 쓰는데 추가적인 상수곱이나 제곱연산이 가능하다. 사진을 예시로 3번째 값 hf_q.. 2023. 5. 3.
[알고리즘] 배낭 알고리즘 (fractional 배낭, 0-1 배낭) 분할 가능한(fractional) 배낭 알고리즘 문제 도둑은 W만큼 들 수 있는 가방을 가지고 있다. W를 초과하는 보석을 담을 경우 가방이 찢어져 버리고 만다. 무게가 w고 가치가 v인 N개의 보석이 존재할 때 도둑이 훔칠 수 있는 보석의 최대 가치를 구하라. (보석은 분할 가능하다.) 그리디 알고리즘을 다룰 때 가장 자주 나오는 문제이다. 브루트포스를 사용해 훔칠 수 있는 보석의 모든 조합을 구할 수 있겠지만 N개의 보석의 모든 조합을 구하려면 O(2^N)의 시간이 걸릴 것이다. (보석을 훔친다 || 안 훔친다.) * N개 따라서 그리디하게 접근하면 효율적으로 해결할 수 있다. 무게 대비 가치가 높은 것부터 가방을 채우면 되지 않을까? N개의 보석을 v/w가 높은 순으로 정렬 후 W만큼까지만 훔쳤을 .. 2023. 4. 29.
[자료구조] AVL 트리, Red-Black 트리 AVL 트리 AVL트리는 발명가 Adelson-Velsky, Landis 이름 앞글자에서 따온 균형이진탐색트리이다. 스스로 균형을 잡는 트리로 처음 고안됐으며 말단 노드의 레벨 차이가 항상 1이하로 나는 트리이다. 노드 삽입, 삭제 시 균형이 깨진다면 스스로 조절하기 때문에 높이는 항상 logN이 보장된다. Red-Black 트리 아래 다섯 조건을 만족하는 트리를 레드블랙트리라고 한다. 마찬가지로 균형이진탐색트리이므로 높이는 logN이다. 모든 노드는 Red / Black 의 색을 가져야 한다. 루트 노드는 항상 블랙이다. NIL 노드는 항상 블랙이다. (value가 없는 말단 노드를 항상 가진다. NIL == Null Leaf) 레드 노드의 자식 노드는 항상 블랙이다. (블랙 노드는 상관 없다) 각 노.. 2023. 4. 28.
[알고리즘] 퀵 정렬과 병합 정렬 퀵 정렬 배열에서 기준값(Pivot)을 설정해 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치한다. 재귀적으로 분할해 정렬을 수행한다. pivot, left 인덱스와 right 인덱스를 설정한다. left값이 피봇보다 작으면 오른쪽으로 이동하고 크면 stop, right값도 똑같이 피봇보다 크면 왼쪽으로 이동하고 작으면 stop한다. 둘 다 stop인 경우 두 값을 swap한다. left 인덱스와 right 인덱스가 만날 때까지 수행하고, 그 인덱스를 기준으로 파티션을 분할해 정렬을 수행한다. 평균 시간복잡도는 O(nlogn)이지만 최악의 경우(오름차순 되어 있는데 내림차순으로 변경할 때) O(n^2)이다. 병합 정렬 https://i.namu.wiki/i/4JKVP3wRyMYaDKU_CBtFlxlJletKN.. 2023. 4. 26.

티스토리툴바