자료구조13 [자료구조] 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. 단순 연결 리스트 (Singly Linked List) 단방향 링크 이전 노드에 접근하기 위해선 첫 번째 노드부터 다시 순회해야함 2. 원형 연결 리스트 (Circular Linked List) 단방향 링크 마지막 노드와 첫 번째 노드가 연결된 원형 구조 이전 노드에 접근하기 위해서 계속 한 방향으로만 순회하면 됨 3. 이중 연결 리스트 (Doubly Linked List) 양방향 링크 각 노드가 앞 뒤로 연결됨 이전 노드에 직접 접근 (Direct Access) 가능 2020. 8. 25. [자료구조] 리스트 (List) 리스트 (List) 자료를 순서대로 (Sequential) 일직선으로 저장하는 자료구조 자료가 일직선으로 서로 연결된 선형구조 자료 추가 : 빈 공간 확보를 위해 기존 자료들의 위치 이동 자료 삭제 : 빈 공간이 없도록 함 1. 배열 리스트 (Array List) 배열은 메모리 상에 순차적 (Sequential)으로 저장됨 논리적 순서 = 물리적 순서 원소 추가 : 맨 뒤 index ~ 추가하려는 index 까지의 원소들을 뒤로 한 칸씩 이동시킨다. (공백 추가) 원소 삭제 : 삭제 index ~ 맨 뒤 index 까지의 원소들을 앞으로 한 칸씩 이동시킨다. (공백 제거) 2. 연결 리스트 (Linked List) 포인터를 이용하여 리스트를 구현 → 물리적으로 멀리 떨어진 자료들을 순서대로 연결 논리적 .. 2020. 8. 25. [자료구조] 자료구조의 분류 자료구조의 형태에 따른 분류 구조 설명 단순 구조 (Primitive Data Structure) - 정수 (int) - 실수 (float, double) - 문자, 문자열 (char) - 언어에서 제공하는 기본적인 데이터 타입 선형 구조 (Linear Data Structure) - 자료를 순차적으로 저장, 효율적인 자료 저장이 목표 - 리스트 (list) - 스택 (stack) : LIFO (후입선출) - 큐 (queue) : FIFO (선입선출) - 덱 (deque) - 연결된 앞뒤 자료가 1:1 구조 비선형 구조 (Non-linear Data Structure) - 트리 (Tree) : 계층구조 - 그래프 (Graph) : 망구조 - 연결된 앞뒤 자료가 계층구조, 혹은 망구조 파일 구조 (File.. 2020. 8. 25. 이전 1 2 3 4 다음
