알고리즘
-
[백준] 1516 - 게임 개발알고리즘/백준 2024. 5. 11. 21:54
https://www.acmicpc.net/problem/1516 알고리즘다이나믹 프로그래밍 / 그래프 이론 / 위상 정렬 / 방향 비순환 그래프 설명예 ~ 전에 풀려다가 못 풀었었는데, 오랫만에 보니까 금방 풀었다.문제 내용부터 '나 위상 정렬' 이라고 말하고 있기 때문에, 그냥 위상 정렬 후 소요 시간만 잘 계산하여 주면 된다. [각 작업에 대한 최소 소요 시간] = [입력 간선으로 들어오는 노드들 중, 가장 늦게 끝나는(최대 소요 시간)] + [해당 노드의 작업 시간]위상 정렬 코드#include #include #include #include using namespace std;int N;int cost[501];int result[501]; //각 건물을 짓는데 필요한 시간int in[5..
-
[백준] 30689 - 미로 보수알고리즘/백준 2024. 5. 11. 21:34
https://www.acmicpc.net/problem/30689 알고리즘그래프 이론 / 그래프 탐색 / 깊이 우선 탐색 / 함수형 그래프설명이전에 풀었던 텀 프로젝트 문제와 비슷한 느낌이 난다.재귀를 통하여 구현해당 유형은 익숙하지가 않아 구현 실수가 많은 것 같다.이번 차례에 방문한 칸과 이전에 방문했던 칸을 체크하는 두 개의 vistied 배열을 사용하여 미로 내의 사이클을 찾는 문제만약 사이클을 발견하게 되면, 사이클을 이루는 칸 중 가장 비용이 작은 칸을 정답에 더해준다.코드#include #include #include #include #include #include #include #include #include using namespace std;int N, M;string arr[200..
-
[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)을 사용해서 문자열에서 특정 패턴과 일치하는지 찾..