🗒️ Data Structure (41)

1. 2017.06.21 [C] 탐색(Search)

   탐색(Search) [탐색이란?] - 탐색(search)은 컴퓨터가 가장 많이 하는 작업 중의 하나임. - 탐색은 컴퓨터 프로그램에서 가장 많이 사용하는 작업임과 동시에 많은 시간이 요구되므로 탐색을 효율적으로 수행하는 것은 매우 중요함. - 탐색은 기본적으로 여러 개의 자료 중에서 원하는 자료를 찾는 작업. - 탐색을 위하여 사용되는 자료 구조는 배열, 연결 리스트, 트리, 그래프 등 매우 다양할 수 있음. - 탐색 중에서 가장 기초적인 방법은 배열을 사용하여 자료를 저장하고 찾는 것. - 그러나 탐색 성능을 향상하고자 한다면 이진 탐색 트리와 같은 더욱 진보된 방법으로 자료를 저장하고 탐색해야 함. - 탐색의 단위는 항목이며, 항목은 간단하게 숫자일 수도 있고, 아니면 구조체가 될 수도 있음. - 항..
2. 2017.06.20 [C] 해싱(Hashing)

   해싱(Hashing) [해싱이란?] - 대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근함. - 하지만 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근함. - 해시 테이블(hash table) : 키 값의 연산에 의해 직접 접근이 가능한 구조 - 해싱(hashing) : 해시 테이블을 이용한 탐색 - 해싱은 일상생활에서의 정리 정돈으로 비유할 수 있음. - 키들의 비교에 의한 탐색 방법은 정렬이 안 되어 있으면 O(n)이고 정렬되어 있으면 O(log₂n). - 이 정도의 시간 복잡도가 허용되는 경우도 있는 반면, 어떤 경우는 더 빠른 탐색 방법이 필요함. - 해싱은 이론적으로는 O(1)의 시간 안..
3. 2017.06.19 [C] 그래프(Graph)

   그래프(Graph) [그래프란?] - 그래프(graph) : 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조. 예) 지도 - 지도를 그래프로 표시하면 하나의 도시에서 다른 도시로 갈 때 최단 거리 경로가 어떤 것인지를 알고리즘을 이용해 쉽게 찾을 수 있음. - 운영 체제에서 프로세스와 자원들이 어떻게 연관되는지를 그래프로 표현하게 되면 시스템의 효율이나 교착 상태 유무 등을 알아낼 수 있음. - 그래프는 많은 문제들을 표현할 수 있는 훌륭한 논리적 도구. - 선형 리스트나 트리의 구조로는 복잡한 문제들을 표현할 수 없음. - 그래프 구조는 인접 행렬이나 인접 리스트로 메모리 에 표현되고 처리될 수 있으므로 광범위한 분야의 다양한 문제들을 그래프로 표현하여 컴퓨터 프로그래밍에 의해 해결할 수 있..
