PROGRAMMING/알고리즘
-
(라이님 블로그 대회 알고리즘 따라잡기 32) TriePROGRAMMING/알고리즘 2024. 8. 5. 12:23
오늘은 Trie에 대해 알아보았다. 늘 그렇듯 설명은 라이님 블로그 Trie를 참고하면 된다.이번 알고리즘은 내용도 직관적이고, 코드도 짧아 좋았다@@ #include #include #include using namespace std;constexpr int SIZE = 10; // 0-9까지 총 10개의 숫자struct Trie { unique_ptr child[SIZE]; bool isEnd; // 현재 노드가 전화번호의 끝인지 여부 bool hasChild; // 현재 노드가 자식을 가지고 있는지 여부 // 생성자 Trie() : isEnd(false), hasChild(false) {} // 전화번호를 트라이에 삽입하고, 일관성이 유지되는지 확인 bool insert(const..
-
(백준 4354번 문자열 제곱) (라이님 블로그 대회 알고리즘 따라잡기 31) KMP(Knuth–Morris–Pratt Algorithm)PROGRAMMING/알고리즘 2024. 8. 1. 11:36
라이님 블로그에서 아이디어를 가져와서 풀어보았다! https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220917078260&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList KMP 알고리즘(Knuth–Morris–Pratt Algorithm) (수정: 2019-09-01)KMPlayer가 아니다 안녕하세요. 한동안 그래프를 줄창 했듯이 이제부터는 문자열을 줄창 하게 될 겁니다...blog.naver.com늘 그렇듯 설명은 라이님 블로그를 참고! 이 문제에서 처음에 틀렸습니다가 뜨면 abcabca를 한 번 넣어보는 걸 추천한다. 정답은 1이지만 2가 나올 가..
-
(라이님 블로그 대회 알고리즘 따라잡기 31) KMP(Knuth–Morris–Pratt Algorithm)PROGRAMMING/알고리즘 2024. 7. 31. 11:08
오늘은 KMP 알고리즘에 대해 공부해보았다. 솔직히 개념 + 코드 이해하는데 좀 걸렸다...뭔가 직관적이지 않아서 이해가 단번에 되지 않았다..ㅠ 늘 그렇듯 설명은 라이님 블로그에 있다.(아휴 어려워) 그래도 보다보니 이해가 되는거 같기도 하다...^^#include #include #include using namespace std;int main() { string S, W; getline(cin, S); getline(cin, W); int N = S.length(); int M = W.length(); // Fail function computation directly in main vector fail(M, 0); // 0으로 초기화된 벡터 생성 fo..
-
(라이님 블로그 대회 알고리즘 따라잡기 30) LCA(Lowest Common Ancestor)PROGRAMMING/알고리즘 2024. 7. 29. 11:58
오늘은 LCA를 배워보았다. 그 전에 Sparse Table에 대해 알아두면 좋을 것 같아 Sparse Table에 대해서도 공부해보았다. 라이님 LCA 포스팅을 보다보니 Sparse Table이 나왔는데 전에 본 적이 없어서 이 참에 공부! Sparse Table에 대한 설명은 블로그를 참고하고, 아래는 아주 조금 보기 쉽게 고친 코드이다.#include using namespace std;const int MAX = 500001;const int MAX_D = 19; // 2^k >= MAX인 최소의 kint main() { // next의 크기가 너무 클 경우 vector>로 정의 int M, next[MAX][MAX_D]; // 정점 입력 scanf("%d", &M); for..
-
(라이님 블로그 대회 알고리즘 따라잡기 28) 디닉 알고리즘(Dinic's Algorithm)PROGRAMMING/알고리즘 2024. 7. 23. 09:49
https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220812858041&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList\ 디닉 알고리즘(Dinic's Algorithm) (수정: 2016-09-19)안녕하세요. 예고한 대로 더 빠른 시간복잡도의 최대 유량 알고리즘을 소개하러 왔습니다. 그런데, 본래는 ...blog.naver.com 시간복잡도 O(V^2E) 알고리즘인 이 알고리즘은 에드몬드 카프 알고리즘이 O(VE^2)이였던 알고리즘에 비해 빠른 알고리즘이다! 설명은 라이님 블로그를 참고할 것! 코드는 크게 BFS를 이용해 레벨 그래프를 구축하는 과정과..
-
(라이님 블로그 대회 알고리즘 따라잡기 26) 이분매칭(Bipartite Matching)PROGRAMMING/알고리즘 2024. 7. 22. 10:57
오늘은 네트워크 플로우의 특수한 케이스인 이분 매칭에 대해 배워보았다. 이론은 상당히 단순한데, 내용은 라이님 블로그에 자세히 설명되어 있다. https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220807541506&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 이분 매칭(Bipartite Matching)이번에 올릴 글은 네트워크 플로우 개념의 연장...은 아닌 것 같고, 유량 그래프의 아주 특수하면서 메이저...blog.naver.com 라이님이 알려준 코드를 살짝만 수정해서 사용하고자 한다.#include #include #include // m..
-
(라이님 블로그 대회 알고리즘 따라잡기 25) 네트워크 유량(Network Flow)PROGRAMMING/알고리즘 2024. 7. 16. 10:45
네트워크 유량에 대해 공부해보았다. 개념 자체는 어렵지 않은데 음의 유량 다루는 부분이 조금 생소했다. 아래 라이님 블로그에 아주 잘 기술되어 있으므로 정독하는 것을 추천!https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220804885235&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 네트워크 유량(Network Flow) (수정: 2019-08-14)안녕하세요. 그래프에 대해서 1차적으로 쓸 내용 중에서는 마지막 개념에 달했습니다. 그런데 마지막 개념...blog.naver.com ⭐ 플로우 그래프의 가장 큰 특징 : 간선의 용량!⭐ 어떤 길을..
-
(라이님 블로그 대회 알고리즘 따라잡기 24) 2-SAT(Satisfiability Problem)PROGRAMMING/알고리즘 2024. 7. 12. 11:36
라이님 블로그에서 이번에는 2-SAT(2-Satisfiability Problem)을 배워보았다.https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220803009418&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 2-SAT 문제(2-Satisfiability Problem) (수정: 2019-11-16)안녕하세요. 이번에 강의할 내용은 2-SAT(2-Satisfiability)이라는 좀 생소할 수 있는 내용입니다! 이...blog.naver.com 아직도 끝나지 않은 그래프 지옥...★ 코드는 저번 SCC 코드랑 비슷한 방식으로 작성해보았다.#inc..