본문 바로가기

전체 글

 (121)
자료구조 | 트리(Tree) 트리(Tree)는 데이터들의 구조가 실제 나무와 비슷하다고 해서 붙여진 이름이다(나무를 거꾸로 뒤집은 모습). 맨 꼭대기 노드인 루트(root)에서 시작하여 가지(branch)와 같은 여러 경로를 통해 맨 아래의 리프(leaf) 노드로 뻗어 나가는 구조를 가지고 있다. 그림 봐도 알겠지만 앞서 배웠던 자료구조들과 다르게 linear 하다고 보기엔 어렵다. 따라서 트리는 비선형 자료구조로 분류된다. 수많은 천재들이 트리를 잘 활용하는 법을 알아내준 덕에 우리는 데이터 관리를 위한 매우 뛰어난 도구를 몇가지 얻게 되었다. 특히 트리 구조는 탐색 기법으로 응용될 때 더 빛을 발하는데, 예를 들어 이진 탐색 트리(Binary Search Tree, BST)나 몬테카를로 트리 탐색(Monte-Carlo tree ..
Week 1. 자료구조/알고리즘 주차(1) 회고 자료구조/알고리즘 주차의 첫 일주일이 지났다. 정글은 매주 목요일을 기점으로 주차가 끝난다. (주말이라고 풀어지지 말라는 의미 ㅎ) 이번 주차는 지난주 미니프로젝트가 끝나고 토요일(10/14)에 시작했기 때문에 이틀 정도가 적었다. 그래서인지, 아님 아직 공부 방법이 잡히지 않아서인지 시간이 많이 부족했다... 점점 난이도가 올라갈 것이므로 배운 점 이번 주차엔 정글에 들어오면서 많이 기대했던 부분인 CS 지식 습득에 풀 집중 할 수 있었다. 이번주 공부 키워드는 다음과 같다. 배열, 문자열, 반복문 재귀 함수 복잡도(BigO, 시간, 공간) 정렬 (삽입 정렬, 퀵 소트, 머지 소트, 힙 소트) 완전 탐색, 이분 탐색, 분할 정복 자료구조 (스택, 큐, 우선순위 큐, Linked List, 해시 테이블)..
자료구조 | 해시 테이블(Hash Table) 해시 테이블은 'Key: Value'의 쌍을 저장하는 구조로, 고유한 Key를 기반으로 빠르게 데이터를 검색할 수 있게 해주는 자료구조이다. 이론적으로는 해시 테이블에서 원소를 찾는 것이 연결 리스트에서 원소를 찾는 것(최악의 경우 O(n)의 수행시간을 가진다)만큼 오래 걸릴 수 있지만 실제로 해싱은 성능이 탁월하다. 합리적인 가정 하에서 해시 테이블에서 원소를 찾는 데 걸리는 평균 수행시간은 O(1)이다. (출처: Introduction to Algorithms) 해싱(Hashing)이라는 개념은 1930년대에 처음 사용되었으며, 데이터 저장 및 검색 분야에 큰 혁신을 가져왔다고 한다. 'Hash'라는 단어는 'hack'에서 유래되었는데, 원래 의미는 '잘게 자르다'이다. 데이터를 작은 부분으로 나누어..
알고리즘 | 정렬 기법 | 병합 정렬(Merge Sort) Merge Sort는 이전 포스팅에서 공부했던 Quick Sort와 함께 분할 정복을 활용한 대표적인 정렬 기법이다. 1945년에 폰 노이만이 개발했다고 한다. 안정적인 정렬로 알려져 있으며, 데이터의 크기와 상관없이 일정한 성능을 보여준다는 장점이 있다. 따라서 대용량의 데이터를 정렬할 때 효과적이라고 한다. 앞서 Quick Sort가 Java에서 기본형 타입의 배열의 Array.sort() 메서드에 활용된다고 했는데, 객체 타입 배열의 Array.sort()에는 Tim Sort가 쓰인다. 파이썬의 list.sort()와 sorted(list)도 Tim Sort 기반으로 동작한다. 여기서 Tim Sort가 삽입 정렬(Insertion Sort)과 Merge Sort를 결합한 기법이다. 1. 핵심 아이디..
알고리즘 | 분할정복(Divide and Conquer) 분할 정복 알고리즘은 다양한 알고리즘 설계에서 핵심 원칙으로 사용되고 있다. 자주 접하는 개념 중에선 Quick Sort, Merge Sort가 분할 정복 알고리즘을 응용한 대표적인 예시이다. 고속 푸리에 변환(FFT)도 분할 정복 알고리즘 기반이라고 한다. 분할 정복 알고리즘 개념 분할 정복(Divide and Conquer)은 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 전략이다. Divide and Conquer라는 이름의 어원은 원래 정치와 군사 전략에서 사용되던 용어로, 큰 적 또는 문제를 작은 부분으로 나누어 각각을 해결함으로써 전체를 제어하는 전략을 의미한다고 한다. (나무위키에 따르면 제국주의 시절 유럽 식민제국이 식민지인들의 단결을 막기 위해 주로 사용한 방법으로 유명한 분..
자료구조 | 이중 연결 리스트, 원형 연결 리스트 이중 연결 리스트(Doubly Linked List)와 원형 연결 리스트(Circular Linked List)는 연결 리스트를 살짝 변형하여 단점을 개선한 자료구조이다. 연결 리스트를 배열과 비교했듯, 이들 역시 기본형인 단순 연결 리스트와 비교하면서 이해하는 게 효과적일 것 같다. 단순 연결 리스트 vs 이중 연결 리스트 vs 원형 연결 리스트 1. 개념 단순 연결 리스트: 일방향적. Head 노드 → Tail 노드 방향으로 포인터가 다음 노드 주소를 일방향적으로 가리킨다. 이중 연결 리스트: 양방향적. Head 노드 ↔ Tail 노드 양방향에서 다음 노드 주소를 양방향적으로 가리킨다. 원형 연결 리스트: 일방향적이나 순환적. Head 노드 → Tail 노드 일방향으로 포인터가 가리키지만, Tail ..
자료구조 | 연결 리스트(Linked List) 연결 리스트는 그 유연성과 동적인 특성 때문에 매우 중요한 자료구조로 간주된다. 연결 리스트는 여러개의 노드가 이어지는 형태로 구성되어 있다. '각 노드 = 데이터(data) + 포인터(next)' 이다. 해당 자료구조의 특징에 대해서는 배열(Array)과의 비교를 통해 이해하는 것이 가장 효율적일 것 같다. 그 이후에 단순 연결 리스트의 변형인 이중 연결 리스트, 원형 연결 리스트에 대해 비교해보자. 연결 리스트(Linked List) vs 배열 (Array) 1. 개념적 차이 배열 : 데이터가 메모리 상 연속된 공간에 할당된다. 즉, '논리적 저장 순서'와 '물리적 저장 순서'가 일치한다. 연결 리스트 : 연결 리스트의 노드들은 메모리 상 불연속적인 공간에 존재한다. 즉, '논리적 저장 순서'와 '물..
알고리즘 | 정렬 기법 | 퀵 정렬 (Quick Sort) Quick sort는 1961년 Tony Hoare(토니 호어)가 발표한 정렬 기법이다. 정렬 기법 중에서 매우 흔히 사용되는 기법으로, 현대에는 Quick Sort에 여러 가지 최적화 기법을 추가한 변형을 자주 사용한다. 예를 들어, Java의 Array.sort() 메서드는 기본형 타입의 배열(int, long 등)에 대해서는 Dual-Pivot Quick Sort를 사용한다고 한다. (객체 배열에 대해서는 Tim Sort를 사용한다.) - Dual-Privot Quick Sort: Insertion Sort와 Quick Sort를 결합한 정렬 기법 - Tim Sort: Insertion Sort와 Merge Sort를 결합한 정렬 기법 1. 핵심 아이디어 분할 정복 전략을 사용하여 리스트를 정렬한다..

티스토리툴바