HwangHub

문제 링크 문제 해석 트리 구조에서 공통된 조상 중 가장 가까운 조상을 찾는 건 그래프 알고리즘 중 유니온파인드 알고리즘의 '파인드' 부분을 활용하면 될 것으로 보았다. 아울러 그 노드 기준으로 자식 노드의 개수를 세는 건 dfs로 간단하게 구현할 수 있다. 문제 풀이 시간복잡도 : DFS를 인접리스트로 구현하였고(O(V+E)), 파인드 로직에서 최소 공통 root 노드를 찾기 위한 로직에서 트리 높이(h)가 최악의 경우 노드 개수(V)에 근사해지므로 O(V + E)이다. package ssafy.사전학습; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import jav..

지난 실력진단 문제에서 구성되는 마을의 최대 크기라던지, 마을의 개수를 어떻게 구할 수 있을지 쉽게 떠오르지 않았어서 해당 부분을 연습하기 위해 이 문제를 다시 풀어봤다. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 접근 이 문제는 단순 반복문을 통해서는 나의 한계로 로직이 떠오르지도 않거니와, 있더라도 분명히 매우 복잡할 것이므로 패스하였다. 그 외에 순열, 조합과 같은 경우의 수를 탐색하는 경우도 아니고, 최대최소를 얻는 그리디한 바이브의 문제도 아니였다. 탐색 알고리즘 중에 이웃한 항과의 관계를 통해 답을 도출해 내는 그래프 알고리즘이 이 문..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 이 문제는 지난번에 풀었던 "사각형 채우기"와 같은 유형의 문제로써, 점화식을 세울 때 조금 더 생각을 해줘야 하는 문제이다. 기본적으로 n번째 자리까지 타일을 까는 경우의 수는 n-1, n-2 번째까지의 타일을 까는 경우의 수 들을 이용하여 도출해낼 수 있다는 아이디어가 DP의 기본 흐름이다.(큰 문제는 작은 문제로 쪼개어 생각한다.) 이렇게 볼 때, 1칸짜리 그리고 2칸짜리를 이용하여 f(n) = 2 * f(n-1) + 3 * f(n-2) 까지는 쉽게 구해질 것이다. 이게 만약 안보인다면 ..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제 해석 위 문제는 가중치가 1로 동일한 경우에서의 최단 거리를 묻는 문제이므로 BFS를 돌리면 된다고 느낄 수 있다. 대표적인 유형의 문제인 걸로 느껴지는데, 지금 뇌가 정지한건지 도저히 내가 어디가 틀린지 모르겠다... 일단 내 풀이는 맞을 가망이 없었고, 아무리 봐도 모르겠어서 일단은 답안을 이해한 뒤에 내 방식대로 고쳐서 작성해 보았다. 내 풀이(틀린 풀이) 나는 인간이 있는 좌표로부터 최단거리에 있는 대피소를 BFS로 찾고, 그 최단 거리를 ans라는 정답 배열의 인간 좌표에 입력해주는 방식으..