본문 바로가기

알고리즘/알고리즘 도감

 (44)
힙 지난 글: [알고리즘] - 해시 테이블 힙(heap)은 그래프의 트리 구조 중 하나로, '우선순위 큐(priority queue)'를 구현할 때 사용된다. 우선순위 큐는 데이터 구조의 하나로서 데이터를 자유롭게 추가할 수 있다. 반면, 데이터를 추출할 때는 최솟값부터 순서대로 선택된다. 추가는 자유롭게 하고 추출할 대는 작은 값부터 꺼내는 것이 우선순위 큐이다. 또, 힙을 표현하는 트리 구조에서는 각 정점을 '노드(node)'라고 부른다. 힙에서는 각 노드에 데이터가 저장된다. 1 1, 3, 6, 4, 8, 7 순서대로 각 노드에 숫자가 적혀 있다. 적혀 있는 숫자가 저장돼 있는 데이터이다. 이 노드들은 최대 두 개의 자식 노드를 갖는다. 또, 트리 모양은 데이터 개수에 의해 정해진다. 노드는 위에서부터..
해시 테이블 지난 글: [알고리즘] - 큐 해시 테이블(hash table)은 데이터 구조의 하나이며, 데이터 검색을 효율적으로 하기 위해 사용되는 구조이다. 1 해시 테이블은 키(key)와 값(value)이 한 쌍을 이루는 데이터를 저장한다. 예로 각 사람의 성별을 데이터로 저장하고 있으며, 이름을 키로, 성별을 값으로 저장하고 있다. 일반적으로 키는 데이터 식별자, 값은 데이터의 내용이라고 생각하면 된다. 2 해시 테이블의 특징을 비교하기 위해 먼저 데이터를 '배열'에 저장하는 경우를 생각해보자. 3 6개의 상자로 이루어진 배열을 준비하고 데이터를 저장한다(상자 번호는 내림차순). 여기서 상자에 저장된 Ally의 성별이 알고 싶다. 하지만 나는 Ally가 배열의 몇 번째 상자에 저장돼 있는지 모른다. 그러므로 앞..
큐 지난 글: [알고리즘] - 스택 큐(Queue)는 데이터 구조의 하나로, 여태 배운 것들과 마찬가지로 데이터를 1열로 나열한 구조이다. 스택과 비슷하지만 큐는 추가하는 측과 삭제하는 측이 반대이다. 큐는 '대기 행렬'이라고 불린다. 1 큐에 데이터를 추가하면 가장 위에 추가된다. 현재 'Blue'라는 데이터만 큐에 저장돼 있다. 2 'Green'이라는 데이터를 추가한다. 큐에 데이터를 추가하는 작업을 '인큐(enqueue)'라고 하며, 추가된 데이터는 기존에 있던 'Blue' 데이터 위에 쌓인다. 3 다시 'Red' 데이터를 인큐한다. 4 큐에서 데이터를 꺼낼 때는 가장 아래, 즉 가장 오래된 데이터부터 꺼낸다. 여기서는 'Blue'가 추출된다. 큐에서 데이터를 꺼내는 작업을 '디큐(dequeue)'라고..
스택 지난 글: [알고리즘] - 배열 스택(stack)은 데이터 구조의 하나로서 데이터를 1열로 나열하지만, 쌓아놓은 서류처럼 새롭게 추가한 데이터에만 접근할 수 있다. 새로운 서류가 도착하면 현재 서류 더미의 가장 위에 올려두고 서류를 꺼낼 때는 가장 위에서부터 꺼내는 것과 같다. 1 현재 스택에 'Blue'라는 데이터만 저장돼 있다. 2 여기에 'Green'이라는 데이터가 추가됐다. 3 'Red'라는 데이터를 또 푸시한다. 4 스택에서 데이터를 꺼내는 경우 가장 위, 즉 가장 최근에 추가된 데이터부터 꺼낸다. 여기서는 'Red'가 추출된다. 5 다시 팝을 하면 'Green'이 추출된다. 부연: 스택처럼 나중에 넣은 것을 먼저 꺼내는 후입선출 구조를 'Last In First Out'이라 하며 앞글자만 따 ..
배열 지난 글: [알고리즘] - 리스트 배열은 데이터 구조의 하나로, 데이터를 1열로 나열한 것이다. 지난 글의 리스트와는 대도적으로 데이터에 접근하기는 쉽지만 추가나 삭제에 시간이 걸린다. 1 배열의 개념도이다. 세 개의 문자열 "Blue", "Yellow", "Red"가 데이터로 저장되어 있다. 2 데이터는 연속된 메모리 영역에 순서대로 저장된다. 3 연속된 영역에 저장돼 있어 첨자를 사용해 메모리의 주소를 계산할 수 있다. 따라서 각 데이터에 바로 접근할 수 있다. 이것을 임의 접근(random access, 랜덤 액세스)이라고 한다. 4 예를 들어 "Red"에 접근하고 싶다면 a[2]라고 지정하여 쉽게 "Red"에 접근 가능하다. 5 배열은 임의의 위치에 데이터를 추가, 삭제해야 하는 경우에 리스트에 ..
리스트 지난 글: [알고리즘] - 데이터 구조란? 리스트(list)는 데이터 구조의 하나로, 데이터를 일직선으로 나열한 형태를 가지고 있다. 데이터 추가나 삭제는 쉽지만, 원하는 데이터에 접근하려면 시간이 많이 걸린다. 1 Blue -> Yellow -> Red // -> = 포인터 이것이 리스트의 개념도이다. 세 개의 문자열 "Blue", "Yellow", "Red"가 데이터로 저장되어 있다. 각 데이터에는 '포인터(pointer)가 있으며, 다음 데이터의 메모리 위치를 가리킨다. "Red"는 마지막 데이터이므로 "Red"의 포인터는 아무것도 가리키지 않는다. 2 리스트에서는 데이터가 메모리상의 연속된 위치에 저장되지 않아도 되며 일반적으로 떨어진 영역에 흩어져서 저장된다. 3 흩어져 저장돼 있으므로 포인터를..
데이터 구조란? 지난 글: [알고리즘] - 계산 시간을 표현하는 방법 데이터의 순서나 위치 관계를 정한다 컴퓨터 안에서 데이터는 메모리에 저장된다. 메모리는 상자가 일렬로 나열된 형태를 하고 있으며 하나의 상자 안에 하나의 데이터를 저장한다. 데이터를 메모리에 저장할 때 데이터의 순서나 위치 관계 등을 정하는 것이 '데이터 구조'이다. 전화번호부의 데이터 구조 알기쉬운 예로 전화번호부를 생각해보자. 여기서 전화번호부는 수기로 작성하는 것이다. ex1) 위에서부터 차례로 추가 전화번호부를 관리하는 가장 일반적인 방법은 전화번호를 얻을 때마다 종이 위에서부터 차례로 기입하는 방법이다. 만약 '김예찬'이라는 사람을 찾아서 전화하고 싶다. 그러면 전화번호는 단순히 번호를 받은 순서로 저장되어 있기에 앞에서부터 순서대로 찾는 방..
계산 시간을 표현하는 방법 지난 글: [알고리즘] - 계산 시간 구하는 법 지난 글에서 계산 시간을 구하는 법을 배웠었다. 이제 그 결과를 간략화하는 방법을 배워보자. Tc와 Ts는 기본 단위로 입력과는 무관하다. 입력에 의해 바뀌는 것은 수열의 길이인 n이므로 선택 정렬의 실행시간은 n을 크게하면 할수록 입력 수열의 크기 n의 2승만큼 비례해서 바뀐다. 알고리즘의 계산 시간 표시는 O(n의 제곱) 식으로 표기한다. 이를 보았을 때, O(n)과 O(n의 2승) 중 어느 것이 계산 시간이 더 짧은지를 알 수 있다. 솔직히 뭔말인지 모르겠다. 책에 수식이 첨부 되어있기는 하나 수랑 안친해서 잘 모르겠다. 아마 알고리즘은 오랜 시간을 들여 친해져야 할 것 같다. 참고 서적:

티스토리툴바