네트워크(Network) 컴퓨터와 같은 호스트(host) 간에 전송 매체들이 연결되어 데이터를 교환하는 시스템 자체를 이야기한다. 데이터의 교환 방식에는 다양한 방법들이 존재하는데, 시스템이 데이터를 교환할 때는 일련의 통신 규칙인 프로토콜(Protocol)에 의해 통신이 이루어진다.IP라는 프로토콜을 사용하는 네트워크인 인터넷이 대표적인 네트워크 통신망이다. 프로토콜(Protocol) 데이터 통신을 위해서 사용하는 통신 규약을 말한다. 대표적으로 인터넷에서 사용하는 프로토콜인 IP(Internet Protocol)이 있다. 인터넷을 사용할 때는 IP 패킷이라는 단위로 여러 정보들을 담아서 서버간 통신을 진행한다. 패킷(Packet)데이터 통신이 이루어질때 네트워크를 통해서 송수신되는 데이터 조각이..
그리디(=욕심쟁이, 탐욕) 알고리즘 그리디 알고리즘은 각 단계에서 가장 최선의 선택을 한 후, 선택한 답이 전체적으로도 최선의 방법이기를 '바라는' 알고리즘이다. 최선의 방법이기를 바란다는 말에서 알 수 있듯이 부분적(local)으로만 최선의 해답이고 전역적(global)으로는 최선의 방법이 아닌 경우에 그리디 알고리즘을 적용하게 되면 최선의 해답을 얻을 수 없다. 즉, 그리디 알고리즘을 사용한다고 해서 무조건 최선의 해답을 보장할 수 없다. 따라서 그리디 알고리즘을 사용했을 때 최적의 해답을 주는지가 검증되어야 한다. vs DP 그리디 알고리즘은 동적 프로그래밍과 다르게 지난 선택이나 앞으로의 선택을 고려하지 않는다. 그러므로 탐욕 알고리즘을 적용하려면 앞의 선택이 이후 선택에 영향을 주지 않고 부분적..
LIS LIS는 Longest Increasing Subsequence 의 약자로 한글로는 ‘최장 증가수열’, 또는 ‘최대 증가 부분수열’로 불린다. 이것은 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분수열 중 가장 긴 수열을 말하는데 이때 부분수열의 숫자들은 원 배열에서 위치가 이어져 있지 않아도 된다는 주요한 특징이 있다. 예를 들어 원 배열이 [1,4,6,8,3,5,6,7]일 때 [1,6,8], [4,6,8], [1,7]은 증가 부분수열인데, 이 중 가장 긴 부분수열은 [1,3,5,6,7]이 된다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작..
JOIN JOIN은 두개 이상의 테이블에 대해서 결합하여 나타낼때 사용한다. 결합을 위해서 조건을 지정해줄 수도 있는데, 이 조건은 각 테이블의 열이 일치하는지 여부를 기준으로 한다. 내부 조인은 두 테이블 모두에서 일치하는 값을 가진 행만 골라서 테이블을 만들어서 반환한다. A와 B라는 두 개의 테이블이 있다고 하자. 위 사진에서 볼 수 있듯이 JOIN은 SELECT FROM TABLE A JOIN TABLE B ON 라고 하면 A의 col_a와 B의 col_b가 같은 열들의 경우 A와 B의 선택한 columns 정보를 합쳐서 새로운 테이블을 생성해준다. 위와 같은 두 개의 테이블이 있다고 할 때, SELECT A.ID, A.NAME, B.KNAME FROM A INNER JOIN B ON A.ID=B..
백트래킹 백트래킹이란 말 그대로 '되추적'의 의미를 가진다. 즉 어떤 노드의 유망성을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가서 다른 자식 노드를 찾는 방법을 의미한다. 브루트 포스 알고리즘과 다른 점은, 모든 경우의 수 중에서 가능성이 존재하지 않는다면(=더 이상 유망하지 않다면) 더이상 탐색하지 않는다는 점이다. 이를 위해서는 상태공간트리를 그려 DFS와 같은 탐색 알고리즘을 통해서 구현할 수 있다. DFS의 특징 자기 자신을 호출하는 순환형태의 알고리즘 형태를 가진다. (재귀 호출이 이루어진다) 상태공간트리에서 탐색한 노드에 대한 정보를 검사해야 한다. 상태공간트리에서 탐색할 노드가 유망한지를 검사해야 한다. 트리의 branch의 끝까지 탐색해야 다음 branch를 탐색하기 때문..
4. Mergesort 병합정렬은 divide and conquer의 방법을 사용하는 분할 정복 알고리즘이다. divide and conquer란 DP에서 설명했듯 큰 문제를 작은 문제들로 나누어 각각을 푸는 것으로, top-down approach의 방식으로 접근한다. divide and conquer의 특성을 이용하는 만큼 재귀호출을 이용한다. //pseudocode mergeSort(left, right) { if(left
정렬 알고리즘 정렬 알고리즘은 n개의 input이 주어졌을 때, 이것들을 특정한 기준을 정해(오름차순, 내림차순) 정렬하여 출력하는 알고리즘이다. 효율적인 정렬은 데이터의 정규화를 통해 정렬된 상태에서 사용 가능한 다른 알고리즘을 수행하기 위해 필요하다. 이러한 정렬 알고리즘은 여러 종류가 있으며, 그 방법에 따라 다양한 수행시간을 가진다. 대부분 O(nlgn)과 O(n^2) 사이의 시간복잡도를 가지지만, input이 특수한 성질을 만족하는 경우에는 O(n) sorting도 가능하다. 1. Selection Sort 범위 내의 최소/최대값을 선택해서 한쪽으로 열외시키는 것 반복 선택정렬은 배열을 한쪽 방향부터 정렬하는 제자리 정렬 알고리즘이다. 제자리 정렬 알고리즘이란 input에 필요한 메모리 외에 추..
피보나치 문제의 예시를 보자. 피보나치의 경우 재귀함수를 이용한 Divide-and-Conquer 방법으로 풀 수도 있지만, 재귀의 방법을 사용하면 모든 호출된 재귀함수들이 fib(1)에서부터 계산해나가야 하기 때문에 수행시간이 길다. //재귀를 사용한 피보나치, Top-down public int fibInRecursive(int n) { if(n=1) { fib[1]=1; for(int i=2; i
탐색 알고리즘 주어진 input에서 원하는 data를 찾기 위한 알고리즘. 1. Sequential search 리스트에서 저장된 데이터를 차례로 검사한다. 무작위로 저장된 리스트를 탐색할 수 있지만, 최악의 경우(리스트에 찾으려는 데이터가 존재하지 않거나, 리스트의 마지막에 데이터가 존재하는 경우) n개의 input size를 갖는 리스트를 탐색할때 O(n)의 시간복잡도를 가진다. public int seqSearch(int[] arr, int target) { for(int i=0; i
0. Analysis of Algorithms 1. Search 1-1. Sequential Search 1-2. Binary Search 1-3. Static Searching - Binary Search Tree 1-4. Dynamic Searching - B-tree 1-5. Hashing 2. Sorting 2-1. Selections Sort 2-2. Bubble Sort, Exchange Sort 2-3. Insertion Sort 2-4. Merge Sort 2-5. QuickSort 2-6. HeapSort 2-7. Counting Sort 2-8. Radix Sort 3. Matrix Multiplication - Strassen's 4. Dynamic Programming 4-1. Bi..
실제 메모리가 얼마나 있던지에 상관없이 프로세서에 일정한 크기의 메모리가 있는 것처럼 환상을 주자! 앞서 Processor와 Main memory의 속도적 한계를 극복하기 위하여 캐시메모리를 사용했다. 캐시메모리에 사용될 확률이 높은 데이터들을 미리 저장해두고 hit이면 빠르게 사용할 수 있게 한 것이다. 이번 Virtual Memory는 메인메모리와 Disk사이의 크기적 한계를 극복하기 위해서 메인메모리를 프로세서와 disk사이의 일종의 '캐시'로 사용하는 것이다. 실제 물리적인 메모리의 크기가 nGB라고 하면 프로그램 하나에서 메모리 전체를 사용하는 경우는 드물기에 필요한 메모리만 사용하게 하는 것이다. VM의 특징 캐시메모리와는 다르게 VM의 경우 miss penalty가 매우 크기 때문에 page..
저번의 Direct Mapped Cache에 이어서 1-2. n-way Set Associative Cache Direct Mapped Cache의 경우 block의 개수가 1개였다. 여러개의 Word를 하나의 index에 저장하는 n-word block방식으로 여러개의 word를 한꺼번에 저장하여 hit rate를 높일 수 있다는 장점이 존재하기는 했지만 index단위로 갱신되는 특성상 같은 index에는 하나의 block만 저장할 수 있었다. 이러한 단점을 해결하기 위해 n-way Set Associative Cache라는 방법이 존재한다. block의 크기를 단순히 늘리는 것이 아니라, 하나의 index에 여러개의 set을 두는 것이다. n-word block 방식과 비슷해 보일수도 있지만 여기서는..