자료구조 (Data Structure)(9)
-
TREE (트리)
1. 부모 자식 관계의 자료구조 - tree(트리) 2, 트리의 구성 - node: 구성요소 - root node: 가장 맨 위에 있는 node, 부node가 없다 - link, edge : node와 node사이를 연결 - leaf node: 가장 마지막 끝에 있는 node - height: root node 부터 leaf node 까지의 높이. 주로 h라고 한다. - 경로(path): 출발노드 ~ 경유노드~ 도착노드 / 경로 길이 3, 트리의 표현법 리스트 - level0, level1 .... A = [ a, b,c, None,d,e,f ] - 각 레벨마다 꽉 차있다고 생각. 빈 노드도 왼쪽부터 비어있음을 표시 - 나는 지금 각 level별로 분류를 해보았다. - 단점: 메모리 낭비가 심함 리스트 ..
2021.06.29 -
순차적 자료구조 - QUEUE
1. QUEUE란? FIFO(FIRST IN FIRST OUT) 규칙의 순차적 자료구조 2. QUEUE의 연산 enqueue(val): 값을 큐의 오른쪽에 삽입(push와 같다) dequeue(): 가장 왼쪽에 저장된 값을 삭제 후 리턴 front(): 가장 왼쪽에 저장된 값을 라턴. 삭제하는 dequeue()는 다르다 3. 큐의 활용 - Josephus Problem n 명의 사람이 원형 테이블에 앉아 있다. 매 k번째 사람을 죽이는데, 최종 살아남는 사람은 누구인가!! ex) 1,2,3,4,5,6,7,8,9 사람이 있고, 3번째 마다 죽인다 -> 1,2, 4,5, 7,8 -> 1,2, 5, 7, -> 1,2,7-> 1,2-> 2 출처 https://namu.wiki/w/%ED%81%90(%EC%9E%..
2021.06.28 -
순차적 자료구조 - STACK
1. STACK이란? 리스트와 다르게 제한된 접근만 허용. 즉, 삽입, 삭제만 허용하는 선형(linear)자료구조 LIFO(LAST IN FIRST OUT)의 원칙을 따른다 2. STACK의 연산 삽입: push() 삭제: pop() - 가장 위에 있는 항목을 삭제 peak() - 가장 위에 있는 항목을 리턴, 항목을 삭제하는 pop과는 다름 isEmpty() - 스택이 비어 있다면, True를 반환 java로 구현 Node public class Node { //데이터 필드 public String data; //링크 필드 //참조변수에 저장되는 객체 타입으로 타입을 선언 public Node link; public Node(String data) { super(); this.data = data; }..
2021.06.28