이재윤 블로그

1) search 메소드 public class NodeMgmt{ public class Node { Node left; Node right; int value; public Node(int data){ this.value = data; this.left = null; this.right = null; } } public boolean insertNode(int data){ if(this.head == null){ }else{ Node findNode = this.head; while(true){ if(data < findNode.value){ if(findNode.left != null){ findNode = findNode.left; }else{ findNode.left = new Node(data)..

1. 트리란? - 트리는 난이도로 보면 자료구조 중 제일 높음 -> 트리를 유지보수하는 로직이 복잡하더라도, 참고하는 편이 좋음 - 면접에서 트리의 특정 로직을 구현하라고 할 수 있음 - 트리는 노드와 브랜치라는 것을 사용해서 사이클을 이루지 않도록 구성함 -> 트리는 굉장히 넓은 범위로 정의를 한 것임 -> 그 중에서 우리가 익혀야 하는 것은 이진 트리 구조임 - 노드가 있을 때, 최상단 노드는 루트 노드임 -> 이진 트리는 노드의 최대 브랜치가 2개 -> 이진 트리 중에서 이진 탐색 트리(Binary Search Tree)가 있음 - 이진 탐색 트리 노드의 왼쪽 노드는 작은 값이, 오른쪽 노드는 큰 값이 들어감 -> 이진 트리 중에서도 이진 탐색 트리를 많이 씀 - 최상단에 위치한 노드는 Level ..

- Linear Probing 기법의 코드는 다음과 같이 작성할 수 있음 public class MyHash{ public Slot[] hashTable; public MyHash(Integer size){ this.hashTable = new Slot[size]; } public class Slot{ String key; String value; Slot(String value){ this.key = key; this.value = value; } } public int hashFunc(String key){ return (int)(key.charAt(0)) % this.hashTable.length; } public boolean saveData(String key, String value){ Int..

- 해시 테이블의 장,단점 (1) 장점 - 데이터 저장/읽기 속도가 빠르다는 것임 - 해시는 키에 대한 데이터가 있는지 확인이 쉬움 (2) 단점 - 일반적으로 저장 공간이 많이 필요함 - 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요함 - 해시 테이블의 주요 용도 (1) 검색이 많이 필요한 경우 (2) 저장, 삭제, 읽기가 빈번한 경우 (3) 캐시 구현 시 - 충돌(Collision) 해결 알고리즘 (1) Chaining 기법 - 충돌이 발생하면 해당 위치에 linked list 만듦 - 개방 해싱(Open hashing)이라고도 함 (2) Linear Probing 기법 - 폐쇄 해싱(Closed hashing)이라고도 함 Chaining 기법 코드 public c..

- 키에 데이터를 매핑할 수 있는 데이터 구조임 -> 각각의 데이터마다 키와 밸류에 해당하는 값은 다를 수 있음 - key를 hash function에 넣으면 주소를 리턴해줌 -> hash function은 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수임 - hash 함수는 사용자가 정의할 수 있음 - 해시 테이블에 저장하면 key를 hash function에 넣으면 O(1)에 확인할 수 있음 (cf. 배열, 링크드 리스트) - 해시 테이블은 보통 배열을 많이 사용함 -> 각각의 실제 데이터가 저장되는 공간을 slot이라고 함 - 해시 함수를 통해 리턴된 값을 해쉬 주소, 해쉬 값, 해쉬 라고 함 - 해시 클래스는 다음과 같이 만들 수 있음 public class MyHash{ public Slo..

- 더블 링크드 리스트에서 데이터를 임의의 노드 앞에 노드를 추가하는 메서드는 기존의 코드(https://bryanlee.tistory.com/47)에 다음 메서드를 추가하면 됨 public boolean insertToFront(T existedData, T addData){ if(this.head == null){ this.head = new Node(addData); this.tail = this.head; }else if(this.head.data == existedData){ Node newHead = new Node(addData); newHead.next = this.head; this.head = newHead; return true; }else{ Node> node = this.head;..

- 기존의 링크드 리스트는 데이터를 무조건 처음부터 찾아나가야 함 - 더블 링크드 리스트는 하나의 노드에 2개의 포인터가 존재함 -> 따라서 100개의 노드가 있다면 99번째 노드는 100번째 노드로부터 찾을 수 있음 - 더블 링크드 리스트는 다음과 같이 구현할 수 있음 -> addNode, printAll, searchFromHead, searchFromTail 메소드를 구현할 수 있음 public class DoubleLinkedList { public Node head = null; public Node tail = null; public class Node { T data; Node prev = null; Node next = null; public Node(T data){ this.data = ..

1) 링크드 리스트 사이에 데이터 추가 - 링크드 리스트 사이에 데이터를 추가할 때는 부가적인 로직이 필요함 -> 기존 코드를 가져와서 붙여넣고, 중간에 데이터를 추가하는 메소드를 만들어봄 -> 여기서는 search 메소드와 addNodeInside 메소드를 추가함 public class SingleLinkedList{ public Node head = null; public class Node{ T data; Node next = null; public Node(T data){ this.data = data; } } public void addNode(T data){ if(head == null){ head = new Node(data); }else{ Node node = this.head; while..

1) 링크드 리스트 특징 - 링크드 리스트는 하나의 저장된 데이터가 있을 때마다, 해당 데이터를 저장할 공간과 다음 연결될 데이터의 주소값을 가지는 공간을 생성함 - 데이터가 1000개, 2000개, 10000개가 있어도 연결해서 놓을 수 있음 2) 링크드 리스트의 장단점 (1) 장점 - 미리 데이터 공간을 할당하지 않아도 됨 -> 데이터 공간이 필요할 때 할당하면 됨 (2) 단점 - 항상 데이터를 저장할 때, 데이터 공간과 다음 데이터 공간을 가리키는 데이터 공간이 필요함 -> 저장공간 효율이 높지 않음 - 링크드 리스트는 데이터를 찾으려면 무조건 맨 앞부터 찾아가야 함 -> 접근 속도가 느림 - 중간에 있는 데이터를 삭제하려면, 부가적인 작업이 필요함 3) 링크드 리스트 구성 - 링크드 리스트는 하나..

1) 스택의 특징 - 스택은 큐와 함께 가장 많이 쓰이는 자료구조 중 하나임 - 큐가 FIFO 정책을 쓴다면, 스택은 LIFO 정책을 씀 -> 즉, 가장 마지막에 넣어진 데이터를 먼저 뽑음 2) 스택의 활용 - 컴퓨터 내부 프로세스 구조의 함수 동작 방식에 스택이 활용됨 3) 스택의 메소드 - push(): 데이터를 스택에 넣기 - pop(): 데이터를 스택에서 꺼내기 4) 스택의 장단점 장점 (1) 구조가 단순해서 구현이 쉬움 (2) 데이터 저장/읽기 속도가 빠름 단점 (1) 데이터 최대 개수를 미리 정해야 함 (2) 저장 공간의 낭비가 발생할 수 있음 5) 스택 활용하기 import java.util.Stack; Stack stack_int = new Stack(); stack_int.push(1);..