Computer Science/Data Structure
-
[자료구조 Java] 비선형 자료구조 ④ 맵 (Map), 집합 (Set), 해시테이블Computer Science/Data Structure 2022. 10. 5. 19:02
비선형 자료구조란? : 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말하며 일반적으로 트리나 그래프를 의미 5. 맵 (Map) : 특정 순서에 따라 키(Key)와 매핑된 값(Value)의 조합으로 형성된 자료 구조 - 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고, Key 를 통해 Value를 얻을 수 있음 - Key는 중복될 수 없으며, Value는 중복 값을 허용함 - 자바에서 Map은 인터페이스로, 인터페이스를 구현 Map자료형에는 HashMap, LinkedHashMap, TreeMap 등이 있음 5-1. HashMap 주요 메소드 import java.util.HashMap; public class Test { public static void main(String[] ar..
-
[자료구조 Java] 비선형 자료구조 ③ 힙, 우선순위 큐Computer Science/Data Structure 2022. 10. 5. 18:33
비선형 자료구조란? : 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말하며 일반적으로 트리나 그래프를 의미 3. 우선순위 큐 : 우선순위 대기열이라고도 하며, 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조 - 데이터들이 우선순위를 가지고 있고, 우선 순위가 높은 데이터가 먼저 나감 - 우선순위 큐는 배열, 연결리스트, 힙으로 구현 가능하며 힙으로 구형하는 것이 가장 효율적 구현 방법 삽입 삭제 순서 없는 배열 O(1) O(n) 순서 없는 연결 리스트 O(1) O(n) 정렬된 배열 O(n) O(1) 정렬된 연결 리스트 O(n) O(1) 힙 O(log n) O(log n) 3-1. 우선순위 큐의 활용 - 시뮬레이션 시스템 - 네트워크 트래픽 제어 4. 힙 (H..
-
[자료구조 Java] 비선형 자료구조 ② 트리Computer Science/Data Structure 2022. 10. 5. 17:51
비선형 자료구조란? : 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말하며 일반적으로 트리나 그래프를 의미 2. 트리 : 계층적 관계를 표현하는 자료구조 2-1. 관련 용어 - Node(노드): 트리를 구성하고 있는 각각의 요소 - Edge(간선): 노드와 노드를 연결하는 선 - Root Node(루트 노드): 트리 구조에서 최상위에 있는 노드 - Terminal Node(=Leaf Node, 단말 노드): 하위에 다른 노드가 연결되어 있지 않은 노드 - Internal Node(내부 노드, 비단말 노드): 단말 노드를 제외한 모든 노드 (루트노드도 포함) - Sibling: 같은 부모를 가지는 노드 - 노드의 크기: 자신을 포함한 모든 자손 노드의 개수 - 노드의 깊이: 루트에서 어떤 노드에..
-
[자료구조 Java] 비선형 자료구조 ① 그래프Computer Science/Data Structure 2022. 10. 5. 17:03
비선형 자료구조란? : 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말하며 일반적으로 트리나 그래프를 의미 1. 그래프 : 정점과 간선으로 이루어진 자료 구조 - 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 할 때, '어떠한 곳'은 정점(Vertex)이고 '무언가'는 간선(Edge)가 됨 1-1. 관련 용어 - 방향 그래프, Directed Graph(Digraph): 간선에 방향성이 포함되어 있는 그래프 - 무방향 그래프, Undirected Graph: 간선에 방향성이 없는 그래프 - 인접 정점(adjacent vertext): 간선에 의해 직접 연결된 정점 - 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수(연결된 간선의 수) ▶︎ 무방향 그래프에 존재..
-
[자료구조 Java] 선형 자료 구조(연결 리스트, 배열, 스택, 큐)Computer Science/Data Structure 2022. 10. 5. 15:53
선형자료구조란? : 요소가 일렬로 나열되어 있는 자료 구조 1. 연결 리스트 : 데이터를 감싼 노드를 포인터로 연결해 공간적 효율성을 극대화 시킨 자료구조로, prev 포인터와 next 포인터로 앞과 뒤의 자료들을 연결시킨 것 1-1. 시간 복잡도 - 삽입/삭제 : O(1) - 탐색 : O(n) 1-2. 종류 1) 싱글 연결 리스트: next 포인터만 가짐 2) 이중 연결 리스트: prev, next 포인터를 둘 다 가짐 3) 원형 이중 연결 리스트: 마지막 노드의 next 포인터가 헤드 노드(맨 앞의 자료)를 가리킴 1-3. 주요 명령어 import java.util.LinkedList; import java.util.List; public class Example { public static void..
-
[자료구조 Java] 공간복잡도, 자료구조의 시간 복잡도Computer Science/Data Structure 2022. 10. 2. 13:57
[ 참고용: 시간복잡도 ] 출처: https://erinh.tistory.com/entry/자료구조-Java-시간복잡도-점근표기법-빅오표기법?category=1046468 공간복잡도란? : 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양 - 정적 변수로 선언된 것 외에, 동적인 재귀적 함수로 인해 공간을 계속해서 필요로 할 경우도 포함 - 시간복잡도와 마찬가지로 빅오표기법을 사용 - int 자료형 기준으로 배열 크기에 따른 메모리 사용량을 일반적으로 아래와 같음 int a[1000] : 4KB int a[1000000] : 4MB int a[2000][2000] : 16MB 자료구조에서의 시간 복잡도 1. 최악 시간 복잡도 자료구조 접근 탐색 삽입 삭제 배열 O(1) O(n) O(n) O(n) 스택..
-
[자료구조 Java] 시간복잡도 (점근표기법, 빅오표기법)Computer Science/Data Structure 2022. 10. 1. 14:34
시간복잡도란? : 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 ▶︎ 어떠한 알고리즘의 로직이 '얼마나 오랜 시간'이 걸리는지 나타날 때 사용되며 보통 Big-O 표기법으로 표현 📍점근 표기법 1) Big-O(빅오) : 상한 점근, 시간복잡도가 최악인 경우 2) Big-Ω(빅오메가) : 하한 점근, 시간복잡도가 최선인 경우 3) Big-Θ(빅세타): 상한, 하한의 평균(중간값) ▶︎ 빅오표기법의 경우, 프로그램 실행 과정에서 소요되는 최악의 시간까지 고려하기 때문에 효율적인 코드의 판단 척도로 사용 가능 // 시간복잡도 10n^2+n을 가지는 경우의 코드 for (int i = 0; i < 10; i++) { for (int j = 0; j < n; j++) { for ( int k = 0; k <..