🗒️ Computer Science (60)

1. 2021.06.25 0-1 배낭 문제(0-1 Knapsack Problem)

   0-1 배낭 문제(0-1 Knapsack Problem) 조건 물건들의 집합 O = {O₁, O₂, ..., On}이 있을 경우 Wi : i번째 물건 Oi의 무게 Vi : i번째 물건의 가격(Value) 최대 무게를 T까지 견딜 수 있는 가방(배낭)이 1개 주어짐. 물건들을 가방에 담아야 함. 가방에 넣은 물건들의 가격(V) 합이 최대가 되도록 물건 선택 단, 물건들의 무게 합이 T를 넘지 않아야 함. 예 : 무역을 하는 상인이 매출의 일정 비율을 이익으로 가져갈 떄 이익을 극대화하려면 최대한 비싼 물건들을 가지고 다니면서 팔아야 하지만, 사용할 수 있는 운송 수단(또는 배낭)에는 최대 T 무게까지의 물건말 실을 수 있음. 각각의 물건에 대한 무게(W)와 가격(V)은 이미 알고 있음. 물건들을 어떻게 조..
2. 2021.06.24 최단 작업 우선 스케줄링(Shortest-Job-First Scheduling)

   최단 작업 우선 스케줄링(Shortest-Job-First Scheduling) 그리디 알고리즘(Greedy Algorithm)으로 해결할 수 있는 문제 중 하나 예 : 은행 창구 하나의 창구에서만 업무를 보고 있음. 대기열에 N명의 사람이 기다리고 있음. 서로 다른 용무로 방문했기 떄문에 일 처리에 필요한 시간은 사람들마다 서로 다름. 대기열에 기다리고 있던 모든 사람이 매우 합리적이어서 평균 대기 시간이 최소화될 수 있도록 대기 순서를 다시 정하는 것 에 동의하였음. 그래서 이제 대기 순서를 어떻게 바꿔야 하는지를 결정해야 함. 항목 Pi : i번째 사람 Ai : Pi의 일 처리 시간 Wi : Pi가 기다려야 하는 시간 창구에서 가까운 사람이 먼저 일을 처리할 수 있으므로 첫 번째 사람 P0의 대기 ..
3. 2021.06.09 [C++] 맵(Map)과 리듀스(Reduce)

   맵(Map)과 리듀스(Reduce) 맵과 리듀스라는 용어는 Lisp와 같은 함수형 프로그래밍 언어에서 기원함. 맵(Map) 컨테이너 C를 입력으로 받아, 컨테이너의 모든 원소에 함수 f(x)를 적용하는 연산 예) f(x) = x² 함수를 사용할 경우에 대한 맵 연산 리듀스(Reduce) 컨테이너 C의 모든 원소 x에 함수 f(acc, x)를 적용하여 하나의 값으로 축약하는 연산 예) f(acc, x) = acc + x 함수를 사용할 경우에 대한 리듀스 연산 코드 #include #include #include #include #include void transform_test(std::vector S) { std::vector Tr; std::cout
4. 2021.06.07 선형 시간 선택(Linear Time Selection)

   선형 시간 선택(Linear Time Selection) 각 단계에서 문제를 2개 이상 분할하여 문제를 해결하는 알고리즘 ① 벡터 $V$가 주어지면, 여기서 i번째로 작은 원소를 찾으려고 함. ② 입력 벡터 $V$를 $V_{1}, V_{2}, V_{3}, ..., V_{n/5}$ 으로 분할함. 각각의 부분 벡터 $V_{i}$ 는 5개의 원소를 가지고 있음. 마지막 $V_{n/5}$ 는 5개 이하의 원소를 가질 수 있음. ③ 각각의 $V_{i}$ 를 정렬함. ④ 각각의 $V_{i}$ 에서 중앙값 $m_{i}$ 를 구하고, 이를 모아서 집합 M을 생성함. ⑤ 집합 M에서 중앙값 q를 찾음. ⑥ q를 피벗으로 삼아 전체 벡터 V를 L과 R의 두 벡터로 분할함. ⑦ 이러한 방식으로 분할하면 부분 벡터 L은 q보..
