그래프 (Graph) 정점과 간선으로 이루어진 자료구조 (Cyclic) 지하철 노선도, 통신 네트워크 등에 사용 그래프의 종류 (1) 무방향 그래프 : 간선에 방향이 없는 그래프 (양방향 이동 가능) (2) 방향 그래프 : 간선에 방향이 있는 그래프 (해당 방향으로만 이동 가능) (3) 가중치 그래프 : 간선에 값이 있는 그래프 (이동 비용) (4) 완전 그래프 : 모든 정점이 서로 연결되어 있는 그래프, 노드가 N 개일 경우, 간선의 수는 N(N-1)/2개 그래프 탐색 (1) 깊이 우선 탐색 (Depth First Search; DFS) DFS는 그래프 또는 트리에서 모든 노드를 탐색하는 알고리즘으로 스택 또는 재귀 함수를 사용하여 구현할 수 있다. 시작 노드를 방문하고 방문한 노드를 스택에 push ..
해시 (Hash) 해시는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 매핑하는 과정 또는 그 결과를 말한다. 해시 함수 (Hash Function) 매핑 과정을 수행하는 함수로서, 입력 데이터를 받아서 해시 값을 계산하여 반환하는 함수 동일한 입력에 대해서는 항상 동일한 해시 값을 반환하며, 입력 데이터가 조금이라도 변경되면 다른 해시 값을 생성 데이터의 무결성을 검증하거나 데이터의 식별을 위해 사용 Divison 기법 : 간단한 해시 함수, 입력값을 특정 수로 나눈 나머지를 해시 값으로 사용 H(k) = k mod m, k = 입력값, m = 해시 테이블 크기) Multiplication 기법 : 입력값과 곱셈을 통해 해시 값을 계산하는 방법 0에서 1사이의 상수 A를 선택하고 k * A 의 소수..
이진 탐색 트리 (Binary Search Tree) 아래의 규칙으로 구성된 이진 트리이다. 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다. 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다. 각각의 서브 트리도 이진 탐색 트리이다. 중복된 키를 허용하지 않는다. 이진 탐색 트리의 특징 이진 탐색 트리 규칙에 의해 데이터가 정렬되어 있다. 이진 트리에 비해 탐색이 빠르다. 균형 상태 일때 : O(log n) 불균형 상태 일때 : O(n) 이진 탐색 트리 - 탐색 찾고자 하는 데이터를 루트 노드부터 비교하여 탐색한다. 대소 비교를 하여 찾는 데이터가 현재 노드보다 작으면 왼쪽, 크면 오른쪽 노드로 이동한다. 찾는 데이터가 없으면 null을 반환한다. 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 ..
힙(Heap) 완전 이진 트리 형태 중복 값 허용 반 정렬 상태 최솟값 또는 최댓값을 빠르게 찾아내는데 유용한 자료구조 최소 힙, 최대 힙 우선순위 큐(Priority Queue)를 구현하는데 사용 최소 힙(Min Heap) 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태 (루트 노드가 최소값을 가지는 힙) 최대 힙(Max Heap) 부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태 (루트 코드가 최대값을 가지는 힙) 힙 구현 배열을 사용하여 구현 완전 이진트리의 특성에 따라 배열에서 각 노드는 인덱스로 표현 루트 노드는 인덱스 0에 위치하며, 자식 노드들은 특정한 방식으로 인덱스를 계산하여 배열에 저장 # 부모 노드와 자식 노드의 관계 왼쪽 자식 index = 부모 index * 2 오른쪽..
트리(Tree) 노드와 링크로 구성된 자료구조 계층적 구조를 나타낼 때 사용 ex) 폴더 구조, 조직도, 가계도, etc. 트리의 특징 하나의 노드에서 다른 노드로 이동하는 경로는 유일하다. 노드가 N개인 트리의 Edge의 수는 N-1개 이다. Cycle이 존재하지 않는다. (Acyclic) 모든 노드는 서로 연결되어 있다. 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리된다. 이진 트리 종류 1. 이진 트리(Binary Tree) 각 노드는 최대 2개의 자식을 가질 수 있다. 자식 노드는 좌우를 구분한다. 2. 포화 이진 트리(Perfect Binary Tree) : 모든 레벨에서 노드들이 꽉 채워져 있는 트리 3. 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하..
스택(Stack) 후입선출(Last In First Out; LIFO) 자료구조 : 마지막에 들어온 데이터가 먼저 나가는 구조 스택 구현 일반적으로 배열 또는 연결 리스트로 구현 배열 기반 스택 : 고정된 크기를 가짐 연결 리스트 기반 스택 : 동적으로 크기가 조정됨 스택 기본 연산 push: 스택의 맨 위에 요소 추가 pop : 스택의 맨 위에 있는 요소를 제거하고 반환 peek 또는 top : 스택의 맨 위에 있는 요소를 반환하지만 제거하지는 않음 스택 사용 데이터의 순서와 관련된 정보를 유지하면서 데이터를 저장하고 검색하는 경우 유용하게 사용된다. 함수 호출과 재귀 알고리즘 함수가 호출되면 해당 함수의 호출 정보(매개 변수, 반환 주소 등)가 스택의 맨 위에 저장된다. 함수의 실행이 완료되면 스택에..
배열(Array) : 요소들을 인덱스에 기반하여 연속적으로 저장하는 자료구조 ArrayList : 동적 크기를 가지는 배열로, 내부적으로 배열을 사용하여 구현되는 자료구조 LinkedList : 각 요소들을 노드로 구성하고, 노드들은 데이터와 다음 노드를 가리키는 포인터로 연결되는 자료구조 Array, ArrayList, LinkedList 비교 1. 크기 조정 배열 : 고정 크기로 선언되며, 크기를 변경할 수 없다. ArrayList, LinkedList : 동적으로 크기가 조정된다. 2. 타입 제한 배열 : 제네릭 타입 사용 불가능 ArrayList, LinkedList : 제네릭 타입을 사용가능 배열에 제네릭 타입을 사용할 수 없는 이유는 배열은 컴파일 시점에서 자신의 요소 타입을 알고 있어야 하는..
연결리스트란? 연결리스트 : 데이터 요소들을 노드(Node)라는 단위로 구성하여 메모리 상에서 연속적으로 배치되지 않고, 각 노드들이 포인터(Pointer)로 연결되어 있는 자료구조 • 각 노드는 데이터를 저장하는 데이터 필드(data field)와 다음 노드를 가리키는 링크 필드(link field)로 구성되어 있다 단방향 연결리스트(Singly Linked List) : 각 노드가 다음 노드를 가리키는 링크 필드만을 갖고 있다. 이러한 구조로 인해 단방향으로 노드들이 연결되어 있다. 양방향 연결리스트(Doubly Linked List) : 각 노드가 이전 노드와 다음 노드를 가리키는 링크 필드를 갖고 있다. 양방향으로 노드들이 연결되어 있기 때문에 양쪽 방향으로 노드를 탐색할 수 있다. 연결리스트의 ..
배열이란? 배열 : 동일한 데이터 유형의 요소들을 일렬로 나열한 것 • 논리적 저장 순서와 물리적 저장 순서가 일치한다. • 각 요소는 인덱스를 통해 접근할 수 있다. • 메모리 상에 연속적으로 할당된다. 배열의 장단점 장점 1. 빠른 접근 : 인덱스를 통해 요소에 빠르게 접근할 수 있다. 시간복잡도는 O(1)이다. 단점 1. 크기 제한 : 생성할 때 크기를 정해야 하며, 이 크기는 변경할 수 없다. 2. 메모리 낭비 : 미리 정해진 크기를 사용하기 때문에 요소가 모두 채워지지 않는 경우 메모리를 낭비할 수 있다. 크기를 크게 설정하면 필요 이상의 메모리를 사용하게 되고, 작게 설정하면 요소를 저장할 공간이 부족해질 수 있다. 또한, 빈 메모리 공간이 배열의 크기 보다 작으면 사용할 수 없다. 3. 삽입..
Queue란? 선입선출 (First In First Out; FIFO) 자료구조 먼저 들어온 데이터가 먼저 나가는 구조 입력 순서대로 데이터 처리가 필요할 때 사용 BFS (Breath-First Search) Queue 기본 구조 Queue 기본 연산 Queue 생성 큐는 배열기반의 컬렉션 클래스를 사용하면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터를 복사해야 하므로 LinkedList로 구현하는 것이 적합하다. import java.util.LinkedList; import java.util.Queue; Queue queue = new LinkedList(); // Queue는 interface로 구현되어 있음. 따라서 바로 객체로 만들 수 없음. -> Queue queue = new Que..
