본문 바로가기

알고리즘33

[서평 23년- 24] 알고리즘 트레이닝(초록이) | 두 번째 읽음 독서기간_2023년 5월 26일~6월 2일 저자_안티 라크소넨 출간일_2019년 5월 9일 예전에 읽다가 어려워서 후반부에 포기했었다. 그때보다 실력이 상승해서 다시 읽어보고자 꺼내 들었다. 정확히는 PS에 관심이 생겼다고 해야 하나. 목차를 보니 딱 절반 읽었었다. 작년에 읽을 당시엔 코테용 알고리즘만 공부했어서 고오급 알고리즘이 머선 말이고 했는데 그래도 조금 읽힌다. 몰랐는데 종만북 다음 가는 알고리즘 대회 입문서라고 한다. 일명 ‘초록이’라 불리는 책이다. 실전용 ‘파랑이’도 있다. 다음엔 파랑이를 읽어보겠다. 모듈러 연산부터 기하까지 기본적인 수학 조차 몰랐다는 게 부끄럽기도 하다. 벡터를 코드로 구현하고 외적을 계산한다라 흥미로웠다. 특히 트리를 공부하면 할수록 재미있다. 그래프와는 다른 매력.. 2023. 6. 8.
[알고리즘] 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.
[백준] 2261번: 가장 가까운 두 점 | C++ 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 브루트포스로 O(N^2) 시간에 해결할 수 있지만, O(NlogN)으로 푸는 방법을 알아보고자 한다. 정답코드 1. x좌표 기준으로 오름차순 정렬한다. 2. 0번째와 1번째 거리를 최소 거리(min_d)라고 가정한다. 3. 현재 살펴보는 좌표가 i번째 (x, y)라고 하면 [x - min_d, x] 범위에 해당하는 좌표를 "더 가까울 수 있는" 좌표 후보에 추가한다. 4. [y - min_d, y + min_d] 에 해당하는 좌표.. 2023. 6. 5.
[백준] 2150번: Strongly Connected Component (타잔 알고리즘) | C++ 2150번: Strongly Connected Component첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정www.acmicpc.net 정답코드타잔 알고리즘은 크게 세 가지 경우로 나뉜다. 1. 아직 방문하지 않은 노드 → 방문한다. 2. 방문했지만 SCC가 아직 아닌 노드 → id값이 더 작은 걸 저장한다. 3. 방문했고 SCC가 형성된 노드 → through 한다. 이런 경우를 거치고 현재 노드(id[cur]) id값과 저장된(remember) id 값이 같으면 스택에서 현재 노드를 만날 때까지 pop한다. 2번, 3번 경.. 2023. 6. 4.
[백준] 2150번: Strongly Connected Component (코사라주 알고리즘) | C++ 2150번: Strongly Connected Component첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정www.acmicpc.net 정답코드이론 공부한 거로 직접 구현해서 최적화된 코드가 아닐 수도 있습니다. 1. 정방향 그래프와 역방향 그래프 입력 받기 2. 첫 번째 정방향 DFS 수행 3. 노드 리스트 얻음 4. 두 번째 역방향 DFS 수행 5. SCC 출력 #include #include #include #include #include #define MAX 10001 #define fse(A,B,C) for(int i.. 2023. 6. 4.
[알고리즘] 강한 연결 요소 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.
[알고리즘] 분할정복으로 거듭제곱 최적화하기 프로그래밍에서 거듭제곱을 구하는 방법은 크게 세 가지이다. pow 내장함수 사용하기 double 실수 자료형을 사용해 거듭제곱을 반환하는 방법이다. 하지만 지수가 매우 클 때 정확성의 문제가 발생한다. 그 문제는 아래 글에서 확인 가능하다. C++ 기준 pow에 관한 글이다. 2023.04.30 - [TIL] - [C++] pow함수 double 형의 정확성 문제 [C++] pow함수 double 형의 정확성 문제 https://www.acmicpc.net/problem/1740 1740번: 거듭제곱 3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다. 이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 oozoowos.tis.. 2023. 5. 30.

티스토리툴바