5. 2021.06.02 [C++] 퀵 정렬(Quick Sort)

   퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘 을 이용하여 구현됨. 병합 정렬과 퀵 정렬의 비교 병합 정렬(Merge Sort) 대용량의 데이터 정렬 퀵 정렬(Quick Sort) 평균 실행 시간을 줄이는 것 기본 아이디어는 병합 정렬과 같음. 원본 입력 배열을 작은 크기의 부분 배열로 나눔. 각 부분 배열을 정렬함. 그 결과를 합쳐서 전체 정렬 배열을 생성함. 핵심 병합(Combine)이 아니라 분할(Split) 입력 배열이 주어지고, 입력 배열 중 피벗(Pivot) 원소 P를 선택했을 경우, 퀵 정렬을 위한 분할 연산 은 다음의 2단계로 이루어짐. ① 입력 배열을 2개의 부분 배열 R과 L로 나눔. L 입력 배열에서 P 보다 작거나 같은 원소를 포함하..
6. 2021.06.02 [C++] 병합 정렬(Merge Sort)

   병합 정렬(Merge Sort) 병합 정렬은 분할 정복(Divide and Conquer) 알고리즘 을 이용하여 구현됨. 병합 알고리즘은 다음과 같은 과정으로 정렬을 수행함. ① 많은 원소로 구성된 전체 집합을 작은 크기의 부분 집합 으로 나눔. ② 각각의 부분 집합을 정렬함. ③ 정렬된 부분 집합을 오름차순 또는 내림차순 순서를 유지함. ④ 각각의 부분 집합을 합침. 그림) 병합 정렬을 사용하여 정수 배열을 정렬하는 예 전체 배열을 여러 개의 부분 배열로 나누는 작업을 반복함. 각 부분 배열이 하나의 원소를 가질 때 멈춤. (1단계 ~ 4단계) 이후에는 다시 배열을 합치는 작업을 반복함. 합쳐진 배열의 원소 순서가 오름차순을 유지하도록 조정함. 코드 템플릿을 사용하여 정렬할 데이터 타입에 의존적이지 않..