4. 2017.06.18 [C] 정렬(Sorting)

   정렬(Sorting) - 정렬(sorting) : 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것. - 정렬은 컴퓨터공학을 포함한 모든 과학 기술 분야에서 가장 기본적이고 중요한 알고리즘 중의 하나로 일상생활에서 많이 사용됨. - 정렬은 자료 탐색에 있어서 필수적임. - 일반적으로 정렬시켜야 될 대상은 레코드(record)라고 불림. - 레코드는 다시 필드(field)라고 하는, 더 작은 단위로 나누어짐. - 여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드를 키(key)라고 함. 레코드 { [필드][필드][필드][필드][필드][필드][필드][필드][필드][필드] 레코드 { [필드][필드][필드][필드][필드][필..
5. 2017.06.17 [C] 우선순위 큐(Priority Queue)

   우선순위 큐(Priority Queue) - 컴퓨터에 우선순위의 개념이 필요할 때가 있음. 예) 네트워크 패킷 중에서 네트워크 관리와 관련된 패킷은 다른 일반 패킷보다 우선순위를 가짐. 예) 운영 시스템에서도 시스템 프로세스는 응용 프로세스보다 우선순위를 가지게 됨. - 따라서 자료 구조에서도 이러한 우선순위를 지원하는 것이 필요함. - 우선순위 큐(priority queue) : 우선순위의 개념을 큐에 도입한 자료 구조. - 보통의 큐는 선입 선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 되지만, 우선순위 큐에서는 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 됨. - 스택에 들어 있는 데이터들은 우선순위가 없음. 단지 먼저 들어간 데이터가 가장 늦게 나옴...
6. 2017.06.01 [C] 트리(Tree)

   트리(Tree) - 선형 자료 구조(linear data structure) : 자료들이 직선과 같이 나열되어 있는 구조 (리스트, 스택, 큐 등) - 트리는 계층적인 구조(hierarchical structure) 또는 비선형 자료 구조(nonlinear data structure)를 가지고 있으며, 계층적인 자료를 표현하는 데 이용되는 자료 구조. - 인공 지능 문제에서도 트리가 사용되는데 대표적인 것으로 결정 트리(decision tree)가 있음. - 결정 트리는 인간의 의사 결정 구조를 표현하는 한 가지 방법. [트리에서 쓰이는 용어] - 노드(node) : 트리의 구성 요소 - 트리는 한 개 이상의 노드로 이루어진 유한 집합임. - 이들 중 하나의 노드는 루트(root) 노드라고 불리고, 나머..
7. 2017.05.23 [C] 큐(Queue)

   큐(Queue) - 먼저 들어온 데이터가 먼저 나가는 구조. (선입 선출(FIFO: First-In-First-Out)) - 큐에서 삽입이 일어나는 곳을 '후단(rear)'이라고 하고, 삭제가 일어나는 곳을 '전단(front)'이라고 함. 선형 큐 (Linear Queue) - 배열로 구현된 큐. - 이해하기 쉽다는 장점이 있음. - 문제점 -> front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있어도 사용하지 못함. 따라서 주기적으로 모든 요소들을 왼쪽으로 이동시켜야 함. (상당한 시간이 걸리고 프로그램 코딩이 복잡해짐.) 원형 큐 (Circular Queue) - 선형 큐의 문제점을 보완하기 위해 배열을 원형으로 생각하여 만든 큐. - fr..
8. 2017.05.11 [C] 스택(Stack)

   스택(Stack) - 제일 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조. (후입 선출(LIFO: Last-In-First-Out) - 스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고, 반대쪽인 바닥 부분을 스택 하단(stack bottom)이라고 함. - 스택에 저장되는 것을 요소(element)라고 함. - 스택에 요소가 하나도 없을 때 스택을 공백 스택(empty stack)이라고 함. - 삽입 연산을 push 연산이라고 하고, 삭제 연산은 pop 연산이라고 함. - is_empty 연산과 is_full 연산은 스택이 공백 상태에 있는지와 포화 상태에 있는지를 검사함. - create 연산은 스택을 생성함. - peek 연산은 ..
9. 2017.05.06 [C] 이중 연결 리스트(Doubly Linked List)

   이중 연결 리스트(Doubly Linked List) - 응용 프로그램에서의 특정 노드에서 양방향으로 자유롭게 움직일 수 있는 리스트 구조. - 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트. - 링크가 양방향이므로 양방향으로 검색이 가능해짐. - 공간을 많이 차지하고 코드가 복잡해진다는 단점이 있음. - 실제 응용에서는 이중 연결 리스트와 원형 연결 리스트를 혼합한 형태가 많이 사용됨. - 헤드 노드(head node)라는 특별한 노드를 추가하는 경우가 많음. - 헤드 노드는 데이터를 가지고 있지 않은 특별한 노드를 의미함. cf) 헤드 포인터 : 리스트의 첫 번째 노드를 가리키는 포인터 - 헤드 노드가 존재하면 삽입, 삭제 알고리즘이 간편해짐. - 이중 연결 리스트에서의 ..
10. 2017.05.02 [C] 원형 연결 리스트(Circular Linked List)

    원형 연결 리스트(Circular Linked List) - 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트. -> 마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드 주소가 되는 리스트. - 한 노드에서 다른 모든 노드로의 접근이 가능하다는 장점이 있음. - 노드이 삽입과 삭제가 단순 연결 리스트보다는 용이해짐. - 삭제나 삽입 시에는 항상 선행 노드의 포인터가 필요함. - 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적일 수 있음. 코드 // 원형 연결 리스트 (Circular Linked List) #include #include typedef int element; typedef struct ListNode { element data; struct ListNo..
11. 2017.04.17 [C] 단순 연결 리스트(Singly Linked List)

    단순 연결 리스트(Singly Linked List) - 단순 연결 리스트는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결되어 있음. - 마지막 노드의 링크 필드 값은 NULL. - 첫 번째 노드를 가리키는 포인터(헤드 포인터) 값만 알고 있으면 연결 리스트 안의 모든 노드에 접근이 가능함. -> 하나의 단순 연결 리스트는 첫 번째 노드를 가리키는 하나의 포인터만 있으면 충분함. - 헤드 포인터(head pointer) : 첫 번째 노드를 가리키는 포인터 코드 #include typedef int element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; void error(cha..