프로그래민👨‍💻

Trie와 DFS를 활용한 문제였다. Trie를 활용하기 위해 Node라는 클래스를 만들고, 그안에 child라는 Map구조의 Node를 주었다. 일반 적인 Trie문제와 다르게 배열대신 Map을 활용해보았다. 그렇게 모든 입력들을 root아래 저장 후, DFS를 활용하여 출력을 해주었다. 단, 이때 알파벳순 출력이 필요하기때문에 Map의 keySet을 정렬된 리스트의 형태로 만들고 문제를 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61..

DFS를 이용하여 트리의 구조에서 지름을 찾는 문제였다. 트리의 지름은 리프노드에서 리프노드까지의 거리를 의미하기 때문에 브루트포스의 형식으로 모든 노드를 탐색하면서 리프노드라고 판별될 경우 그 노드를 기준으로 DFS를 돌아서 다른 리프노드까지의 거리를 찾아서 비교하여 최대값을 구하는 방식으로 풀이해보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 package algostudy2..

위상정렬 혹은 DFS를 사용할 수 있는 문제였다. 이 문제는 트리 문제로써 각 위치마다 양 또는 늑대가 존재하고, 루트까지의 양의 총합을 구하는 문제였다. 트리를 형성하고, 전체를 순회하는 구조이기에 맨처음 DFS로 접근해보았다. 1번(루트)에서 DFS를 한번도는 방식을 구상하였는데, 양의 수를 구하기 위해 DFS를 돌때 리턴값(양의 수)을 가지게 되고 최종적으로 자식노드 부터 리턴값을 보내어 1번(루트)에서 받아보는 방식을 생각해보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 ..

이진트리의 순회 문제이다. 이 문제는 이진트리의 노드들이 주어지고 전위순회(루트->좌->우), 후위순회(좌->우->루트)를 구하는 문제였다. 보통의 문제들과 다른점은 간선을 그리는 것이 주요한 문제였다. 따라서 두가지 과정을 거쳐 간선을 그려보았다. 일단 첫번째로 모든 노드들을 y로 내림차순, y가 같다며 x로 오름차순이 되도록 정렬을 하였다. 그 후에 Node라는 클래스를 만들어 left, right를 Node의 형으로 멤버변수(포인터의 개념)를 주고, 정렬된 노드들을 x값을 비교하여 left,right에 할당하며 연결해주었다. 이것을 완료한 후에는 재귀를 이용하여 간단하게 전위순회, 후위순회를 하여 풀었다. 문제의 우선순위, 즉 이문제에서는 간선을 그리는것이 최우선목표인데 그것을 해결하는 것이 중요한..