CS

머신러닝의 종류머신러닝의 종류는 3가지로 나눌 수 있다. supervised : 지도학습은 정해진 답을 알려주면서 학습시키는 방법이다. input으로 label(답)을 입력시키고 이것을 학습한 것을 바탕으로 예측하는 방법이다.unsupervised : 비지도학습은 정해진 답을 제공하지 않고 비슷한 데이터끼리 clustering 하는 방법이다.reinforcement : 머신러닝의 꽃이라 불리는 강화학습은 정답이 따로 없고 본인이 학습하고 난 후 보상을 받는 방식으로 학습된다.  머신러닝 모델링과 예측머신러닝에서 데이터셋은 특징 벡터와 레이블로 표현된다. 일반적으로 기계 학습 모델을 학습시키는데 쓰이는 것을 train set, 기계 학습 모델의 성능을 평가하기 위해서 사용되는 것이 test set이다. t..

Instruction Set Architecture(ISA) 명령어는 컴퓨터가 이해할 수 있는 언어이자 프로세서가 돌아가게 하기 위한 최소 단위이다. 소프트웨어와 하드웨어의 인터페이스라고 할 수 있다. 여기에서 잠시 생각해보자. 인텔 CPU와 AMD CPU는 같을까? 동일한 아키텍쳐를 가진다. 그 이유는 OS를 설치해보면 알 수 있는데, 동일한 명령어 집합을 공유하고 있기 때문이다. 그러나 마이크로아키텍쳐는 다르다. 동일한 명령어 집합을 사용하면서, 회사마다 회로 설계방식은 다를 수 있기 때문이다. 지난 글에서 언급했듯 마이크로아키텍쳐는 CPU의 하드웨어 설계를 말한다. 컴퓨터는 2개의 상태를 가지는데, register와 memory이다. 우리는 명령어를 사용해서 각각의 상태를 관리해주어야 한다. 관리하..

컴퓨터란?컴퓨터란 계산하는 기계라는 의미로, 수학적 논리적 계산을 수행하는 기계다. Von Neumann Architecture은 모든 현대 컴퓨터의 시초라고 할 수 있다. 초기 컴퓨터는 기능에 따라 회로를 하나하나 바꿔야 했다. 그러나 효율성이 크게 떨어지는 문제로 모든 프로그램을 메모리 안에 저장하기 시작했다. 이것이 Stored Program Computer(내장형 프로그램 컴퓨터)이다. 대부분 Sequential로 동작한다. Processing Unit은 산술 논리 장치와 레지스터를 의미하고 Control Unit은 명령 레지스터와 Program Counter를 의미한다. 메모리에는 프로그램에 필요한 데이터와 명령어가 저장된다.그러나 이 아키텍쳐는 병목현상이라는 문제점이 있다. 이는 CPU와 메모..

Backtracking은 DFS와 같은 방식으로 트리를 탐색하는 방법 중 하나다. 탐색을 진행하다가 더 갈 수 없으면 다시 이전 노드로 돌아와 탐색하는 방법이다. Sum of Subsets 문제도 backtracking으로 풀 수 있는 문제 중 하나다. Sum of Subsets은 집합 wi의 부분 집합 중 그 합이 W와 같은 부분 집합들을 찾는 문제다. 예를 들어서, 𝑛 = 5, 𝑊 = 21, and 𝑤𝑖 = [5, 6, 10, 11, 16]이 주어졌다고 하자. 그러면 21이 될 수 있는 조합은 {5, 6, 10}, {5, 16}, {10, 11}이다. 이렇게 푸는 것을 상태공간트리를 만들어서 풀어보자. 왼쪽은 wi를 포함시키는 것이고 오른쪽은 wi를 포함하지 않을 때의 값이다. weight가 ..

K번째로 작은 값 찾기Median of MediansQuick sort으로 Selection 문제를 접근하는 데에 있어 불균형을 해결하기 위해서, 비교적 균등하게 배열을 나누는 알고리즘이다. 문제를 푸는 방법은 다음과 같다. 1. 배열 L을 5개씩 묶어준다. 즉, n/5로 분할한다.2. 각 묶음에서 median 값을 찾는다. 이때, 묶음은 5개이므로 6번 비교하면 median 값을 찾을 수 있다. 비교 횟수는 총 (6 * n/5)번이다.3. Median들 중에서 median인 m*을 찾는다. 이때 T(n/5)가 걸린다.4. m*과 비교해서 loser 그룹과 winner 그룹으로 나눈다. 비교 횟수는 총 n번이다.5. 재귀호출하거나 m*를 반환한다. 이때 T(|loser|) 이거나 T(|winner|) 시..

