2024. 11. 19. 14:57ㆍ코딩테스트/알고리즘
자료구조란?
1. 자료구조의 정의
- 자료구조란 일련의 자료들을 조직하고 구조화하는 것이다.
- 효율적인 프로그램을 작성할 때 가장 우선적인 고려사항은 저장 공간의 효율성과 실행시간의 신속성이다.
- 자료구조는 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과,
저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법등을 연구 분석하는 것을 말한다.
2. 자료구조의 분류
- 원시형/비원시형
원시형: 기본형, 내장형 자료구조
비원시형: 원시형을 묶어서 만든 자료구조
- 선형구조
- 데이터가 순차적으로 나열된 구조.
- 요소 간의 순서가 명확하고, 데이터가 메모리 상에서 연속적으로 저장되거나 포인터로 연결된다.
- 예: 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue) 등.
- 비선형구조
- 데이터가 계층적(Hierarchical) 또는 비순차적(Non-sequential)으로 저장된 구조.
- 데이터 간의 관계가 더 복잡하며, 특정 키를 통해 데이터를 검색하거나 계층 구조를 표현할 때 사용된다.
- 예: 트리(Tree), 그래프(Graph), 해시 기반 자료구조(Map, Set) 등.
1. 배열 (Array)
1) 개념
- 같은 타입을 여러 변수를 하나의 묶음으로 다루는 것
- 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합
- 메모리에서 물리적으로 연달아서 저장된다
- 사용한 첨자의 개수에 따라 n차원 배열이라 부른다.
- 장점
- 접근 속도가 빠름. 반복적인 처리 작업에 적합.
- 첨자(index)를 이용하여 데이터에 바로 접근하므로 데이터(요소)마다 동일한 이름의 변수를 사용하여 처리가 간편하다.
- 단점
- 정적인 자료구조로 기억장소를 고정하므로 생성 이후 추가가 어렵다 (가변성이 없음)
- 데이터 삭제 시 데이터가 저장되어 있던 기억장소는 빈 공간으로 남아있어 메모리의 낭비가 발생한다.
2) 자바에서 사용
int[] arr; //선언 (배열을 다루기 위한 참조변수 선언)
int[] arr = new int[5]; //선언+생성 (실제 저장공간을 생성)
int[] arr2 = new int[5] {1,2,3,4,5}; //선언+생성+초기화 (배열 생성할 때만 가능)
int[] arr3 = {1,2,3,4,5}; //생략가능
int[0] = 10; //값 넣기
int a = int[0]; //값 가져오기
//향상된 for문
for(int i : arr) {..}
2. 리스트 (List)
1) 연결리스트 (Linked List) 개념
- 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되,
- 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결 시킴
- 장점
- 연결리스트는 노드의 삽입과 삭제 작업이 용이하다
- 메모리를 효율적으로 사용 가능
- 단점
- 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.
- 연결을 위한 링크(포인터)부분이 필요하기 때문에 순차리스트에 비해 기억공간을 많이 차지한다.
2) 자바에서 사용
- List 컬렉션은 객체를 일렬로 늘어놓은 구조로 이루어져 있다.
- List 컬렉션 인터페이스에는 객체를 추가(add), 검색(contain, get, size), 삭제(remove, clear) 기능의 메서드가 선언되어 있다.
그러므로 List 컬렉션 인터페이스를 상속해서 구현하는 클래스는 해당 기능을 오버라이드 해야한다.
- List 컬렉션 인터페이스를 구현한 클래스 종류
ArrayList
- 일반 배열과 ArrayList는 인덱스로 객체를 관리한다는 점에서 동일하지만, 크기를 동적으로 늘릴 수 있다는 점에서 차이점이 있다.
- 배열처럼 ArrayList에서 특정 인덱스의 객체를 제거하게 되면, 제거한 객체의 인덱스부터 마지막 인덱스까지 모두 앞으로 1칸씩 앞으로 이동한다. 이처럼 객체 삭제와 삽입이 빈번하게 일어나는 곳에서 ArrayList를 사용하지 않고 LinkedList를 사용하는 것이 좋다.
- ArrayList는 인덱스가 있으므로 객체 검색, 맨 마지막에 객체 추가 등에서 좋은 성능을 발휘한다.
LinkedList
- ArrayList에는 내부 배열에 객체를 저장해서 인덱스로 관리하지만, LinkedList는 인접 참조를 링크해서 체인처럼 관리한다.
- 그렇기 때문에 LinkedList에서 특정 인덱스의 객체를 제거하게 되면, 제거되는 인덱스의 앞 뒤 링크만 변경되고 나머지 링크는 변경되지 않는다. ArrayList는 제거되는 인덱스를 기준으로 뒤에 있는 객체가 한칸씩 이동 했었던 점과 차이가 있다.
- 이러한 차이로 인해서 객체를 삽입, 삭제하는 로직에 있어서 ArrayList보다 LinkedList를 사용할 때 좋은 성능이 나옵니다.
List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();
list.add("hi"); //객체 추가
String str = list.get(0); //인덱스에 위치하는 객체 값 얻기
list.remove(0); // 인덱스를 이용하여 객체 삭제
int size = list.size(); // 객체 총 개수
boolean isFindValue = list.contains("gglee"); // 동일한 객체 있는지 검색
//for문에서 리스트에 인덱스값으로 접근하는 것은 구조상 비효율적임
//효율적으로 리스트 값 가져오기 위해서는 향상된 for문 사용
for(String s: arrayList) {}
Interator i = arrayList .iterator();
while (i.hasNext()) i.next;
arrayList.stream().forEach();3. 스택
1) 개념
- 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조
- LIFO(Last In First Out) 방식으로 자료를 처리한다.
- 오버플로/언더플로
- 스택의 모든 기억공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로(Overflow),
- 더이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로(Underflow)가 발생한다.
- Top/Bottom
- Top: 스택의 할당된 기억공간에서 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소
- Bottom: 스택의 가장 밑바닥
2) 자바에서 사용
import java.util.Stack; //import
Stack<Element> stack = new Stack<>(); //int형 스택 선언
stack.push(값); // 값 추가
stack.pop(); // stack의 첫번째 값을 반환하고 제거, 비어있다면 null
stack.peek(); // stack의 가장 상단의 값 반환만하고 제거X
stack.clear(); // stack의 전체 값 제거 (초기화)
stack.size(); // stack의 크기 출력
stack.empty(); // stack이 비어있는지 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)
4. 큐 (Queue)
1) 개념
- 한쪽에서는 삽입 작업이, 다른 한쪽 끝에서는 삭제 작업이 이루어지도록 구성한 자료 구조
- FIFO(First In First Out) 방식으로 자료를 처리한다 .
- 시작과 끝을 표시하는 두 개의 포인터가 존재한다. (Front포인터, Rear포인터)
- Priority Queue
- 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 (큐에 들어가는 원소는 비교가 가능한 기준이 있어야함)
- 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있음
2) 자바에서 사용
import java.util.LinkedList; //import
import java.util.Queue; //import
Queue<Element> queue = new LinkedList<>() //큐 선언
queue.offer(값); // 값 추가
queue.poll(); // queue에 첫번째 값을 반환하고 제거, 비어있다면 null
queue.peek(); // queue의 첫번째 값 반환만하고 제거X
queue.clear(); // queue 초기화
queue.size(); // queue의 크기 출력
queue.isEmpty(); // queue가 비어있는지 check (비어있다면 true)
//우선순위큐
PriorityQueue<Integer> queSmall = new PriorityQueue<>(); //작은 수가 우선
PriorityQueue<Integer> queBig = new PriorityQueue<>(Collections.reverseOrder()); //큰 수가 우선
queBig.offer(1);
queBig.offer(9);
queBig.offer(7);
System.out.println(queBig.poll()); //9
System.out.println(queBig.poll()); //7
System.out.println(queBig.poll()); //3add()와 offer()의 차이 ▼
|
|
Throws exception
|
Returns special value
|
|
Insert
|
add(e)
|
offer(e)
|
|
Remove
|
remove()
|
poll()
|
|
Examine
|
element()
|
peek()
|
5. 데크 (Deque)
- 양쪽 끝에서 삽입과 삭제 작업이 가능하도록 구성한 자료구조
- 스택과 큐를 혼합시킨 형태
- 두 개의 bottom포인터가 존재한다. (L-bottom, R-bottom)
- 종류: 입력 제한 데크(스크롤), 출력 제한 데크 (쉘프)
그래프 : 엉망진창 리스트
트리: 그래프 + 형태 상의 규칙
힙: 그래프 + 내용 상의 규칙
6. 그래프 (Graph)
- 정점(Vertex)와 간선(Edge)들로 이루어진 자료구조
- 트리와 달리 루트 노드 개념이 없으며 정점 간의 부모 자식관계가 없다.
- 그래프의 간선은 방향성을 가지거나, 가지지 않을 수 있다. (방향/무방향 그래프)
- 그래프는 자기 자신을 잇는 간선을 가질 수 있다.
- 구현: 인접행렬, 인접리스트
- 종류: 방향/무방향 그래프, 다중/단순 그래프, 가중치 그래프, 이분 그래프, 희소/밀집 그래프, 완전/부분 그래프
7. 트리 (Tree)
1) 개념
- 정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 "사이클을 이루지 않도록 구성한" 그래프의 특수한 형태
- 트리는 나무를 뒤집은 모습으로 계층 구조를 표현하기에 적합
2) 용어
- 노드: 하나의 기억공간, 링크: 노드와 노드를 연결하는 선
- 루트노드: 트리 맨 위에 있는 노드, 단말노드: 자식이 하나도 없는 노드
- 부모, 자식, 형제 노드
- 차수: 각 노드에서 뻗어나온 가지의 수 (트리의 차수는 노드들의 차수 중 가장 많은 수)
- 깊이: 트리의 최대 레벨
3) 종류
- 이진 트리: 모든 노드들의 자식 노드가 두 개 이하인 트리, 배열이나 연결리스트로 구현 가능
- 이진 탐색 트리: 이진 트리이면서, 중복 값을 갖는 노드가 없는 트리.
데이터의 삽입, 삭제, 탑색들리 자주 발생하는 경우에 효율적인 구조이다.
8. 힙 (Heap)
- 완전 이진 트리 형태로 구성된 비선형 자료구조입니다.
- 주로 우선순위 큐(priority queue)를 구현하는 데 사용됩니다.
- 특성: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작다.
- 최대 힙(Max Heap): 부모 노드가 자식 노드보다 값이 크거나 같은 구조 (최대값이 루트에 위치).
- 최소 힙(Min Heap): 부모 노드가 자식 노드보다 값이 작거나 같은 구조 (최소값이 루트에 위치).
- 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
- 힙의 주요 연산은 삽입(Insert)과 삭제(Delete)이며, 둘 다 O(log n)의 시간 복잡도를 가집니다.
9. 맵 (Map)
1) 개념
- 키-값(Key-Value) 쌍으로 데이터를 저장하는 자료구조
- 해쉬 맵: 키와의 맵핑에 해시값을 이용
- 각 키는 고유하며, 키를 통해 값에 접근할 수 있다.
- 키는 중복될 수 없으며, 값은 중복될 수 있습니다.
- 키를 사용해 데이터를 검색, 업데이트, 삭제하는 데 효율적입니다.
- 장점: 엑세스가 빠르면서(배열), 추가 삭제가 편함(리스트)
- 단점: 메모리를 많이쓴다 (배보타 배꼽이 커질수있다)
- 사용사례
- 데이터의 매핑 관계를 표현할 때 (예: 학생 ID와 이름).
- 빠른 검색, 삽입, 삭제가 필요한 경우.
2) 자바에서 사용 (HashMap)
HashMap<Integer,String> map = new HashMap<>(); //HashMap 선언 및 생성
map.put(1,"사과"); //값 추가
map.get(1); //key값 1의 value얻기 : 사과
map.remove(1); //key값 1 제거
map.clear(); //모든 값 제거
map.size(); //개수 리턴
map.containsKey(1) //key값 1 검색 -> true
map.containsValue("바나나"); //value값 "바나나" 검색 -> false
//getOrDefault(map에서 찾을 key값(있으면 key값의 value 리턴), map에 해당하는 key값이 없으면 리턴할 디폴트값);
map.getOrDefault(1, "없음"); // map의 key값으로 1이 있으면 "사과" 리턴, 없으면 "없음" 리턴
// map 출력
for (String key : map.keySet()) {
String value = map.get(key);
System.out.println("[key]:" + key + ", [value]:" + value);
}
10. 셋 (Set)
1) 개념
- Set은 중복을 허용하지 않는 데이터의 집합입니다.
- 순서와 관계없이 고유한 값들로만 이루어져 있습니다.
- 요소(Element)는 중복될 수 없습니다.
- 순서는 보장되지 않지만, 특정 구현체에서 정렬된 Set을 사용할 수 있습니다.
- 사용 사례
- 유일한 값을 저장하고 싶을 때.
- 중복 데이터 제거가 필요할 때.
- Map과 Set의 차이점 요약
| Map | Set | |
| 데이터 구조 | 키-값(Key-Value) 쌍 | 고유한 요소의 집합 |
| 중복 허용 여부 | 키는 중복 불가, 값은 중복 가능 | 중복 요소 불가 |
| 주요 사용 목적 | 키로 값에 빠르게 접근 | 중복 제거 및 고유 값 관리 |
| 주요 구현체 | HashMap, TreeMap, LinkedHashMap | HashSet, TreeSet, LinkedHashSet |
2) 자바에서 사용 (HashSet)
HashSet<Integer> set = new HashSet<Integer>(); //생성
set.add(1); //값 추가
set.remove(1); //값 1 제거
set.clear(); //모든 값 제거
set.contains(1); //boolean 리턴
//출력
Iterator iter = set.iterator(); // Iterator 사용
while(iter.hasNext()) {//값이 있으면 true 없으면 false
System.out.println(iter.next());
}