moonscode

Collection 객체를 효율적으로 관리하기 위한 자바의 자료구조 모음 List 순서 유지 중복 가능 ArrayList 내부 저장 구조에 Array를 사용하는 List 저장용량이 초과하면 자동으로 저장용량을 늘림 List list = new ArrayList(); List list = new ArrayList(30); Vector ArrayList와 동일한 내주 저장 구조를 가짐 ArrayList와 다른 점은 동기화(Synchronized)된 메소드를 가짐으로 ThreadSafety 하다는 것 Syncronized & ThreadSafety? List list = new Vector(); List list = new Vector(30); LinkedList 다음 객체의 주소를 참조하여 체인처럼 관리하는..

/** * [하위트리확인] * 두개의 커다란 이진트리 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..