moonscode

/** * [균형확인] * 이진트리가 균형 잡혀있는지 확인하는 함수를 작성하라 * 이 문제에서 균형잡힌 트리란 * 모든 노드에 대해서 왼쪽부분 트리의 높이와 오른쪽 부분 트리의 높이의 차이가 최대 하나인 트리를 의미 * * [풀이] * => 균형잡힌 트리란 ? * => 루트로 부터 왼쪽트리와 오른쪽트리의 높이를 말하는 것인지 ? * => 왼쪽과 오른쪽의 높이 차이가 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 ..

/** * [회문] * 주어진 연결리스트가 회문인지 검사하는 함수를 작성 * * [풀이] * => 리스트 내부함수로 구현하는가 ? * => 양방향인가 단방향인가 ? * => 전체 길이를 캐싱할 수 있는가 ? * */ public class Q06 { public static void main(String[] args) { } /* Node */ static class Node { Node next; int data; Node(int data) { this.data = data; } } /* isPalindromeA */ static boolean isPalindromeA(Node head) { Node reversed = reverseAndClone(head); return isEqual(head, re..

/** * [리스트의합] * 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로표현할 수 있다. * 각 숫자는 역순으로 배열되어 있는데 첫번째 자릿수가 리스트의 맨 앞에 위치하게 배열된다는 뜻이다. * 이와 같은 방식을 표현된 숫자 두개가 있을 때 이 두수를 더해 그 합을 연결 리스트로 반환하는 함수를 작성 * * [풀이] * => 리스트를 직접구현 ? * => 최대 혹은 최소 몇자리수까지 리스트가 존재하는가 ? * * */ public class Q05 { public static void main(String[] args) { sumList(Arrays.asList(9, 9, 9), Arrays.asList(9, 9, 9)); // 1998 } /* sumList - 외부구현 *..

/** * [분할] * 값 x가 주어졌을 때 x보다 작은 노드들을 x보다 크거나 같은 노드들 보다 앞에 오도록 하는 코드를 작성 * 만약 x가 리스트에 있다면 x는 그보다 작은 원소들 보다 뒤에 나오기만 하면 된다. * 즉, 원소 x는 오른쪽그룹 어딘가에 존재하면 된다. 왼쪽과 오른쪽 사이에 있을 필요는 없다. * * [예제] * (3) > [5] > 8 > [5] > 10 > (2) > (1) [분할5] * 3 > 1 > 2 > 10 > 5 > 5 > 8 * * [풀이] * => 요청받은 분할값 뒤로 분할값보다 작은게 있으면 앞으로 보내면 된다. * * */ public class Q04 { class Node { Node next; int data; } /* partitionA - 두개의 리스트를 만..

/** * [중간노드삭제] * 단방향 연결리스트가 주어졌을때 중간(처음과 끝이 아님)에 있는 노드 하나를 삭제하는 알고리즘을 구현해라 * 단 삭제할 노드에만 접근할 수 있다. * * Poinst. * => 리스트 내부함수 ? 외부함수 ? * => 삭제는 인덱스로 ? 객체로 ? * * */ public class Q03 { class Node { Node next; int data; } class MyList { Node head; MyList() { } // == 노드 기준 (O) - 마지막 노드를 삭제할 수 없음 == boolean delete(Node node) { Node next = node.next; node.data = next.data; node.next = next.next; return ..