독학두비니

Coding_Algorithm/DS_Algorithm

Adjacency Matrix and Adjacency Lists

00. Introduction 알고리즘을 공부하다 보면, Graph를 대상으로 하는 알고리즘들이 있다. 이를 효율적으로 표현하기 위해서 보통 Adjacency Matrix와 Adjacency Lists를 사용하는데, 본 글에서는 어떤 식으로 각 representation을 만드며, 어떻게 사용되는지에 대해서 알아보도록 한다. 아 Graph는 undirected graph와 directed graph가 있으며, 다음과 같다. 말 그대로라 설명은 생략. 아 Graph는 수식적으로 다음과 같이 표기한다. G = (V, E) - V: Vertex(정점)의 집합 - E: Edge(간선)의 집합 01. Basic Notion 개념 자체는 말 그대로이다. 그래프는 말그대로 "그래프" 형식이기 때문에 컴퓨터가 처리하기..

Coding_Algorithm/DS_Algorithm

Hash Table/Algorithm and Collision Resolution

00. Hash Table이란? Hash Table이란, Dictionary 구조를 구현하는 효율적인 자료 구조 중 하나이다. cf. Dictionary: INSERT, SEARCH, 그리고 DELETE 기능이 있는 집합 참고로 Hash Table을 사용하였을 때 SEARCH하는데 걸리는 Time Complexity는 다음과 같다. worst case: Θ(n^2) expected time: O(1) Hash Table에는 여러 가지 종류가 존재한다. 이에 대해서 알아보도록 하자. 01. Direct Address Table 가장 단순한 형태의 Hash Table이다. Key값이 그대로 테이블의 인덱스 값이 되며, 따로 처리할 내용이 없기 때문에 Time Complexity도 항상 O(1)이다. 각 op..

Coding_Algorithm/DS_Algorithm

Quick Sort

Quick Sort 0. 개요 Quick Sort는 특이하게도 Worst case로 따지자면 Merge Sort, Heap Sort보다 안좋은 성능을 보인다. 그러나 Runtime의 기댓값이 낮기 때문에 많이 사용하는 알고리즘이다. 후에도 언급하겠지만 이 핵심은 partition을 어떻게 정하느냐에 있고, 추후 글에는 randomized quick sort에 대해서도 다룰 것이다. 1. Pseudocode Quicksort는 partition을 정한 뒤, 참고: https://www.youtube.com/watch?v=COk73cpQbFQ 2. Randomized Quick Sort 2.1 Randomized Quick Sort Time Complexity O(nlgn)

Coding_Algorithm/DS_Algorithm

Heap Sort

