www.youtube.com/playlist?list=PLDV1Zeh2NRsBI1C-mR6ZhHTyfoEJWlxvq Union Find [Disjoint Set] Playlist Playlist of videos explaining the union find (disjoint set) data structure. www.youtube.com
N-Queen 문제를 해결하는 아주 효율적인 풀이이다 #include #define MAX 15 using namespace std; int col[MAX]; int N, total = 0; bool check(int level) // level을 받는 이유: 매번 0~N까지 다 검사할 수도 있지만, 어차피 현재까지 채워진 부분만 검사하면 되므로 level까지만 검사한다. { for (int i = 0; i i이기 때문) return..
트리에서(이진 트리가 아니어도 된다) 두 노드가 주어졌을 때 두 노드의 공통 조상들 중 가장 깊이 자리잡고 있는 조상을 찾는다. 방법1. 루트에서부터 노드A, 노드B까지의 경로를 구한다. 이렇게 구한 두 경로를 대조하며 처음으로 경로가 달라지는 지점을 찾는다. 방법2. (권장) blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221282478466&parentCategoryNo=&categoryNo=128&viewDate=&isShowPopularPosts=true&from=search 42. 최소 공통 조상(Lowest Common Ancestor) 이번 시간에 공부할 내용은 최소 공통 조상(Lowest Common Ancestor)입니다. 최소 공통 조상이란 트리..
두 문자열의 가장 큰 subsequence(부분수열)을 찾는다. ex. ABCABC, AABBCC -> ABC ex2. ABBCCA, BBCACA -> BBCC 더보기 (백준 9252) 참고: beginthread.tistory.com/142
A를 위해 B,C가 선행되어야 할 때 A,B,C를 위상정렬하면 B-C-A순 (혹은 C-B-A순)으로 정렬된다.
주의할 점: 경로 생성이 불가능할 떄 -1을 반환하게 만드는 과정(solve() 함수)이 생각보다 까다롭다. dist와 cost를 혼동하지 말자 - dist는 start에서 해당 노드까지의 거리로, 시작지점이 변하면 변하는 값이고, cost는 어떤 두 노드 사이의 거리로 프로그램 실행부터 종료까지 변하지 않는다. #include #include #include using namespace std; const int INF = 987654321; struct compNode { bool operator() (pair a, pair b) { return a.second > b.second; } }; int N, E; int n1, n2; // 지나야 하는 두 노드 int result = INF; vector..
BFS를 사용하되, 매 루프마다 한 칸씩 이동하는 대신, 갈 수 있는 만큼 최대한 한 방향으로 이동한다. 또 visited 칸을 저장하는 대신, 한 번 지나간 칸에 대해 해당 칸으로 가기 까지 필요한 거울의 갯수(count)를 기록한다. 즉 count != 0 이라면 한 번 이상 방문한 칸인 셈이다. BFS를 사용하기 때문에, 어느 칸에 처음 방문했을때 그 칸까지 가는 최단거리(여기서는 최소한으로 사용되는 거울 갯수)를 바로 알 수 있으며, 이러한 성질을 활용해 거울의 갯수를 축적시켜 최종적으로 목적지에 도달할때까지 길을 찾는 방식이다. (굉장히 다양한 풀이가 존재하지만 이 풀이가 가장 깔끔하고 직관적인 풀이법이라고 생각한다.) #include #include using namespace std; cha..
문제에서 찾아내기 어려운 부분들: 1. 매일매일 마다 백조를 시작지점부터 BFS를 돌려 길을 찾는 것은 낭비이다. 백조가 충돌한 얼음은 다음 날 녹는다. 때문에 이를 기록해두었다가 다음날 시작지점으로 사용하면 된다. 2. 얼음을 녹일 때는 "얼음을 기준으로 주변을 살피기" 가 아니라 "물을 기준으로 주변을 살피기"가 훨씬 효율적이다. 어차피 물과 닿아있어야 녹기 때문이다. 때문에 얼음의 위치를 기록하기보다는 물의 위치를 기록하는 편이 더 좋다. 참고: 인풋을 텍스트 형태로 받기 때문에 2d 그리드를 제작할 때 2d 벡터 대신 벡터 내에 string객체를 저장하는 방식을 사용한다. #include #include #include #include #include using namespace std; int ..
