🗒️ Computer Science (60)

1. 2022.09.01 팰린드롬(Palindrome)

   팰린드롬(Palindrome) 팰린드롬(Palindrome) 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시하고, 앞으로 읽으나 거꾸로 읽으나 같은 문장 또는 낱말을 회문(回文) 또는 팰린드롬(Palindrome) 이라고 한다. 예) "소주 만 병만 주소", "여보 안경 안보여" 수학에서도 111, 12321과 같이 똑바로 읽으나 거꾸로 읽으나 같은 수를 팰린드롬 수(Palindrome Number) 또는 대칭수라고 한다. 숫자 뒤집기 숫자 k = 123, r = 0 으로 초기화되어 있다고 할 때, 다음의 순환문을 완료하면 k의 값은 0이 되고 r의 값은 k의 값이 거꾸로 뒤집어진 321이 된다. int k = 123; int r = 0; 숫자 뒤집기 알고리즘 while (k != 0) { p = k..
2. 2022.08.31 완전제곱수(Perfect Square Number, 제곱수, 정사각수)

   완전제곱수(Perfect Square Number, 제곱수, 정사각수) 정사각수(Square Number) 어떤 자연수의 제곱이 되는 `1^{2}, 2^{2}, 3^{2}, 4^{2}`과 같은 수를 완전제곱수(Perfect Square Number) 또는 제곱수(Square Number) 또는 정사각수라고 한다. 1 = 1² 1 + 3 = 2² 1 + 3 + 5 = 3² 1 + 3 + 5 + 7 = 4² 1 + 3 + 5 + 7 + 9 = 5² 위에서와 같이 1부터 연속된 홀수의 합은 언제나 완전제곱수임을 알 수 있다. 완전제곱수 판별하기 ① 약수의 개수를 이용한 완전제곱수 판별 완전제곱수는 약수의 개수가 언제나 홀수개이므로 약수의 개수를 확인하여 완전제곱수인지 판별할 수 있다. 예제 1부터 100까지의..
3. 2022.08.31 팩토리얼(Factorial)

   팩토리얼(Factorial) 팩토리얼(Factorial) 1부터 N까지 모두 곱한 수를 N 팩토리얼(Factorial)이라 부르며, 기호로는 N!로 나타낸다. N! = 1 x 2 x 3 x ... x N 곱셈 연산을 할 때의 초깃값은 언제나 1이어야 한다. 초깃값이 0일 경우, 어떤 수를 곱해도 항상 0이 된다. 예) 5! = 1 × 2 × 3 × 4 × 5 = 120 예제 5! 구하기 #include using namespace std; int main() { int fact; fact = 1; // 초깃값은 항상 1이어야 한다. for (int i = 1; i
4. 2022.08.31 완전수(Perfect Number), 부족수(Deficient Number), 과잉수(Abundant Number)

   완전수(Perfect Number), 부족수(Deficient Number), 과잉수(Abundant Number) 완전수(Perfect Number) 그 수 자신을 제외한 모든 약수의 합이 그 수 자신과 같은 수를 완전수(Perfect Number)라고 한다. 예) 6의 약수는 {1, 2, 3, 6} 이고, 그 수 자신을 제외한 1 + 2 + 3의 합은 6과 같으므로 6은 완전수이다. 부족수(Deficient Number) 그 수 자신을 제외한 모든 약수의 합이 그 수 자신보다 작은 수를 부족수(Deficient Number)라고 한다. 예) 8의 약수는 {1, 2, 4, 8} 이고, 그 수 자신을 제외한 1 + 2 + 4의 합은 7과 같으므로 8은 부족수이다. 과잉수(Abundant Number) 그..
