독학두비니

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/백준 풀이

[Python] 1407번: 에디터 풀이

백준 풀이 1407번: 에디터 풀이 문제 Link: https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 설명 풀이 과정 제가 처음 접근했던 방식은 단순하게 string을 사용하여 관리를 하고, 별도로 index라는 변수를 사용하여 커서를 구현했었습니다. 리스트를 사용하려다가 string으로 관리하는 것이 더 빠르기 때문에 string으로 구현하였습니다. 코드는 다음과 같습니다. # github link: https://github.com/dub..

Coding_Algorithm/백준 풀이

[Python] 17215번: 볼링 점수 계산 풀이

백준 풀이 13783번: 합 구하기 풀이 볼링? 절 대 못 참 아 문제 Link: https://www.acmicpc.net/problem/17215 17215번: 볼링 점수 계산 첫째 줄에 각 기회마다 소현이가 쓰러뜨린 볼링핀의 개수가 공백없이 주어진다. 이때 스트라이크는 S, 스페어는 P, 핀을 하나도 못 쓰러뜨린 것은 -으로 주어진다. www.acmicpc.net 문제 설명 단순하게 볼링 점수 계산을 하는 프로그램을 만드는 것입니다. 저는 볼링을 쳐본적이 있어서 따로 점수 계산에 대한 이해가 필요 없었지만, 볼링 점수 체계에 대해서 잘 모르시는 분은 참고 부탁드립니다. 참고: https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=jabab..

Coding_Algorithm/백준 풀이

[Python] 11441번: 합 구하기 풀이

백준 풀이 13783번: 합 구하기 풀이 문제 Link : https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 단순한 합 구하기 문제인 것 같다. 그러나 특히 python같은 느린 언어로 정직하게 짤 경우, 시간초과가 발생하게 된다. import sys input = sys.stdin.readline N = int(input()) n_list = list(map(int, inp..