Heap Sort 0. 개요 앞서 다뤘던 내용들은 자료구조를 사용하지 않는 알고리즘이었다. (Insertion Sort, Merge Sort 등) 그러나 자료구조를 사용할 경우 더 효율적으로 문제를 풀 수 있는 경우가 생기며, 대표적으로 Max heap를 사용하는 Heap Sort가 있다. 1. 자료구조 heap 자료구조 heap, 특히 max heap에 대해서 알아봅시다. Max Heap이 되기 위해서는 다음 조건을 만족해야한다. 1) a complete binary tree여야함 - tree 구조에서 마지막 level을 빼고는 모두 차 있어야 함 - 마지막 level은 왼쪽부터 오른쪽으로 차있음 2) Max-heap Property를 가지고 있어야 함 - key(x) >= keys(at x's chi..

Coding_Algorithm/DS_Algorithm

Probabilistic Analysis

Probabilistic Analysis 0. 개요 기존에는 알고리즘의 시간분석도를 계산할 때 알고리즘에서 실행되는 명령어의 수를 계산하는 방식으로 진행했다. 특히 worst case로 진행해 그러나 많은 알고리즘은 주어지는 입력에 따라 성능이 달라지는 경우가 많다. 이렇게 입력이 확률적으로 주어지는 상황에서, 입력에 대한 worst case로 성능을 보는 것이 아닌, 평균적인 성능으로 알고리즘의 성능을 분석하는 방법을 알고리즘의 확률적 분석이라고 한다. 다만 확률적 분석은 입력의 분포를 알고 있다는 가정 하에 진행된다. 입력의 분포를 모른다면 확률적 분포를 진행할 수 없다. 1. Hiring Problem Hiring Problem은 사람을 채용할 때의 문제를 칭한다. 각각 사람을 면접볼 때 비용이 들..

Coding_Algorithm/DS_Algorithm

Growth of Function

0. Asymptotic Notations 알고리즘을 만들다 보면 알고리즘을 평가해야 할 때가 많습니다. 너무나 당연한 이야기지만 슈퍼컴에서 돌릴 때와 내 작고 귀여운 5년된 노트북에서 돌릴 때 성능 차이는 당연히 날 것입니다.(아주많이..ㅠ) 따라서 알고리즘의 성능을 평가할 때는 컴퓨터의 성능과는 관계가 없는 방법으로 평가를 하게 됩니다. 이를 Asymptotic Notation(점근표기법)이라고 합니다. 한국어 이름 '점근'에서 볼 수 있듯이, Asymptotic Notation에서는 'n을 무한대로 보냈을 때 소요되는 시간이 얼마나 걸리는가'를 기준으로 봅니다. 예를 들어 어떠한 알고리즘의 시간소요량이 f(n)=5n^2+8n+10이라고 합시다. 이 경우 n을 무한대로 보내면, 5n^2의 값이 8n에..

Coding_Algorithm/DS_Algorithm

Divide and Conquer 관점에서 본 Merge Sort

Divide and Conquer 관점에서 본 Merge Sort 0. 개요 지난 글에 이어서 오늘은 Divide and Conquer approach에 대해서 알아보고, 나아가 Merge Sort에 대해서 알아보도록 하겠습니다. 1. Divide and Conquer 먼저 Divide and Conquer에 대해서 알아봅시다. 말 그대로 Divide(분할)한 뒤 Conquer(정복)하는 개념입니다. 가장 중요한 것은 Divide - Conquer - Combine의 순서로 진행된다는 점입니다. 이전 글이었던 Incremental approach와의 차이점에 대해서 이야기하자면, Incremental approach는 작게 문제를 나누어서 해결한 작은 문제를 기반으로 더 큰 문제를 풀어나간다면, 문제를 ..

Coding_Algorithm/DS_Algorithm

Incremental approach로 본 Insert sort algorithm

Incremental approach로 본 Insert Sort Algorithm 0. 개요 알고리즘을 구상할 때 여러 가지 접근 방법이 있겠지만, 크게 두 가지 approach에 대해서 다룰 예정이다. 첫 번째는 Incremental Approch이고, 대표적인 예시인 Insert Sort Algorithm에 대해서 알아볼 것이다. 1. Incremental Approach(증가적 도달) Incremental Approach란 위에서도 이야기했듯, 문제를 푸는 하나의 시각이다. 자세히 알아보자. GPT는 쪼개서 풀어내는 방법을 'Subproblems'라고 했는데, 추후 한 번 더 이야기하겠지만 작은 부분 문제를 순차적으로 해결하면서 전체적인 문제 해결을 추구하는 방법이다. 이는 작은 부분 문제를 독립적..

Coding_Algorithm/DS_Algorithm

알고리즘 & Halting Problem

알고리즘 & Halting Problem 0. 알고리즘이란? 다음은 위키백과에 수록되어있는 알고리즘의 정의이다. 알고리즘, 셈법은 수학과 컴퓨터과학, 전산언어학 등에서 사용되는, 문제 해결 방법을 정의한 일련의 단계적 절차이다. 알고리즘에 대해서 보기 전에, 한 가지 짚고 넘어가야 하는 점이 있다. 여기서 '문제'란 무엇일까? 특히 알고리즘에서 문제(Problem)을 논할 때는, Computational Problem을 논한다. 알고리즘에서의 Computational Problem이란 input과 output으로 구성됩니다. 그리고 이 input과 output 사이의 관계를 나타내는 것을 문제의 정의(definition)이라고 한다. 알고리즘의 문제에 대한 대표적인 예시는 정렬 문제(Sorting Pro..

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-12번(멱급수) 풀이

12번 문제 S가 n개의 원소로 된 집합일 때 S의 멱집합(powerset)은 모든 가능한 S의 부분 집합이다. 즉, S = {a, b, c}이면 powerset(S) = { {}, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c} } 이다. powerset(S)를 계산하는 순환 함수를 계산하여라. 문제가 약간 1장 3번같은 느낌이네요. 이 풀이도 참고하면 좋을 것 같습니다. https://dokhakdubini.tistory.com/186 [C로 쓴 자료구조론] 1장 연습문제-3번(Boolean출력) 풀이 1장 연습문제-3번(Boolean출력) 풀이입니다. 3. n개의 Boolean 변수 x1, x2, x3, ... ,xn이 주어졌을 때, 이 변수들이 가질 수 있는..

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-11번(하노이의 탑) 풀이

11번 문제 세 탑이 있는데, 첫 번째 탑에는 반경이 서로 다른 64개의 원 판들이 쌓여 있다. 이때 각 원판은 반경이 큰 순서로 아래부터 쌓여있다. 이제, 다음 규칙에 따라 수도승들이 첫 번째 탑에서 세 번째 탑으로 원판을 옮기려 한다. (a) 한 번에 1개의 원판만을 다른 탑으로 옮길 수 있다. (b) 쌓아놓은 원판은 항상 위의 것이 아래 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 순환 함수를 만들어라. 그냥 재귀함수로 구현할게요~ https://dokhakdubini.tistory.com/190?category=814319 [재귀함수] 재귀함수 구현할 때 염두에 두면 좋은 것들 작년에 c언어를 처음 배울 때도 재귀함수에 대해서 배웠는데 너무 어려워서 그냥 무시한 적이 있..

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-10번(Ackermann 함수) 풀이

10번 문제 Ackermann 함수 A(m, n)은 다음과 같이 정의된다. 이 함수는 m, n의 값이 아주 작은 값에서도 급속히 증가하는 성질이 있다. 이 함수를 계산하는 순환함수와 반복 함수를 작성하여라. 뭐하는 함수인지 궁금해서 좀 찾아보았습니다. 그냥 재귀함수에서 대표적으로 쓰이는 함수인 것 같네요. 혹시나 궁금한 분들은 위키피디아ㄱㄱ https://ko.wikipedia.org/wiki/%EC%95%84%EC%BB%A4%EB%A7%8C_%ED%95%A8%EC%88%98 아커만 함수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 계산 가능성 이론에서, 빌헬름 아커만의 이름을 딴 아커만 함수(Ackermann函數, 영어: Ackermann function)는 원시 재귀 함수가 ..