5. 2022.08.31 가우스 계산법(Gaussian Calculation)

   가우스 계산법(Gaussian Calculation) 가우스(1777 ~ 1885, Carl Friedrich Gauss) 가우스(1777 ~ 1885, Carl Friedrich Gauss)의 선생님 뷔트너는 수업 시간에 잠시 쉴 생각으로 학생들에게 1부터 100까지 더하는 문제를 냈다. 가우스는 순식간에 5050 이라는 정답을 알아내었다. 가우스의 천재성을 알아본 뷔트너는 그에게 고등학교 수학 교과서를 선물했다고 한다. 독일의 수학자 가우스는 아르키메데스, 뉴턴과 함께 수학의 역사살 가장 위대한 세 명의 수학자 중 한 명이다. 가우스 계산법 연속된 수 또는 규칙적으로 나열되어 있는 수열 등의 합을 쉽게 계산하기 위해서 사용하는 계산법 일반화하면 다음과 같다. 처음 값부터 마지막 값까지의 합 = (처음..
6. 2022.06.29 [Python] 동적 계획법(DP: Dynamic Programming)

   동적 계획법(DP: Dynamic Programming) 동적 계획법(DP: Dynamic Programming) 불필요한 연산을 줄이고, 최적의 답안을 구하는 알고리즘 동적 계획법의 등장 배경 ① 배낭 문제(Knapsack Problem) 무게와 가격이 다른 여러 물건 중에서, 가장 효율적으로 배낭에 채우기 위한 문제 예) 배낭에 넣을 수 있는 무게는 한정 되어 있고, 배낭에 넣을 수 있는 보석의 무게와 가치가 각각 다를 때 어떻게 해야 가방에 가장 큰 이익이 담길 수 있도록 보석을 채울 수 있을까? ② 브루트 포스 검색(Brute Force Search) 모든 경우의 수를 나열한 후, 그중에서 최선의 해결책을 찾는 방법 '짐승(Brute)처럼 무식한 힘(Force)으로 전체 경우의 수를 검색한다.'는..
7. 2022.06.29 [Python] 탐색(Search)

   탐색(Search) 탐색의 기본 개념 탐색(Search) : 어떤 집합에서 원하는 것을 찾는 것으로 검색이라고 한다. 탐색의 종류 순차 탐색(Sequential Search) 이진 탐색(Binary Search) 트리 탐색(Tree Search) 검색 결과로 특정 집합의 위치인 인덱스를 알려 준다. 검색에 실패하면(찾는 데이터가 집합에 없다면) -1을 반환하는 것이 일반적이다. 탐색 알고리즘의 종류 탐색은 데이터 상태에 따라 다양한 알고리즘을 사용할 수 있다. 탐색할 집합이 정렬되어 있지 않은 상태라면 순차 탐색을 해야 한다. 순차 탐색(Sequential Search) 순차 탐색은 처음부터 끝까지 차례대로 찾아보는 것으로, 쉽지만 비효율적인 탐색 방법이다. 하지만, 집합의 데이터가 정렬되어 있지 않다면..
8. 2022.06.28 [Python] 정렬(Sort) : 선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬

   정렬(Sort) 정렬의 기본 정렬의 개념 정렬(Sort) : 자료들을 일정한 순서대로 나열하는 것 순서대로 나열할 때는 작은 것부터 나열하는 방법(오름차순)과 큰 것부터 나열하는 방법(내림차순)이 있다. 오름차순 정렬(Ascending Sort) : 작은 것부터 큰 순으로 나열된 방법 내림차순 정렬(Descending Sort) : 큰 것부터 작은 순으로 나열된 방법 정렬의 대표적인 예 : 사전 정렬 알고리즘의 종류 오름차순 정렬이든 내림차순 정렬이든 결과의 형태만 다를 뿐, 같은 방식으로 처리된다. 정렬하는 방법에 대한 알고리즘은 수십 가지이다. 이해하고 구현하기 쉽지만 속도가 느린 알고리즘 이해와 구현이 어렵지만 속도가 빠른 알고리즘 특수한 상황에서만 효율적인 알고리즘 메모리를 적게 사용하는 알고리즘..
9. 2022.06.05 [Python] 재귀 호출(Recursion)

   재귀 호출(Recursion) 재귀 호출의 기본 재귀 호출의 개념 재귀 호출(Recursion) : 자기 자신을 다시 호출하는 것 재귀 호출은 처음 접하면 상당히 혼란스럽지만 자료구조와 알고리즘을 학습할 때 매우 유용한 방법이므로 꼭 알아두어야 한다. 재귀호출의 동작 파이썬에서는 재귀 호출이 너무 많아지면 반복을 자동 종료한다. def openBox() : print("종이 상자를 엽니다.") openBox() openBox() # 처음 함수를 다시 호출 더보기 종이 상자를 엽니다. 종이 상자를 엽니다. ... RecursionError: maximum recursion depth exceeded while pickling an object 반환 조건을 추가할 경우, 무한 반복에서 빠져나올 수 있다. d..
