Greedy algorithm, 탐욕법
Greedy - 탐욕스러운, 욕심 많은 그리디 알고리즘은 이름 그대로 선택의 순간이 될때마다 당장 눈앞의 최적의 상황만을 선택하여 최종적인 답에 도달하는 방법이다. 최적의 상황이란? 최적의 상황의 예시를 들어보자 루트노드에서 가장 깊은 레벨의 노드까지의 최대합을 구하는 경로를 구해본다고 생각해보자. 여기서 탐욕스러운 방법을 이용한다면 1부터 시작해서 12보다 큰 23을 선택한다 그리고 36 37 중 더 큰 37을 선택하여 잘못된 값을 선택하게 될것이다. 그래서 실제로 그리디 알고리즘을 활용할 경우는 이러하게 간단히 선택할 수 없다. 그리디 알고리즘으로 문제를 해결하는 방법은 다음과 같다. 선택 : 현재 상태에서 최적의 해답을 고른다. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답 ..
캐시 메모리, Cache Memory 캐시 메모리는 CPU와 주 기억장치(Memory, ram)의 속도차이를 극복하기 위하여 CPU ↔ 주기억장치 사이에 존재하는 고속의 버퍼 메모리이다. 캐시 메모리를 사용하여 CPU가 작업을 빠르게 처리할 수 있다. CPU는 캐시 메모리에 접근하여 연산에 필요한 명령과 데이터를 읽어 들인다. 만약, CPU가 캐시 메모리에 접근할 때 원하는 데이터가 없다면 캐시 메모리는 주기억장치에 접근하여 데이터를 캐시 메모리에 올려야 된다. -> CPU가 원하는 데이터가 캐시 메모리에 있을 수 있도록 하는 것을 의미한다. 캐시의 작동 원리 원본 데이터와 별개로 자주 쓰이는 데이터들을 복사해둘 캐시 메모리를 만든다. 데이터 요청이 들어올 경우 캐시 메모리 먼저 탐색한다. 캐시에 원하는..
[알고리즘] Dijkstra, 다익스트라 알고리즘
최단경로 구하기 하나의 정점을 기준으로 다른 정점까지의 최단거리를 측정하는 알고리즘이다. 특정 지역에서 다른 지역까지의 최단 경로를 구하는 지도를 사용하는 application에서 사용할 수 있다. node와 가중치(node 사이의 거리)가 있는 간선으로 표현되는 그래프에서 사용한다. 1번 노드에서 부터 6번 노드까지의 최단거리를 구해야 된다고 생각해보자. 모든 경우의 수에 대하여 계산해보자. (Brute force solution) 1 -> 2 -> 3 -> 4 -> 6 => 20 1 -> 2 -> 4 -> 6 => 15 1 -> 2 -> 5 -> 6 => 9 1 -> 3 -> 4 -> 6 => 13 최단경로는 3번째 경우의 수가 된다. 하지만 모든 경우의 수를 계산하는 방식은 시간이 많이 걸린다. =..
[알고리즘] 정렬알고리즘(2) - bubble sort, 버블정렬
Sorting algorithm 2. 버블정렬 버블정렬은 현재 인덱스와 현재 인덱스 + 1의 원소를 비교하여 정렬하는 방법이다. 1. 0번째 index의 값과 0 + 1번째 index의 값을 비교한다. 2. 0번째 index의 값이 더 클경우 swap을 진행한다. 간단하게 위 과정을 배열의 길이만큼 반복하면 된다. 코드로 구현 rust fn bubble_sort(array: &mut Vec) { for i in (0..array.len()).rev() { for j in 0..i { if array[j] > array[j + 1] { let curr = array[j]; array[j] = array[j + 1]; array[j + 1] = curr; } } } println!("{:?}", array)..
[알고리즘] 문자열_알고리즘 KMP 알고리즘
문자열 검색 알고리즘 문자열 검색 알고리즘은 자동완성, ctrl+f를 눌렀을 때 특정 단어를 찾을 경우 등 수많은 곳에서 활용된다. KMP알고리즘은 이 알고리즘을 개발한 사람의 이름을 따서 (Knuth, Morris, Prett) KMP알고리즘이라고 한다. 2개의 문자열간 일치하는 패턴을 확인하는 알고리즘이다. 만약 하나의 문자열과 다른 문자열을 비교할때 가장 단순하게는 문자열 하나하나를 비교해나가는 것일것이다. 단순 검색 문자열1은 "ABABCABCDE"이고 문자열2는 "ABCDE"라고 하자 문자열1을 기준으로 문자열2를 맞추어 나가면서 일치하는 문자열을 찾을때까지 순회할 수 있다. 1번째 비교 0 1 2 3 4 5 6 7 8 9 A B A B C A B C D E A B C D E 2번째 비교 0 1..
[알고리즘] 정렬 알고리즘(1) - selection sort, 선택정렬
정렬 알고리즘 시리즈를 시작해보려고 한다. 기초 정렬 알고리즘인 selection sort부터 시작해서 Insertion sort, merge sort, heap sort, bubble sort 등등.. 오늘은 그 첫번째인 선택정렬이다. Sorting algorithm 1. 선택정렬 선택정렬은 가장 작은 수를 선택하여 교환을 반복하는 정렬이다. interger type 배열의 정렬으로 예를 들어보자. 아래와 같은 배열이 있다. 이 배열을 순차적으로 돌며 가장 작은 값을 교환해줄 것이다. 1. 0번째 index부터 시작하여, 0번째 이후의 원소 중 가장 작은 값을 찾아서 값을 교환한다. 2. 1번째 index를 가리키며 1번째 이후의 원소 중 가장 작은 값을 찾아서 값을 교환한다. 3. 1번과 2번을 반복..
[알고리즘] Divide and conquer, 분할 정복 알고리즘
Divide and conquer, 분할 정복 알고리즘 단어 그대로 "분할", "정복", "합치기" 세개로 나누어 진행하는 알고리즘이다. divide and conquer알고리즘의 대표적인 예로는 merge sort가 있으며 quick sort, ip 주소 할당, memorization알고리즘 등이 있다. 1. 분할(divide) - 가장 작은 단위가 될때 까지 쪼갠다. - 주어진 문제의 최소단위로 나누어질때 까지 같은 작업을 반복하기 때문에 recursion으로 구현할 수 있다. 2. 정복(conquer) - 쪼개진 단위들을 정렬하며 합쳐나간다. merge sort의 time complexity는 O(logn)이 된다. 프로그래밍언어마다 내장되어 있는 sort method가 있다. //javascrip..
[자료구조] BST(Binary Search Tree, 이진탐색트리)
BST - 이진탐색과 연결 리스트를 결합한 자료구조이다. - 트리형태이며 하나의 노드는 left, value, right를 가진다. - value는 unique이다. - 어떤 노드를 기준으로 왼쪽노드의 value는 더 작은 값이 들어간다 - 어떤 노드를 기준으로 오른쪽노드의 value는 더 큰 값이 들어간다 - 루트 노드를 기준으로 왼쪽의 노드들의 value는 루트 노드의 value보다 작다. - 루트 노드를 기준으로 오른쪽의 노드들의 value는 루트 노드의 value보다 크다. - 현재 노드를 기준으로 큰 값은 오른쪽 작은 값은 왼쪽에 있으므로 time complexity는 O(logn)이다 1. 삽입 알고리즘 - root node부터 검색하여 큰값이면 오른쪽 작은값이면 왼쪽으로 위치시킬 수 있도록 ..