7. 2021.05.29 [C++] 선형 탐색(Linear Search), 이진 탐색(Binary Search)

   선형 탐색(Linear Search), 이진 탐색(Binary Search) 선형 탐색(Linear Search) 시퀀스 전체 원소를 방문하면서 해당 원소가 N과 같은지 확인 다음과 같은 코드로 구현할 수 있음. bool linear_search(int N, std::vector& sequence) { for (auto i : sequence) { if (i == N) { return true; // 찾음! } } return false; } 장점 입력 시퀀스의 정렬 여부와 상관없이 항상 잘 동작함. 단점 효율적이지 않음. 주어진 배열이 정렬되어 있다는 점을 전혀 이용하지 못함. 시간 복잡도 : O(N) 이진 탐색(Binary Search) 주어진 시퀀스가 정렬되어 있다는 사실을 이용하여 검색하는 방법 ..
8. 2021.05.28 [C++] 블룸 필터(Bloom Filter)

   블룸 필터(Bloom Filter) 해시 테이블에 비해 공간 효율이 매우 높은 방법 결정적(Deterministic) 솔루션 대신 부정확한 결과를 얻을 수 있음. 거짓-부정(Fals Negative) 이 없다는 것은 보장하지만, 거짓-긍정(False Positive) 은 나올 수 있음. 특정 원소가 존재한다는 긍정적인 답변을 받을 경우, 이 원소는 실제로 있을 수도 있고 없을 수도 있음. 그러나 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면, 이 원소는 확실히 없음. 뻐꾸기 해싱과 마찬가지로 블룸 필터도 여러 개의 해시 함수를 사용함. 보통 2개의 해시 함수는 충분한 정확도를 기대하기 어렵기 때문에 3개 이상을 사용해야 함. 블룸 필터는 실제 값을 저장하지는 않음. 대신 특정 값이 있는지 없는지..
9. 2021.05.22 [C++] 뻐꾸기 해싱(Cuckoo Hashing)

   뻐꾸기 해싱(Cuckoo Hashing) 크기가 같은 2개의 해시 테이블을 사용함. 각각의 해시 테이블은 서로 다른 해시 함수 를 가짐. 모든 원소는 두 해시 테이블 중 하나에 있을 수 있음. 위치는 해당 해시 테이블의 해시 함수 에 의해 결정됨. 뻐꾸기 해싱이 다른 해싱 기법과 다른 점 원소가 두 해시 테이블 중 어디든 저장될 수 있음. 원소가 나중에 다른 위치로 이동할 수 있음. 다른 해싱 방법에서는 재해싱을 수행하지 않는 이상 원소가 최초 삽입된 위치에서 다른 위치로 이동할 수 없음. 그러나, 뻐꾸기 해싱 방법에서는 모든 원소가 2개의 저장 가능한 위치를 가지며, 상황에 따라 이동할 수 있음. 더 나은 성능을 얻고, 재해싱 빈도를 줄이기 위해 저장 가능한 위치 개수를 증가 시킬 수도 있음. 룩업 연..
10. 2021.05.20 [C++] 체이닝(Chaining)을 이용한 해시 테이블(Hash Table) 구현

    체이닝(Chaining)을 이용한 해시 테이블(Hash Table) 구현 체이닝(Chaining) 해시 테이블에 두 값을 모두 저장할 수 있는 여러 방법 중 하나 해시 테이블의 특정 위치에서 하나의 키 를 저장하는 것이 아니라 하나의 연결 리스트 를 저장함. 새로 삽입된 키에 의해 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가함. 따라서 다수의 원소를 원하는 만큼 저장할 수 있음. 벡터 대신 연결 리스트를 사용하는 이유? 특정 위치의 원소를 빠르게 삭제하기 위함. 코드 #include #include #include #include using uint = unsigned int; class hash_map { std::vector data; public: hash_map(size_t n) { dat..
11. 2021.05.19 [C++] 인접 리스트를 이용하여 그래프 구현하기

    인접 리스트를 이용하여 그래프 구현하기 서론 인접 리스트(Adjacent List)를 이용하여 그래프(Graph)를 구현해보자. 코드 #include #include #include enum class city : int { MOSCOW, LONDON, SEOUL, SEATTLE, DUBAI, SYDNEY }; std::ostream& operator
12. 2021.05.19 [C++] 인접 행렬을 이용하여 그래프 구현하기

    인접 행렬을 이용하여 그래프 구현하기 서론 인접 행렬(Adjacent Matrix)을 이용하여 그래프(Graph)를 구현해보자. 코드 #include #include enum class city : int { MOSCOW, LONDON, SEOUL, SEATTLE, DUBAI, SYDNEY }; std::ostream& operator
13. 2021.05.16 [C++] 이진 탐색 트리(Binary Search Tree)

    이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree) 널리 사용되는 형태의 이진 트리(Binary Tree) BST의 속성 왼쪽 노드 ≤ 부모 노드 ≤ 오른쪽 노드 의 관계를 가짐. 부모 노드의 값 ≥ 왼쪽 자식 노드의 값 부모 노드의 값 ≤ 오른쪽 자식 노드의 값 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 이고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 됨. 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어듦. BST가 마지막 레벨을 제외한 모든 노드에 2개의 자식 노드가 있을 경우 트리의 높이 : log₂N N : 원소의 개수 BST의 검색 및 삽입 동작의 시간 복잡도 : O(l..
14. 2021.05.15 [C++] 트리 순회(Tree Traversal)

    트리 순회(Traversal) 트리 순회 방법 트리 순회 방법은 다음과 같이 4가지가 있음. 전위 순회(Preorder Traversal) 중위 순회(In-Order Traversal) 후위 순회(Post-Order Traversal) 레벨 순서 순회(Level Order Traversal) 전위 순회(Preorder Traversal) 재귀적 인 방식으로 다음의 노드를 방문함. ① 현재 노드 (C) ② 현재 노드의 왼쪽 하위 노드 (L) ③ 현재 노드의 오른쪽 하위 노드 (R) 전위(Pre) 상위 노드를 하위 노드보다 먼저 방문한다는 뜻 전위 순회는 항상 부모 노드 를 방문한 다음, 왼쪽자식 노드, 오른쪽 자식 노드를 차례로 방문함. 이러한 방식의 순회를 루트 노드에서만 수행하는 것이 아니라, 루트 노..
15. 2020.11.11 피보나치 수열(Fibonacci Sequence)

    피보나치 수열(Fibonacci Sequence)의 점화식은 다음과 같다. $F_{n}:=\begin{cases} 0 \quad (\text{if} \quad n = 1) \\ 1 \quad (\text{if} \quad n = 2) \\ F_{n-1} + F_{n-2} \quad (\text{if} \quad n > 2) \end{cases}$ 이 점화식을 바탕으로 구한 피보나치 수열의 항과 값은 다음과 같다. 항 1 2 3 4 5 6 7 8 9101112131415161718... 값 0 1 1 2 3 5 8 13 213455891442333776109871597... 피보나치 수열은 재귀 함수 또는 반복문을 이용하여 구현할 수 있다. 1. 반복문을 이용하여 구현하기 123456789101112131..
16. 2020.08.13 탐욕 알고리즘(Greedy Algorithm)

    *탐욕 알고리즘 탐욕 알고리즘(Greedy Algorithm) - 결과값에 대하여 생각하지 않고 최선의 옵션을 선택하여 문제를 해결하는 알고리즘 - 즉, 지역적(locally)의 최선의 선택이 전역적(globally)의 최상의 결과값을 생성하도록 하는 것을 목표로 하는 알고리즘.- 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘 - 탐욕 알고리즘은 해답에 포함될 원소들을 차례로 선택하는 과정을 거치게 됨 - 각 단계에서는 전체적인 상황을 종합적으로 판단하고, 고려하여 결정하는 것이 아니라 현 시점의 정보 를 바탕으로 가장 이익이 되는 원소들을 선택함. - 동적 계획법(Dynamic Programming)과 마찬가지로 최적화 문제(Optimization Problem) 를 푸는데 사..
17. 2020.06.08 Union-Find 알고리즘(서로소 집합 알고리즘)

    *Union-Find 알고리즘 - Disjoint-Set(서로소 집합) 알고리즘이라고 불린다. - 지금 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 검사하는 알고리즘.- 간선의 양끝 정점이 서로 다른 집합에 속하는 경우, 두 정점을 연결하여도 사이클이 형성되지 않는다.- Kruskal MST 알고리즘을 구현하는데 사용된다. #include #define MAX_VERTICES 100 int parent[MAX_VERTICES]; // 부모 노드int num[MAX_VERTICES]; // 각 집합의 크기 // 초기화void set_init(int n) { int i; for (i = 0; i < n; i++) { parent[i] = -1; num[i] = 1; }} // vertex가..
18. 2017.08.29 최대공약수 (The Greatest Common Denominator(GCD)), 최소공배수(The Least(Lowest) Common Multiple(LCM))

    *최대공약수 (The Greatest Common Denominator(GCD)), 최소공배수(The Least(Lowest) Common Multiple(LCM)) # Algorithm 1 : 간단한 방법(Simple Way)을 이용한 최대공약수(GCD) 구하기 1 2 3 4 5 6 int min(int a, int b) { if (a > b) return b; else if (a =1; g--) if ((m % g == 0) && (n % g == 0)) return g; } Colored by Color Scripter cs # Algorithm 2 : 유클리드 호제법(Euclidean Algorithm)을 이용한 최대공약수(GCD) 구하기 1 2 3 4 5 6 7 8 9 10 11 12 13 14..
19. 2017.08.29 알고리즘이란?

    *알고리즘이란? - 알고리즘(algorithm) : 주어진 문제를 해결하는 절차(procedure) - 각 단계는 기본적인 연산(operation) 하나로 이루어져 있을 수도 있고, 혹은 다른 부분 문제(subproblem)에 대한 알고리즘일 수는 있찌만 충분히 구체적이어야 함. - 일반적으로 알고리즘은 다음의 두 조건을 반드시 만족해야 함. 종료(termination) : 모든 가능한 입력 사례에 대하여 반드시 끝난다. 정확성(correctness) : 모든 가능한 입력 사례에 대하여 옳은 답을 출력한다. - 가능한 입력에 대하여 항상 종료하고 옳은 답을 출력하면 알고리즘이 되지만, 실행시간이 빠르고 또한 메모리를 적게 쓰는 알고리즘을 선호하게 됨. - 다시 말하면 자원(resource)을 적게 쓰는 ..
20. 2017.06.21 [C] 탐색(Search)

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

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

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

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

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

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

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

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