10. 2022.06.04 [Python] 그래프(Graph)

    그래프(Graph) 그래프(Graph)의 기본 그래프의 개념 그래프(Graph) : 여러 노드가 서로 연결된 자료구조 루트에서 하위 노드 방향으로만 이어지는 트리와 달리, 여러 노드가 연결되어 있을 수 있다. 트리도 그래프의 일종이지만, 트리와 그래프를 구현하는 코드 등이 확연히 다르기 때문에 이 둘은 별도로 생각하는 편이 낫다. 그래프의 종류 그래프는 정점을 연결하는 간선의 방향성 여부에 따라 방향 그래프와 무방향 그래프로 나눈다. 간선에 가중치(Weight)를 부여하여 가중치 그래프도 만들 수 있다. 무방향 그래프 트리의 노드(Node)에 해당하는 용어가 그래프에서는 정점(Vertex)이다. 정점을 연결하는 선은 간선(Edge)이므로 그래프는 정점과 간선의 집합으로 볼 수 있다. 그래프에서 정점은 V..
11. 2022.06.04 [Python] 이진 트리(Binary Tree)

    이진 트리(Binary Tree) 이진 트리(Binary Tree)의 기본 이진 트리의 개념 트리(Tree) 자료구조는 나무를 거꾸로 뒤집어 놓은 형태이다. 트리의 맨 위를 뿌리(Root, 루트)라고 한다. 루트를 레벨 0으로 두고 나뭇잎(Leaf, 리프)에 해당하는 아래로 내려올 수록 레벨이 1씩 증가한다. 트리에서 각 위치를 노드(Node)라고 한다. 각 노드는 선, 즉 에지(Edge)로 연결되어 있다. 위 노드와 바로 아래 노드의 관계를 부모-자식 관계(Parent-Child Relationship)라고 한다. 자식 노드의 개수를 차수(Degree)라고 한다. 차수가 0인 노드를 리프(Leaf)라고 한다. 트리의 차수는 차수가 가장 높은 노드를 기준으로 정한다. 컴퓨터는 데이터를 0과 1로 표현하므..
12. 2022.06.03 [Python] 큐(Queue)

    큐(Queue) 큐(Queue) 선입선출(First In First Out, FIFO)의 특징을 갖는 자료구조 큐는 양쪽이 뚫려 있는 구조이다. 한쪽에서는 삽입만 진행되고, 다른 쪽에서는 추출만 진행된다. 큐에 데이터를 삽입하는 동작을 enQueue(인큐)라고 하며, 데이터를 추출하는 동작을 deQueue(데큐)라고 한다. 큐의 중요한 용어로 front(머리)와 rear(꼬리)가 있다. 머리는 저장된 데이터 중 첫 번째 데이터를 가리킨다. 꼬리는 저장된 데이터 중 마지막 데이터를 가리킨다. 첫 번째 데이터 앞을 front가 가리켜야 한다. 데이터 삽입 : enQueue 데이터 추출 : deQueue 큐의 간단 구현 큐는 배열 형태로 구현할 수 있다. 큐는 초기에 크기를 지정하고 배열로 생성할 수 있다. ..
13. 2022.05.30 [Python] 스택(Stack)

    스택(Stack) 스택(Stack) 선입후출(First In Last Out, FILO) 또는 후입선출(Last In First Out, LIFO)의 특징을 갖는 자료구조 스택은 한쪽만 뚫려 있는 구조이기 때문에 삽입과 추출이 한쪽에서만 진행된다. 스택에 데이터를 삽입하는 동작을 push(푸시)라고 하며, 데이터를 추출하는 동작을 pop(팝)이라고 한다. 스택에서는 top(톱)이라는 용어가 중요한데, 현재 스택에 들어 있는 가장 위의 데이터 위치를 가리키는 개념이다. 스택의 간단 구현 스택은 배열 형태로 구현할 수 있다. 스택은 초기에 크기를 지정하고 배열로 생성할 수 있다. 스택의 맨 위쪽을 표현하는 top은 아직 데이터가 없으므로 -1로 초기화한다. top이 -1이라는 것은 스택이 비었다는 의미로 해..
