6. 자료구조 & 알고리즘

자료구조 - [ 이진 탐색 트리 ]

이진 탐색 트리는 부모 노드 기준 작은 키는 좌측 자식 노드로, 큰 키는 우측 자식 노드로 유지하는 트리이다. 이러한 자료 구조는 데이터 탐색 시 노드를 이동하면서 재귀적으로 탐색 가짓수를 1/2로 줄여나가며 찾는다. 그러나 이진 탐색 트리는 키의 삽입 순서에 따라 트리의 균형이 달라지기 때문에 트리의 균형을 예측하기가 어렵다는 단점이 있다. 1. 이진 탐색 트리 삽입 부모 노드보다 작으면 좌측 자식 노드로, 부모 노드보다 크면 우측 자식 노드로 배치한다. 따라서 부모 노드 기준 좌측 끝에 있는 노드는 트리에서 가장 작은 키가, 부모 노드 기준 우측 끝에 있는 노드는 트리에서 가장 큰 키가 된다. 2. 이진 탐색 트리 삭제 노드를 삭제 시에도 이진 탐색 트리의 구조를 유지해야 하기 때문에 특정한 규칙에 ..

자료구조 - [ 이진 트리 순회 ( 깊이 우선 / 너비 우선 ) ]

1. 깊이 우선 탐색 1) 전위 순회 (pre-order) 부모 노드를 선 방문 후 좌측 서브 트리와 우측 서브 트리를 방문하는 방법 void visit(Node node) { System.out.println(node.data); } void preOrder(Node parent) { if (null == parent) { return; } visit(parent); preOrder(parent.left); preOrder(parent.right); } 2) 중위 순회 (in-order) 좌측 서브 트리를 방문하고 부모를 방문 후 우측 서브 트리를 방문하는 방법 void visit(Node node) { System.out.println(node.data); } void inOrder(Node pare..

자료구조 - [ 재귀 - 점화식 관점 / 분할 관점 / 백트래킹 관점 ]

재귀(Recursion)란 컴퓨터 과학에서 자신을 정의할 때 자기 자신을 재참조하는 방식을 뜻하며 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다. 1) 순환적 특성이 존재해야 한다. 2) 순환을 종료할 중단 조건이 있어야 한다. // ex 1) public void A(...) { if(중단 조건) { } A(...); } // ex 2) public void A() { if(중단 조건) { } B(); } public void B() { if(중단 조건) { } A(); } // 반복문 public static void evenNumber() { for (int i = 1; i 10) { return; } else if (i % 2 == 0) { System.out...

자료구조 - [ Queue ]

큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO) 구조로 저장되며, 일반적으론 작업 대기열로 많이 사용된다. 또한 Thread Pool에서 작업을 저장하는데 큐가 사용되며 순차적으로 먼저 들어온 작업을 처리하는 데 사용된다.. 또한 메시지와 관련한 서버 간의 통신을 위해 사용되는 메시지 큐, 그리고 시스템 버퍼에도 사용된다. 큐를 구현하는 방법으로는 크게 배열을 이용한 Circle Queue와 연결 리스트를 이용한 Queue가 있다. 1. Circle Queue (배열) front는 데이터를 꺼낼 때 어떤 데이터를 꺼내야 하는지 배열의 index를 저장하는 값으로, 데이터를 꺼낸 후 1씩 증가한다. but 배열의 크기를 넘어서는 값을 가지지는 않는다. * front의 변경 범위 0

자료구조 - [ Stack ]

스택은 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 구조로 되어 있으며, 데이터를 넣는 것을 Push, 데이터를 꺼내는 것을 Pop이라고 한다. 마지막에 들어간 것이 먼저 나온다는 후입선출(LIFO - Last In First Out)의 특징을 가지고 있다. 1. 배열로 Stack 구현 top은 데이터를 꺼낼 때 어떤 데이터를 꺼내야 하는지 배열의 index를 저장하는 값이다. 데이터를 넣을 때 top은 위로 이동하고, 데이터를 꺼낼 때는 top이 아래로 이동하며, 최솟값으로 -1을 가지고 최댓값으로 배열의 마지막 index를 가진다. * top의 변경 범위 -1

자료구조 - [ 이중 연결 리스트 ]

1. 이중 연결 리스트 이중 연결 리스트의 노드는 데이터와 좌측 노드의 참조값을 저장하는 변수, 우측 노드의 참조값을 저장하는 변수가 있다. 구성은 크게 head, tail 그리고 노드가 있다. head : 첫 번째 노드를 가리키는 노드 또는 변수 tail : 마지막 노드를 가리키는 노드 또는 변수 노드 : 데이터, 좌/우측 노드로 접근할 수 있는 참조값을 가지고 있음 1) 장점 - 데이터의 크기가 예측 불가능할 때 사용할 수 있다. - 필요한 만큼만 메모리 공간을 사용 -> 배열보다 상대적으로 메모리 절약 가능 - 단일 연결 리스트와 다르게 양방향 연결을 지향하므로 뒤 쪽에 있는 노드 접근 시 tail을 이용하면 더 빠르게 접근 가능 ex) 노드의 개수가 10000개일때 9821번째 노드에 접근하려면 ..