moonscode

/** * [하위트리확인] * 두개의 커다란 이진트리 T1, T2가 있을때 * T1이 T2보다 훨씬 크다고 했을때, T2가 T1의 하위 트리 (sub tree)인지 판변하는 알고리즘 제자 * * [풀이] * => 플래그를 이용하는 방법 * => 이동하는 모든 플래그에 대해서 기호값으로 배열에 추가 * => 중위순회 & 전휘순회 & 후위순회 상관없이 풀이가능 * => 플래그가 배열을 형태까지 복사하기 때문에 배열이 겹친다면 하위트리로 확인이 가능함 * * */ public class Q10 { public static void main(String[] args) { // @Test Node root = new Node(4); root.left = new Node(2); root.right = new Nod..

/** * [첫번째 공통 조상] * 이진트리에서 노드 두개가 주어졌을때, * 이 두 노드의 첫번째 공통 조상을 찾는 알고리즘을 설계하고 그 코드를 작성 * 자료구조내에 추가로 노드를 저장해선 안된다. * * [풀이] * => 주어진 두 노드가 같은 레벨인가요 ? * => 같은 레벨이 아니라면 높이의 차이를 구해서 처리 * => 노드가 부모의 참조를 가질 수 있나요 ? * => 부모에 대한 참조가 없을때 해결할 수 있을까 ? * => * 있음 - NodeA와 NodeB가 더이상 같은쪽에 있지 않으면 그것이 공통조상 * */ public class Q08 { /* main */ public static void main(String[] args) { // @Test - 부모참조 있을때 Node rootB =..

package question.treegraph; /** * [후속자] * 이진탐색트리에서 주어진 노드의 다음노드(중위 후속자, in-order-successor)를 찾는 알고리즘 * 각 노드에 부모 노드를 가리키는 링크가 존재 * * [풀이] * => 중위후속자가 무엇인가 ? * => 중위순회를 진행할때 다음에 나올 노드 * => while(true) { 부모의 오른쪽 노드의 왼쪽 자식 노드, 없다면 부모로 올라감 } * => 부모노드의 참조값을 가지고 있어야함 * */ public class Q06 { /* main */ public static void main(String[] args) { // @Test Node rootB = new Node(4); rootB.left = new Node(2);..

/** * * [BST 검증] * 주어진 이진 트리가 이진탐색트리인지 확인하는 함수 * * [풀이] * => 트리에 중복이 있나요 ? * => 주어진 노드를 받았을때 재귀로 계속 검증 * => 재귀로 검증할때 최상위에서부터 검사해야함 * => * 위에서 부터 타고 내려왔다면 노드마다 범위가 있음 * * [해법] * => 01. 중위순회 * => 02. left 전체크기를 알고 있는가 ? * => 알고있다면 배열 * => 모른다면 리스트 * */ public class Q05 { /* Main */ public static void main(String[] args) { // @Test Node rootA = new Node(1); rootA.left = new Node(2); rootA.right = n..

/** * [균형확인] * 이진트리가 균형 잡혀있는지 확인하는 함수를 작성하라 * 이 문제에서 균형잡힌 트리란 * 모든 노드에 대해서 왼쪽부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미 * * [풀이] * => 균형잡힌 트리란 ? * => 루트로 부터 왼쪽트리와 오른쪽트리의 높이를 말하는 것인지 ? * => 왼쪽과 오른쪽의 높이 차이가 1이내면 균형잡힌 트리인 것인지 ? * => 왼쪽의 최대 높이와 오른쪽의 최대 높이를 각가 구해야함 * */ public class Q04 { /* Main */ public static void main(String[] args) { // @Test Node root = new Node(1); root.left = new Node(2); r..

/** * [깊이의리스트] * 이진트리가 주어졌을때, 같은 깊이에 있는 노드를 연결리스트로 연결해 주는 알고리즘 * 즉, 트리의 깊이가 D라면 D개의 연결리스트를 만들어라 * * [풀이] * => 트리가 주어지냐 ? * => D라는 것을 매개변수로 받아야 하냐 ? * => 큐를 사용해도 되냐 (너비우선탐색) ? * * */ public class Q03 { /* Main */ public static void main(String[] args) { // @Test Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5);..

/** * [최소트리] * 오름차순으로 정렬된 배열이 있고, * 이 배열의 원소는 정수이며 중복된 값이 없을때, * 높이가 최소가 되는 "이진탐색트리"를 만드는 알고리즘을 작성 * * [풀이] * => Tree를 직접만들어야할까요 ? * => 높이가 최소이기 위해선 빈공간이 최소화 되야함 * */ public class Q02 { /* main */ public static void main(String[] args) { // [예상시나리오] // 4 // 2 6 // 1 3 5 7 Tree tree = new Tree(); int[] arr = new int[] {1, 2,3, 4, 5, 6, 7}; minHeightTree(tree, arr, 0, arr.length-1); // @Test tree...

/** * [노드사이의 경로] * "방향그래프"가 주어졌을때, 두 노드 사이에 경로가 존재하는지 확인하는 알고리즘을 작성 * * [풀이] * => 시작부터 끝까지 너비우선탐색 & 깊이우선탐색으로 확인가능 * => 양방향탐색을 진행해서 만나는 점이 있다면 확인이 가능 * */ public class Q01 { /* MyGraph */ public static class Graph { public Node[] getNodes() { return null; } } /* Node */ public static class Node { State state; public Node[] getAdjacent() { return null; } } /*State */ enum State { Unvisited, Visite..

/** * [루프발견] * 순환 연결리스트가 주어졌을때, 순환되는 부분의 첫째노드를 반환하는 알고리즘을 작성 * 순환 연결리스트란 노드의 next 포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는, * 엄밀히 말해서 변질된 방식의 연결리스트를 의미한다. * * [예제] * A -> B -> C -> D -> E -> C [앞에 나온 C와 같음] * * [풀이] * => 새로운 노드가 나올때마다 기존에 나왔던 노드인지 계속 확인을 해줘야 한다. * => Buffer 방식 or Runner 방식 * * */ public class Q08 { /* Node */ static class Node { Node next; int data; Node(int data) { this.data = data..

/** * [교집합] * 단방향 연결리스트 두개가 주어졌을때 이 두 리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라 * 여기서 주소는 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. * 즉 첫번째 리스트에 있는 k번째 노드와 두번째 리스트에 있는 j번쨰 노드가 주소까지 완전히 같다면 교집합 원소이다. * * [풀이] * => 리스트의 노트간에 공유가 가능한가 * => 만약 주소가 같은 노드가 있다면 그 뒤로는 모두 같다. * => 마지막 노드는 항상 같다. * * */ public class Q07 { /* Node */ static class Node { Node next; int data; Node(int data) { this.data = data; } } /* Result ..