14. 2022.04.21 [Python] 원형 연결 리스트(Circular Linked List)

    원형 연결 리스트(Circular Linked List) 원형 연결 리스트의 개념 단순 연결 리스트(Singly Linked List) 끝까지 방문한 후에는 더 이상 방문할 곳이 없어 종료되므로 다시 방문하려면 헤드(head)부터 재시작해야 한다. 원형 연결 리스트(Circular Linked List)는 단순 연결 리스트의 마지막 노드가 다시 첫 번째 노드를 가리키도록 설정되어 리스트 형태가 원(Circle) 형태로 구성된다. 시작 위치와 다음 위치가 계속 이어진 후, 마지막에 다시 시작 위치로 돌아오는 형태 원형 연결리스트는 단순 연결 리스트와 마찬가지로 데이터 삽입에서 오버헤드가 발생하지 않는다. 원형 연결 리스트의 원리 원형 연결 리스트의 원리 및 구조도 단순 연결 리스트와 많은 부분이 비슷하다...
15. 2022.04.21 [Python] 단순 연결 리스트(Singly Linked List)

    단순 연결 리스트(Singly Linked List) 단순 연결 리스트의 개념 선형 리스트(Linear List) 장점 배열에 구성하였기 때문에 단순하다. 물리적인 순서와 논리적인 순서가 동일하여 데이터를 찾기 간단하다. 프로그램으로 구현하기 비교적 쉽다. 단점 : 데이터를 삽입하거나 삭제할 때 많은 작업이 필요하다. 예) 100만 개인 선형 리스트의 맨 앞에 데이터를 하나 삽입하려면 약 100만 개를 뒤로 이동시키는 작업을 해야 한다. (오버헤드(Overhead) 발생) 단순 연결 리스트(Singly Linked List) 선형 리스트(Linear List)와 달리, 저장된 노드들이 물리적으로 떨어진 곳에 위치한다. 각 노드의 번지도 100, 200, 130 등으로 순차적이지 않다. 데이터와 링크로 구..
16. 2022.04.21 [Python] 선형 리스트(Linear List)

    선형 리스트(Linear List) 선형 리스트의 기본 개념 데이터를 일정한 순서로 나열한 구조 순차 리스트(Ordered List)라고도 한다. 입력 순서대로 저장하는 데이터에 해당한다. 선형 리스트는 다양한 방법으로 구현할 수 있지만, 가장 기본적인 방법은 배열 을 이용하는 것이다. 선형 리스트는 메모리에서도 차례로 저장된다. 원리 데이터 삽입 1단계 : 맨 끝에 빈칸을 확보한다. 2단계 : 삽입하고자 하는 공간에 빈칸이 없으므로, 삽입하고자 하는 공간 뒤에 있는 요소들을 한칸씩 뒤로 옮긴다. 3단계 : 빈자리에 요소를 삽입한다. 데이터 삭제 원하는 요소가 삭제된 후 빈칸을 그대로 두지 않고 뒤의 요소들을 앞으로 한칸씩 이동시킨다. 선형 리스트의 구현 사용자가 입력하는 데이터가 가변적으로 작동하는 범..