K번째로 작은 값 찾기Quick sortn과 K가 주어질 때 K 번째로 작은 값을 찾아야 한다. Quick Sort 방식으로 pivot보다 작은 것은 왼쪽, 큰 것은 오른쪽에 두고 pivot이 K번째에 위치할 때까지 재귀적으로 반복하여 푸는 방법이다. 먼저 pivot을 선택한다음에 Loser 배열과 Winner 배열로 나눈다. Loser는 pivot보다 작고 Winner은 pivot보다 큰 값들의 배열이다. pivot과 같은 값이면 M 배열에 집어 넣는다. 이 배열들을 만들기 위해서는 n-1번의 비교가 필요하다. Loser 집합의 개수가 K보다 큰 경우우리가 찾으려는 K가 Loser에 존재한다는 뜻으로, K번째 값을 반환하면 된다.Loser 집합의 개수와 M 집합의 개수가 K보다 작은 경우우리가 찾으려는..

일반적으로 Selection Problem은 정렬되지 않은 배열에서 K번째로 큰 값 혹은 작은 값을 구하는 문제이다. K = 1이라면, 그 배열에서 가장 큰 값 혹은 가장 작은 값을 구하고 K = 2라면 2번째로 큰 값 혹은 2번째로 작은 값을 찾으면 된다.입력 : n개의 값과 K(1출력 : K번째로 크거나 작은 값목표 : 비교 횟수를 최적화하는 것 최댓값 찾기(K = n)K = n일 때, S 배열에서 가장 큰 값을 찾아야 한다. S 배열의 수가 n일 때, n-1번 비교해야 한다. n-1 번이면 항상 최댓값을 찾을 수 있기 때문에 상한(Upper Bound)이라고 한다. n-1 번이면 최솟값을 찾기 위한 하한(Lower Bound)이다.  최솟값과 최댓값을 동시에 찾기(K = 1, K = n)최댓값과 최..

이전 글에서는 Knapsack problem을 Backtracking으로 접근하여 최적 해를 구했다. 이 방법은 bound가 maxprofit보다 크지 않을 때 non-promising이라고 판단한다. 알고리즘의 효율성을 따지면, 조금 더 나은 방법이 있다.그 방법은 branch and bound로 접근하는 것이다. 이 방법의 특징을 잘 살리면 bound를 보고 판단하는 것 외에, promising한 노드들의 bound를 비교해서 그 중에서 가장 좋은 자식 노드들만 방문할 수 있다. DFS처럼 이미 정해진 순서대로 노드를 방문하는 것보다 더 빠르게 최적값을 찾을 수 있다. 이런 방법을 Best-First Search with branch and bound라고 한다. 이러한 방법은 BFS 방식을 약간 수정..

Knapsack Problem은 아주 유명한 문제이다. 어떤 배낭이 있고 그 배낭에 넣을 수 있는 최대 무게가 W라고 하자. 배낭에 넣을 수 있는  n개의 물건이 각각 무게 wi와 이익 pi를 가지고 있을 때, 배낭이 최대한 비싼 물건들을 담을 수 있는 조합을 찾는 문제이다. knapsack 문제는 원하는 만큼 물건을 쪼개어 담는 문제인 Fractional Knapsack와 물건을 쪼갤 수 없어 무게와 가치가 무조건 정수형태를 가지는 0-1 Knapsack 두 유형으로 나뉜다. 이번에는 0-1 Knapsack 문제를 해결하는 방법에 대해서 생각해보자.먼저 마디가 promising한지 판단해야 한다. Greedy Algorithm으로 접근하면, 해당 아이템의 무게가 배낭에 넣을 수 있는 최대 무게 W보다 ..

Switch현재 이더넷은 star topology 형태로 동작하기 때문에 스위치나 허브의 도움이 필요하다. 스위치와 허브의 차이를 잠깐 짚어보자면, 허브는 각 노드의 위치를 저장하고 있지 않기 때문에 데이터를 받으면 연결된 모든 기기에 데이터를 전송한다. 반면에 스위치는 스위치 테이블이 있어서 해당하는 기기에만 데이터를 전송한다. 스위치가 테이블을 만드는 과정을 알아보자.  스위치는 처음에 모든 기기에 대한 정보를 가지고 있지 않는다. 스위치는 라우터와 같이 프로토콜을 사용해서 테이블을 만드는 것이 아니라 Self-Learning으로 테이블을 만든다. 스위치로 프레임이 들어오면 송신자 주소를 확인하고 이를 스위치 테이블에 기록한다. 스위치에 연결된 모든 기기들이 한번씩 프레임을 보내면 테이블이 완성된다...