'📂 자료구조' 카테고리의 글 목록

[자료구조] 05. 해쉬 테이블(Hash Table)

2023.06.19

해쉬 테이블 해쉬 테이블은 해시 값을 index로 삼아 key와 value를 저장하는 자료구조이다. 빠른 검색이 필요한 경우에 많이 사용되는 자료구조인데 내부적으로 배열을 사용하여 값을 저장하기 때문이다. 해쉬 테이블은 각 Key 값에 해쉬함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다. 이때 실제 값이 저장되는 장소를 버킷이라고 한다. 자바에서 제공하는 Hashtable 클래스를 살펴보면 해당 자료구조에 값을 저장할 때 아래의 그림처럼 동작한다. key를 자바에서 제공하는 해쉬함수인 hashCode()를 이용하여 해쉬 값으로 변경하고 그 변경한 값을 인덱스 값으로 또 계산하는 것을 볼 수 있다. 시간복잡도 추가, 삭제 : O(1) 검색 : O(1) 하..

📂 자료구조

[자료구조] 04. 연결 리스트(Linked List)

2023.06.09

연결 리스트(Linked List) 연결 리스트는 떨어진 공간에 있는 데이터들을 포인터를 이용하여 연결되어 있는 자료구조이다. 배열은 순차적으로 연결되어 있는 공간에 데이터를 넣는 자료구조여서 배열과는 다르다. 연결 리스트는 노드로 이루어져 있는데, 여기서 노드란 데이터와 포인터를 담고 있는 공간 단위이다. 포인터는 다음 노드의 주소 값을 저장하는 공간이다. 장점 미리 공간을 할당하지 않아도 됨 단점 연결을 위한 별도 공간이 필요하므로, 저장공간 효율이 좋지 않음 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림 중간 데이터 삭제 시, 앞 뒤 노드의 연결을 재구성해야 하는 부가적인 작업이 필요 연결 리스트를 직접 구현해보며 장,단점을 살펴보고 시간 복잡도에 대해서도 알아보자 구현 IList 인터페이스..

📂 자료구조

[자료구조] 03. 스택(Stack)

2023.06.07

스택(Stack) 스택은 데이터를 제한적으로 접근할 수 있는 자료구조이다. 앞선 글에서 설명한 큐는 FIFO 방식을 사용하는 자료구조이다. 스택은 LIFO(Last-In, First-Out) 방식을 사용하는 자료구조이다. 즉, 가장 마지막에 넣은 데이터를 가장 먼저 꺼내는 자료구조라고 할 수 있다. 이 자료구조가 활용되는 대표적인 예시로는 우리가 지금 사용하고 있는 Java의 JVM이다. JVM에는 메서드 호출 시, 스택 메모리에 메서드가 담기는데 이 때 스택 자료구조가 활용된다. 예를 들어 A메서드 안에서 B메서드를 호출한다고 가정해보자. 그럼 A메서드가 스택 영역에 할당되고, 그 다음 B메서드를 호출하는 부분에서 B메서드가 할당될 것이다. 당연하게도 메서드의 흐름상 B메서드가 먼저 동작이 끝날테니 B..

📂 자료구조

[자료구조] 02. 큐(Queue)

2023.06.01

큐(Queue) 큐는 먼저 입력한 데이터를 먼저 꺼내는 자료구조이다. FIFO(First-In, First-Out) 방식을 사용하는 자료구조라고도 할 수 있다. 이는 만약 우리가 식당에 줄을 서면 먼저 줄을 선 사람이 먼저 입장을 하는 것과 동일하다고 생각하면 될 것 같다. 위의 그림에 주요 용어들이 있는데, 설명하자면 아래와 같다. Enqueue : 큐에 값을 넣는 기능 Dequeue : 큐에서 값을 꺼내는 기능 head : 큐의 맨 앞 부분, front 라고도 함 tail : 큐의 맨 뒷 부분, rear 라고도 함 큐에 값이 추가된다면, tail 위치에 값이 Enqueue 될 것이다. 그리고 값을 지운다면 head의 값이 Dequeue 될 것이다. Enqueue 위의 그림처럼 큐는 선입선출 구조이고,..

📂 자료구조

[자료구조] 01. 배열

2023.06.01

배열(Array) 배열은 값을 나열하고, 각 값을 인덱스에 대응하도록 구성한 자료구조이다. 배열이 필요한 이유 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 같은 종유의 데이터를 순차적으로 저장 장점 값에 빠른 접근이 가능하다. (시간복잡도 O(1)) 단점 중간에 값을 추가, 삭제하기가 쉽지 않다. 미리 크기를 할당해야한다. 또는 배열의 크기를 가변할 수 없다. 위의 내용들을 자바로 예를 들어서 알아보려고 한다. 우선 먼저 배열을 만들어주는데, 위의 단점에 설명했듯이 배열은 선언할 때 미리 크기를 할당해야한다. 그래서 아래와 같이 크기가 7인 배열을 하나 만들어주자. int[] arr = new int[7]; 위의 그림처럼 크기가 7인 배열이 생성된다. int형의 배열을 생성했기 때문에 int 자..

[자료구조] 05. 해쉬 테이블(Hash Table)

[자료구조] 04. 연결 리스트(Linked List)

[자료구조] 03. 스택(Stack)

[자료구조] 02. 큐(Queue)

[자료구조] 01. 배열

티스토리툴바