17. 2021.07.22 부분집합의 합 문제(Subset Sum Problem)

    부분집합의 합 문제(Subset Sum Problem) 부분집합의 합 문제를 한 문장으로 표현하면 다음과 같음. 음수가 아닌 정수로 이루어진 집합 S와 임의의 정수 x가 주어질 때, S의 부분집합 중에서 그 원소의 합이 x와 같은 부분집합이 존재하는가? 부분집합의 합 문제의 예 S = { 13, 79, 45, 29 } x = 42 → True (13 + 29) x = 25 → False 집합 S가 S = { 13, 79, 45, 29 } 형태로 주어질 경우, S로부터 다음과 같은 16개의 부분집합을 추출할 수 있음. { } { 13 } { 79 } { 45 } { 29 } { 13, 79 } { 13, 45 } { 13, 29 } { 79, 45 } { 79, 29 } { 45, 29 } { 13, 79..
18. 2021.07.22 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

    플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 모든 쌍 최단 경로(All-Pairs Shortest Path)를 구하는 알고리즘 O(V³)의 시간 복잡도와 O(V²)의 메모리 사용량으로 동작하는 상향식 알고리즘 벨만-포드 알고리즘 그래프의 두 정점 사이의 최단 경로가 출발 정점에서 시작하는 다른 최단 경로와 최종 목표 정점으로 연결된 에지의 조합으로 구성됨. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 은 이러한 개념에 좀 더 광범위한 일반화를 적용함으로써 큰 효과를 얻음. 정점 A와 정점 B 사이의 최단 거리가 AB이고, 정점 B와 정점 C 사이의 최단 거리가 BC이면, 정점 A와 정점 C 사이의 최단 거리는 AB + BC 임. 이 논리는 그 자체로 획기..
19. 2021.07.04 코사라주 알고리즘(Kosaraju's Algorithm)

    코사라주 알고리즘(Kosaraju's Algorithm) 그래프에서 강한 연결 요소를 찾는 가장 쉽고 널리 사용되는 방법 DFS를 2번 수행하는 형태로 동작함. ① 입력 그래프 자체에 DFS를 수행함. ② 입력 그래프를 전치하여 DFS를 수행함. 코사라주 알고리즘은 일반적으로 DFS 방식 의 순회를 사용하지만, BFS 도 사용할 수 있음. DFS 방식이 전통적인 방식 복잡할 수 있는 문제를 직관적으로 단순화하는 측면에서 매우 효과적이며, 구현하기도 쉬운 편임. 입력 그래프가 인접 리스트 로 표현되어 있을 경우, O(V + E) 형태의 선형 점근적 시간 복잡도 를 갖기 떄문에 매우 효율적임. 코사라주 알고리즘에서 인접 행렬 을 사용하는 것은 권장되지 않음. 그래프 순회에서 각 정점의 이웃을 찾기 위해 상당..
20. 2021.07.04 존슨 알고리즘(Johnson's Algorithm)

    존슨 알고리즘(Johnson's Algorithm) 벨만-포드 알고리즘 과 다익스트라 알고리즘 의 방법을 결합하여 모든 정점 사이의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘의 효율성을 활용함과 동시에 음수 가중치를 갖는 그래프에 대해서도 올바른 결과를 생성할 수 있음. 상당히 새로운 접근 방법을 사용함. 음수 가중치에 대한 다익스트라 알고리즘의 한계를 극복하기 위해 전체 에지 가중치를 음수가 아닌 형태로 변환 함. 벨만-포드 알고리즘 과 적절한 수학 논리 를 결합하여 이루어짐. 동작 방식 그래프에 새로운 더미(Dummy) 정점 을 추가함. 그리고 이 더미 정점과 나머지 모든 정점 사이에 가중치가 0인 에지를 연결함. 이후 벨만-포드 알고리즘 을 이용하여 더미 정점과 나머지 정점들 사이의 최단 경로..
21. 2021.07.02 벨만-포드 알고리즘(Bellman-Ford Algorithm)

    벨만-포드 알고리즘(Bellman-Ford Algorithm) 음수 가중치가 있는 그래프를 다룰 때 사용하는 알고리즘 그래프의 모든 에지에 대해 다익스트라의 그리디 선택 방법을 (V - 1)번 반복하여 점진적으로 최단 거리를 찾음. V : 정점의 개수 다익스트라 알고리즘보다 높은 점근적 시간 복잡도를 가짐. 다익스트라 알고리즘이 잘못 해석할 수 있는 그래프에 대해서도 정확한 결과를 제공함. 코드 1 음수 가중치 사이클 이 없을 경우 #include #include #include using namespace std; struct Edge { int src; int dst; int weight; }; const int UNKNOWN = INT_MAX; vector BellmanFord(vector edge..
22. 2021.06.30 다익스트라 최단 경로 알고리즘(Dijkstra Shortest Path Algorithm)

    다익스트라 최단 경로 알고리즘(Dijkstra Shortest Path Algorithm) 그래프에서 단일 시작(Single Start) 최단 경로 문제(Shortest Path Problem) 구글 지도 또는 자동차 내비게이션 등에서 경로를 탐색할 때 사용됨. 문제 정의 주어진 그래프 G = 의 시작 정점(Source Vertex) 과 목적 정점(Destination Vertex) 이 주어질 때, 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 구하시오. V : 정점의 집합 E : 에지의 집합 각각의 에지는 가중치를 가지고 있음. 다익스트라 알고리즘(Dijkstra's Algorithm) 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘 프림의 MST 알고리즘을 약간 변경한 형태 ..
23. 2021.06.30 프림의 최소 신장 트리 알고리즘(Prim's Minimum Spanning Tree Algorithm)

    프림의 최소 신장 트리 알고리즘(Prim's Minimum Spanning Tree Algorithm) MST 문제 정점 집합 V의 가중치를 갖는 에지 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하는 문제 크루스칼 알고리즘(Kruskal Algorithm) 그래프의 모든 에지를 최소 힙 에 추가하고, 사이클을 만들지 않는 최소 가중치의 에지를 이용하여 MST를 구성함. 프림 알고리즘(Prim's Algorithm) BFS의 동작 방식과 유사함. 먼저 시작 정점을 이용하여 경계를 구성함. 경계는 이전에 방문했던 정점들에 의해 구성됨. 현재 경계에 인접한 정점을 반복적으로 탐색함. 이때 프림 알고리즘은 경계를 관통하는 에지 중에서 가장..
24. 2021.06.30 깊이 우선 탐색(DFS, Depth-First Search)

    깊이 우선 탐색(DFS, Depth-First Search) 너비 우선 탐색(BFS, Breadth-First Search) 시작 장점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식 방문하지 않은 정점을 저장하기 위해 큐(Queue) 를 사용함. 선입선출(FIFO) 자료구조 큐에 있는 정점들은 큐에 들어갔던 순서대로 제거됨. 이러한 큐의 속성을 이용하여 시작 정점에 가까이 있는 정점들을 먼저 처리할 수 있음. 시간 복잡도 : O(V + E) 깊이 우선 탐색(DFS, Depth-First Search) 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식 더 방문할 정점이 없어지면, 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복함. 이러한 그래프 탐색 방..
25. 2021.06.30 너비 우선 탐색(BFS, Breadth-First Search)

    너비 우선 탐색(BFS, Breadth-First Search) 시작 정점을 경계(Frontier)에 추가하는 것으로 시작함. 경계는 이전에 방문했던 정점들 에 의해 구성됨. 현재 경계에 인접한 정점을 반복적으로 탐색함. 시간 복잡도 : O(V + E) V : 정점의 개수 E : 에지의 개수 모든 정점에 대해 자식 정점을 손자 정점보다 먼저 방문한다 는 점이 중요한 특징 BFS를 구현할 경우, 보통 경계를 별도의 자료구조로 만들어서 명시적으로 사용하지는 않음. 대신 정점 ID를 큐(Queue) 에 저장하여 시작 정점과 가까운 정점을 멀리 있는 정점보다 먼저 방문할 수 있도록 구현함. 동작 과정 ① 먼저 시작점인 우리집 정점을 방문함. 빨간색 점선 : 현재 경계 인접한 정점으로 R1과 R2가 있음. ② R..
26. 2021.06.28 그래프 순회 문제(Graph Traversal Problem) ; 그래프 탐색 문제(Graph Search Problem)

    그래프 순회 문제(Graph Traversal Problem) ; 그래프 탐색 문제(Graph Search Problem) 그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제 그래프 순회 문제를 수학적으로 표현할 경우 그래프 G = 가 주어질 떄, 특정 정점 s로부터 시작하여 모든 정점 v ∈ V를 방문하는 문제라고 할 수 있음. 그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도 로 사용될 수 있기 떄문에 그래프 탐색 문제(Graph Search Problem) 라고도 부름. 여러 그래프 탐색 알고리즘이 존재하고, 각각은 서로 다른 순서로 모든 정점을 방문함. 종류 너비 우선 탐색(BFS, Breadth-First Search) 깊이 우선 탐색(DFS, Depth-First Sea..
27. 2021.06.27 웰시-포웰 알고리즘(Welsh-Powell Algorithm)

    웰시-포웰 알고리즘(Welsh-Powell Algorithm) 차수(Degree) 가 높은 정점부터 차례대로 그래프 컬러링을 수행하는 방법 다음의 순서를 따름. ① 단계 모든 정점을 차수에 대한 내림차순으로 정렬하고 배열에 저장함. ② 단계 정렬된 배열에서 색상이 지정되지 않은 첫 번째 정점을 선택하고, 이 정점과 연결된 모든 정점을 조사하여 아직 사용되지 않은 색상을 해당 정점에 지정함. 이 색상을 C라고 지칭하겠음. ③ 단계 정렬된 배열에서 색상이 지정되지 않은 정점을 모두 찾고, 만약 이 정점의 이웃이 C 색상을 가지고 있지 않다며 해당 정점에 C 색상을 지정함. ④ 단계 배열에 색상이 지정되지 않은 정점이 남아 있다면 ②단계로 이동함. 남아 있는 정점이 없다면 종료함. 이때까지 정점에 지정된 색상..
28. 2021.06.26 [C++] 디스조인트-셋(Disjoint-Set) ; 유니언-파인드(Union-Find), 서로소 집합, 상호 배타적 집합

    디스조인트-셋(Disjoint-Set) 디스조인트-셋(Disjoint-Set) 또는 유니언-파인드(Union-Find) 자료구조 다음과 같이 불림. 서로소 집합 자료구조 상호 배타적 집합 자료구조 트리 형태로 구성된 포레스트(Forest) 각각의 원소는 숫자 ID 에 의해 표현됨. 랭크(Rank) 와 부모에 의한 포인터를 가짐. 초기화되면 랭크가 0인 N개의 독립적인 원소가 생성됨. 각각의 원소는 하나의 트리를 나타냄. 공통의 원소를 갖지 않는 원소 집합을 표현하기 위해 사용됨. 지원 연산 make-set(x) x를 ID로 갖는 원소를 디스조인트-셋 자료구조에 추가함. 새로 추가한 원소의 랭크 : 0 원소의 부모 포인터는 자기 자신을 가리키도록 설정함. 그림 설명 원 안에 적힌 숫자 : 원소 ID 괄호 ..
29. 2021.06.26 크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm)

    크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm) 최소 신장 트리(Minimum Spanning Tree) 정점(Vertex) 의 집합 V와 가중치를 갖는 에지(Edge) 의 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소 인 트리 T 크루스칼 최소 신장 트리 알고리즘(Kruskal Minimum Spanning Tree Algorithm) 1956년에 발표됨. 알고리즘 ① 그래프 G의 모든 에지를 최소 힙 H에 추가함. ② H로부터 에지 e를 하나 꺼냄. e : 모든 에지 중에서 가장 가중치가 작은 에지 ③ e이 양 끝 정점이 이미 T에 있을 경우, e로 인해 T에서 사이클이 발생할 수 있음...
30. 2021.06.25 분할 가능 배낭 문제(Fractional Knapsack Problem)

    분할 가능 배낭 문제(Fractional Knapsack Problem) 0-1 배낭 문제 에서 다음 조건 추가 주어진 물건(O)을 원하는 형태로 얼마든지 분할 할 수 있음. 각 물건의 일부분만을 배낭에 담을 수 있음. 실생활의 예) 상인이 기름, 곡물, 밀가루와 같은 품목을 다룰 경우 각 품목을 원하는 양만큼 덜어내서 배낭에 담을 수 있음. 일반 배낭 문제가 NP-완전 문제 인 것과 달리 분할 가능 문제 는 간단한 솔루션이 존재함. 각 물건을 단위 무게(W)당 가격(V)을 기준으로 정렬함. 그리디 방식 에 따라 단위 무게당 가격이 높은 순서 로 물건을 선택함. 분할 가능 배낭 문제의 예 배낭 용량(T)이 8인 경우에 선택할 수 있는 최선의 물건 조합 코드 #include #include #include..