Computer Science51 [자료구조] 트리 (Tree) 트리 (Tree) - 계층 구조 (Hierarchical Structure)로 자료를 저장하는 자료구조 (비선형 자료구조) - 노드(Node), 간선 (Edge)의 집합 - 계층 구조 : 특정 부모 노드 하나에 여러 개의 자식 노드들이 연결되는 구조 회사 조직도 모델링 노드 종류 1. 위치 기준 노드 이름 설명 루트(Root) 노드 트리의 첫 번째 노드 단말(Leaf 혹은 Terminal) 노드 자식 노드가 없는 노드 내부 (Internal) 노드 자식 노드가 있는 노드 2. 관계 기준 노드 이름 설명 부모(Parent) 노드 자식 노드와 간선(Edge)으로 연결 자식(Child) 노드 부모 노드와 간선(Edge)으로 연결 선조(Ancestor) 노드 루트 노드 - 부모 노드까지 경로 상에 있는 모든.. 2020. 8. 31. [자료구조] 큐 (Queue) 큐 (Queue) 추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터가 나오는 자료구조 FIFO (First In First Out, 선입선출) 저장된 자료들은 선후 관계가 모두 1:1 front : 큐의 제일 앞, 자료가 반환되는 곳 rear : 큐의 제일 뒤, 자료가 추가되는 곳 enqueue() : 큐에 자료를 삽입하는 함수 dequeue() : 큐에서 자료를 빼내는 함수 peek() : 큐에 맨 위에 있는 자료 반환하는 함수 (큐에서 삭제는 하지 않는다) 큐의 크기 : 큐가 저장할 수 있는 최대 자료의 개수 → 이 갯수를 넘어버리면 오버플로우(Overflow) 발생 ex) 은행 업무 처리 대기열, 프린터 대기 문서 //배열로 구현한 선형 큐 public class Main { stati.. 2020. 8. 31. [자료구조] 스택 (Stack) 스택 (Stack) 자료를 한 방향으로만 쌓는 자료구조 LIFO (Last In First Out 후입선출 : 마지막에 들어온 것이 가장 먼저 나간다) push : 스택에 data를 넣는 것 pop : 스택 맨 위의 data를 빼는 것 peek : pop과 유사하게 맨 위의 data를 반환하지만 스택에서 제거하지는 않는다. top : 가장 마지막에 추가된 data의 위치 (가장 맨위) 가장 마지막에 push 한 data가 가장 먼저 pop 된다. 오버플로우 (Overflow) : 자료가 스택 크기를 넘어서서 더 이상 push 하지 못할 때 발생 언더플로우 (Underflow) : 스택에 자료가 남아있지 않아서 더 이상 pop하지 못할 때 발생 배열로 구현해보기 public class Main { stat.. 2020. 8. 26. [자료구조] Trie 트라이 트라이 (Trie) retrieval Tree에서 온 단어 문자열들을 트리 구조로 저장하여 O(log n) 속도로 빠르게 문자열을 탐색할 수 있게 해준다. 알고리즘 문제에선 주로 문자열의 '접두어', '~로 시작하는', '접미어', '~로 끝나는' 등의 키워드가 나오는 접두어, 접미어 판별 문제에서 사용된다. ※ 참조 문제 코딩테스트 연습 - 가사 검색 programmers.co.kr 자바로 트라이 구현하기 1. 노드 (Node) 클래스 import java.util.HashMap; public class Node { //해당 node 밑의 서브트리 총 node 개수 (옵션 : 즉 필요에 따라 넣는 요소) int count = 0; // isLast = true면 해당 문자열 존재 boolean isLa.. 2020. 8. 26. 이전 1 ··· 7 8 9 10 11 12 13 다음
