궤도

문제 풀이 myunji.tistory.com/350 [백준] 4803번 : 트리 문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근 myunji.tistory.com 이 문제에서 사이클을 찾는 코드를 작성하긴 했었다. 근데 이번 문제는 사이클이 생기는 지점을 정확히 찾아야 하기도 하고...해서 유니온 파인드로 풀 것이다. 달리말하면 4803번도 유니온 파인드로 풀 수 있단 뜻이다. 아무튼 유니온 파인드에서 사이클이 형성된다는 것을 알 수 있는 기점은 유니온 하려는 x와 y의 부모가 같을 때이다. 소스코드 #include #include using namespace std..

문제 풀이 myunji.tistory.com/367 [백준] 1717번 : 집합의 표현 문제 풀이 유니온 파인드로 푸는 문제다. 약...2년전 자료구조 시간에 배웠는데 그때 당시에는 아는 것도 없고 + 영어 강의고 + 기타 등등의 이유로 개념만 정말 간신히 익힌 것 같다. 지금 내가 myunji.tistory.com 이 문제랑 거의 유사한데 다만 입력값이 string이라는게 조금 까다로울 뿐이다. string으로 들어온 입력값을 int처럼 사용할 수 있게 map을 사용할 것이다. Fred - 1 Barney - 2 Betty - 3 Wilma - 4 이런식으로 저장하면 parent[4]는 Wilma의 부모 노드인 뭐 그런거다. 소스코드 #include #include #include #include us..

문제 풀이 유니온 파인드로 푸는 문제다. 약...2년전 자료구조 시간에 배웠는데 그때 당시에는 아는 것도 없고 + 영어 강의고 + 기타 등등의 이유로 개념만 정말 간신히 익힌 것 같다. 지금 내가 설명하기엔 ssungkang.tistory.com/entry/Algorithm-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find [Algorithm] 유니온 파인드(Union - Find) 유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 합니다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 ssungkang.tistory.com 이 분이 정말 완..

문제 풀이 한 물건에 대해 우리는 그 물건을 넣거나 넣지 않는 2가지 조치만 취할 수 있다. 근데 물건들은 최대 30개까지 들어올 수 있고 이 경우 2^30회의 연산을 해야한다. 이럴 때 사용하는 알고리즘이 meet in the middle이라고 한다. 난 처음 들어봤다. www.secmem.org/blog/2019/03/08/meet-in-the-middle/ meet in the middle Meet in the middle meet in the middle 은 절반 크기의 비슷한 문제를 두 번 해결한 결과를 통해 본 문제를 해결함으로서 문제 해결에 소요되는 시간 복잡도의 향상을 꾀하는 방법입니다. 저 말만 들으면 www.secmem.org 이런 설명이 있다. 그니까 배열을 둘로 쪼개서 연산을 하란 ..

문제 풀이 그냥 모든 배열을 탐색하면서 풀면 시간복잡도가 O(n^2)이 나와서 시간초과가 뜬다. 그러니까 투 포인터를 써야한다. myunji.tistory.com/362 [백준] 2470번 : 두 용액 문제 풀이 이 문제는 시간제한이 있기 때문에 모든 쌍을 찾는 O(n^2)의 시간 복잡도로는 풀 수 없다. 그래서 O(n)의 시간복잡도인 투 포인터 알고리즘을 사용해야 한다. 투 포인터 알고리즘을 사용 myunji.tistory.com 이 문제에서는 양방향에서 좁혀왔는데, 이번엔 한쪽에서 출발할 것이다. 일단 8이하의 모든 소수를 저장한 배열이 있다고 하자. 양 포인터 사이에 있는 모든 수를 합하면 2가 나온다. 우리의 목표 숫자인 8보다 작다. 그럼 오른쪽 포인터를 하나 증가해서 범위를 넓혀준다. 원래 한..

문제 풀이 이 문제는 시간제한이 있기 때문에 모든 쌍을 찾는 O(n^2)의 시간 복잡도로는 풀 수 없다. 그래서 O(n)의 시간복잡도인 투 포인터 알고리즘을 사용해야 한다. 투 포인터 알고리즘을 사용하기 위해 배열을 정렬한다. 투 포인터라는 뜻은 포인터를 2개 사용한단 것이다. 포인터들은 양쪽에서 출발할 때도 있고 한쪽에서 출발할 때도 있는데 이 문제는 양쪽에서 출발할거다. 양 포인터가 가리키는 값들을 합하면 -1이 나온다. 일단 이게 -1과 가장 가까우니까 저 두 조합을 저장해두고... -1은 0보다 작으니까 두 수의 합이 커져야 한다는 뜻이다. 오름차순 정렬이기 때문에 빨간 포인터를 오른쪽으로 옮기면 합이 커지고, 파란 포인터를 왼쪽으로 옮기면 합이 작아질 것이다. 그러니 빨간 포인터를 오른쪽으로 옮..

문제 풀이 루트노드를 직접 찾아야 한다는 것을 몰라서 많이 헤맸다. 그것만 아니었어도 30분은 아꼈을텐데... 이 문제를 보자마자 제일 먼저 한 생각은 레벨 순회를 해야겠다는 것이었다. dfs에 속한다고 볼 수 있는 preorder, inorder, postorder와 달리 level traversal은 bfs에 속한다. 아무튼 이걸 사용해서 각 레벨별 정점을 정리해야겠다고 생각했다. level1 - 1 level2 - 2, 3 level3 - 4, 5, 6, 7 이런식으로 저장될테니 나중에 레벨마다의 너비를 구할때도 각 레벨의 첫번째 값과 마지막 값의 길이만 구하면 된다. 근데 문제는 각 정점의 열을 구하는 것이었다... 처음에는 분할정복으로 각 정점의 열을 구했는데 이것도 문제는 없는 코드였다. 굳이..

문제 풀이 myunji.tistory.com/287 [백준] 1697번 : 숨바꼭질 문제 풀이 얼핏보면 동적계획법 문제라고 생각할 수도 있다. 하지만 수빈이가 계속 앞으로만 이동하는게 아니라 뒤로도 이동할 수 있어서 bfs로 푸는게 훨씬 쉽다. 현재 지점(X)의 X-1, X+1, 2X가 아 myunji.tistory.com 이 문제에서 지나온 경로를 추가하는 코드만 추가하면 된다. bfs를 통해 거리를 갱신하면서 직전 위치도 함께 저장한다. 그리고 도착점부터 시작점까지 거슬러 올라가며 스택에 쌓고 출력하면 된다. 소스코드 #include #include #include #include using namespace std; const int MAX = 100000; pair pos[MAX + 1]; que..