알고리즘
-
[union find path compression] 아리스, 청소합니다 (Hard)알고리즘/백준 2024. 4. 21. 16:24
문제 - 아리스, 청소합니다 Easy 버전 https://www.acmicpc.net/problem/31404 31404번: 아리스, 청소합니다! (Easy) 첫 번째 줄에 방의 크기를 나타내는 $H, W$가 주어집니다. $(1 \le H, W \le 64)$ 두 번째 줄에 아리스의 처음 위치를 나타내는 $R, C, D$가 주어집니다. 아리스의 좌표는 $(R,C)$이고, 위쪽을 기준으로 시계 www.acmicpc.net - 아리스, 청소합니다 Hard 버전 (크기 빼고, Easy와 완전 동일) https://www.acmicpc.net/problem/31399 31399번: 아리스, 청소합니다! (Hard) 첫 번째 줄에 방의 크기를 나타내는 $H, W$가 주어집니다. $(1 \le H, W \le 1\..
-
최근 풀면서 재미있거나 기억나는 문제 모음.알고리즘/백준 2024. 4. 15. 22:39
알고리즘 : 깊이 우선 탐색, check 배열을 두 개를 돌리면서 사이클을 검사해야하는 문제(위상정렬로도 가능) https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 알고리즘 : DFS, BFS, 구현(섬의 높이를 어떻게 구해나갈지 생각하기가 힘들었음) https://www.acmicpc.net/problem/1109 1109번: 섬 첫째 줄에 높이가 0인 섬의 개수, 높이가 1인 섬의 개수, …, 높이가 M인 섬의 개수 까지 공백으로 구분해서 출력한다...
-
[선분 교차 판정] 선분 교차 2알고리즘/백준 2024. 4. 6. 23:22
https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net CCW 를 사용하여 두 선분의 교차 관계를 판정하는 문제이다. 행렬 연산 시, 오버플로우를 간과해서 계속 틀렸다. ㅇㅅㅇ... - AB 선분, CD 선분 간의 교차 판정 R1과 R2가 모두 0 인 경우 : 서로 직선에 위치한 관계, x와 y에 대한 겹치는지 판정 R1과 R2의 곱이 음수인 경우 : 교차 int R1 = ( A, B, C 에 대한 CCW) * ( A, B, D 에 대한 CCW); int R2 = (C, D, A 에 대한 CCW) * (C, D..
-
[Algorithm] CCW알고리즘/백준 2024. 4. 6. 23:13
Counter Clock Wise 점 A, B, C가 있을 때 3개의 점 A, B, C를 차례로 이은 직선의 모양을 알고자 할 때 유용한 기하 알고리즘이다. 세 점에 대해 다음의 3 가지 모양이 존재할 수 있다. 귀찮으니까 코드로 보자. AB와 BC 벡터를 구하고, 벡터를 Cross (외적) 연산하면 세 점 A, B, C의 관계를 알 수 있다. 반시계 방향 : 음수 시계 방향 : 양수 직선 : 0 #include using namespace std; struct xy { int y, x; }; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); xy A, B, C; cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C...
-
체비쇼프 거리알고리즘/Algorithm Theory 2024. 3. 24. 19:44
체비쇼프 거리 Chebyshev Distance 유클리드 거리와, 맨허튼 거리 외에도 체비쇼프 거리라는 것이 있다. 솔직히 특별한 거리는 아니고, 맨허튼 거리가 8 방향에 대해 적용되는 것이라고 보면된다. 노랑색 칸 부터 다른 칸들에 대해 체비쇼프 거리를 나타내면 다음과 같다. Flood Fill(BFS) 를 8 방향으로 돌려 얻거나, 격자의 좌표의 차이의 최대 값이 거리가 된다. strcut yx{ int y, x }; yx a, b; int distance = max(abs(a.x - b.x), abs(a.y - b.y)); https://www.acmicpc.net/problem/28452(체비쇼프 거리를 활용한 시뮬레이션 문제) 28452번: 탄막 게임 두 점 $A(x_1, y_1)$과 $B(x_..
-
라빈-카프, 접미사 배열, lcp 배열알고리즘/Algorithm Theory 2024. 3. 24. 04:40
- Hash(string to int) https://blog.joonas.io/143 문자열을 정수로 해싱하기 + 사전순 비교까지 (String to unique integer hashing) 문자열을 정수로?이 글에서 다루는 내용은, 문자열의 형태로 적혀있는 "112223"과 같은 문자열을 말하는 것이 아닙니다. 영어 소문자로만 이루어진 "aaabbb" 또는 대문자로만 이루어진 "ABCCDD" 같은 blog.joonas.io - RabinKarp https://junstar92.tistory.com/125 Rabin-karp(라빈 카프) 알고리즘 두번째로 살펴볼 문자열 탐색 알고리즘은 Rabin-Karp 입니다. 라빈카프 알고리즘은 해싱(Hashing)을 사용해서 문자열에서 특정 패턴과 일치하는지 찾..
-
세그먼트 트리 시리즈알고리즘/백준 2024. 3. 13. 14:22
각 구간에 대해 특정 해를 항상 가지고 있는 트리. 자료구조로 생각하고 풀이하면 편하다. 각 구간 ~ 에 대해 최소값/최대값/합/곱 ... 을 가지는 트리 - 구간 합 (기본) https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net - 최대 최소 값 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을..
-
세그먼트 트리 (Segment Tree)알고리즘/Algorithm Theory 2024. 3. 12. 13:48
- 일반적인 구간 합 계산 int arr[5] = {3, 2, 1, 5, 4}; arr에서의 2번째에서 4번째까지의 합 : 2 + 1 + 5 = 8 배열의 길이가 N 일 때, 일반적인 구간 합 계산으로는 O(N)의 시간 복잡도를 가진다. 만약 N의 길이가 조금만 커져도 해당 연산을 반복하게 되면, 매우 오랜 시간을 필요로 하게 된다.. 해당 경우, 세그먼트 트리를 사용하여, O(logN)의 시간 복잡도로 구간 합을 구할 수 있다. - 세그먼트 트리 해당 배열을 세그먼트 트리로 나타내면 아래와 같다. 트리는 노드는 9 개, 높이는 3인 이진트리 형태를 가진다. 루트 노드 : 총 합(전체 배열의 합) 리프 노드 : 배열의 각 원소 값 트리의 높이 : math.ceil(log2(N)) //ceil은 올림 함수..