전공 수업 CS

[알고리즘] 동적계획법 | 최적 이진 탐색 트리

이진 탐색 트리는 루트의 왼쪽 서브트리에 있는 원소의 키 값은 루트보다 작고, 오른쪽 서브트리에 있는 원소의 값은 루트보다 큰 값을 가진다. 또, leaf 노드들 간의 depth 차이가 1보다 클 수 없다. 여기서 '최적'이란 단어까지 붙으면 최적 이진 검색트리가 된다. 최적 이진 검색 트리는 가능한 이진 검색 트리 중 key를 찾는데에 걸리는 평균 시간이 가장 짧은 이진 검색 트리를 의미한다. 즉, 트리 내의 키와 각 키가 탐색될 확률이 주어져 있을 때 그 트리의 평균 탐색 비용(평균 비교 횟수)를 계산하고 이를 최소화하는 탐색 트리를 구축하는 문제이다. 여기서 탐색 비용은 원하는 키를 찾기까지 필요한 비교 횟수를 뜻한다. 평균 탐색시간은 한 노드에 담긴 keym이 찾고자하는 search key일 확률..

[알고리즘] 동적 계획법 | 연쇄 행렬 곱셈

동적 계획법을 복습할겸 연쇄 행렬 곱셈에 대해 다시 한 번 정리하고자 한다. 연쇄 행렬 곱셈 문제가 뭔데? 주어진 n 개의 연쇄 행렬을 곱하는 최적의 순서를 구하시오. n 개의 연쇄 행렬 곱셈: A1 * A2 * ...* An [행렬 곱셈은 결합 법칙이 성립한다!] 예를 들어, (Ax * Ay) * Az = Ax * (Ay * Az) 이렇게 곱셈 순서를 바꾸어도 계산 결과가 같다는 뜻이다. 그러나 중요한 점은 행렬 곱셈의 순서에 따라 각 원소의 곱셈 횟수가 달라진다는 것이다. 그렇다면 최적의 순서는 곱셈의 횟수가 가장 작아지도록 하는게 최적일 것이다. 즉 이 문제는 최적화 문제라는 뜻이다. -> 원소의 곱셈 횟수를 최적화하는 문제를 찾아보도록하자. 연쇄 행렬 곱셈 문제를 이해해보자! 2 * 3 행렬과 3..

[알고리즘] 동적 계획법 | 행렬의 연쇄적 곱셈 | 연쇄 행렬 최소곱셈 알고리즘

연쇄행렬 최소곱셈 알고리즘 두 개 이상의 행렬을 곱할 때, 최소 곱셈 횟수를 구하는 문제이다. -> 행렬의 곱셈은 아래와 같이 결합법칩이 성립한다. A*(B*C) = (A*B)*C 그러나, 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라진다. 예를들어 설명하면, 행렬 A,B,C,D 4개가 존재한다. 각각 행렬의 차수는 20x1, 1x30, 30x10, 10x10이라고 한다. 4개의 행렬은 여러가지 방법으로 곱할 수 있지만, 다음 4개의 경우에 대하여 생각해볼때, 곱셈 횟수를 비교하면 아래와 같다. ((A*B)*C)*D) = (20*1*30) + (20*30*10) + (20*10*10) = 8,600 A*(B*(C*D)) = (30*10*10) + (1*30*10) + (20*1*10) = 3,500 (A..

[컴퓨터구조] 모듈러 연산

캐시 기억 장치의 설계를 공부하던 중 직접 사상에서 모듈러 연산 개념이 나왔다. 이 개념에 대해 알아보고자 글을 작성한다. Goal 모듈로 연산에 대한 이해 모듈로 덧셈, 뺄셈, 곱셈 연산에 대한 이해 모듈로 연산(Modulo Operation)이란? 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다. 정수론에서 모듈라 연산(modular arithmetic)이란, 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다. *나눗셈 정리(division theorem) 더보기 두 정수로부터 몫과 나머지를 얻는 연산 나머지 있는 나눗셈(division with remainders) 또는 유클리드 나눗셈(Euclidean division)이라고도 한다...

[컴퓨터구조] 주기억장치 DRAM | DRAM의 동작원리

1. DRAM의 구성요소 DRAM은 한개의 트랜지스터와 1개의 캐패시터로 구성됩니다. 트랜지스터는 전류의 흐름과 차단을 조절하는 소자이며(일종의 스위치), 캐피시터는 전하를 저장하는 소자입니다.(일종의 배터리) 1.1. Transistor(MOSFET) 트랜지스터는 gate, source, drain 3개의 연결지점을 가지는데 source와 drain중 전위가 높은 곳이 drain이 되고, 낮은 곳이 source가 됩니다. 즉, 전류는 전위가 높은 곳에서 낮은 곳으로 흐르므로 drain에서 source로 전류가 흐르게 됩니다. 또한 source와 drain의 위치가 전위의 상대적인 차이로 고정되지않고 바뀌므로, DRAM에서 전류는 양방향으로 흐를 수 있습니다. 이때 흐르는 전류의 양은 gate와 sour..

[알고리즘] 욕심쟁이 알고리즘 | 그리디 알고리즘(Greedy Algorithm)동적 계획법을 공부하다가 궁금해진 알고리즘

그리디 알고리즘을 한 마디로 정의해 보자면, 눈 앞에 보이는 최적의 상황만을 보는 알고리즘이라고 할 수 있다. 이 알고리즘은 항상 최적해를 도출하는 것은 아니다. 그러나 어느정도는 최적해에 근사한 값을 빠른 속도로 구할 수 있다는 장점을 가진다. 또한 특정한 상황에서 최적해를 보장할 수 있다는 장점이 있다. 그리디 알고리즘의 대표적인 예제는 거스름돈 문제이다. 예를 들어 730원을 거슬러주어야할때 10원짜리 동전을 73개 거슬러 주기 보다, 500원짜리 1개와 30원짜리 3개를 주는 것이 편하다. 따라서 이 경우 '무조건 더 큰 화폐 단위부터 거슬러 준다'는 알고리즘만 지킨다면 최적의 해를 보장할 수 있다. 그리디 알고리즘은 극단적으로 문제를 접근한다는 점에서 ( 무조건적으로 큰 경우대로, 작은 경우대로..

[알고리즘] 동적 계획법 | 다이나믹 프로그래밍 ( Dynamic Programing)

동적 계획법은 주어진 문제를 여러 개의 부분 문제로 분할하여 각 부분문제의 해결안을 바탕으로 주어진 문제를 해결하는 기법이다. 이 때 각 부분 문제는 다시 여러개의 부분 문제로 분할될 수 있다. 각 부분문제는 원래 주어진 문제와 동일한 문제이지만 입력 크기가 작다. 따라서 부분 문제를 반복해서 분할하면 궁극적으로 입력의 크기가 매우 작은 단순한 문제가 되기에 쉽게 문제를 해결할 수 있게된다. 반복해서 여러 번 호출되는 부분 문제가 있을 경우 해당되는 부분 문제가 첫 번째 수행될 때 그 결과를 기록해 두었다가 이후에 다시 수행이 요구될 때 또 수행하지 않고 기록해둔 결과를 이용하는 것이 동적 계획법의 핵심이다. 즉, 한 마디로 동적 계획법을 표현하자면 '하나의 문제는 단 한 번만 풀도록 하는 알고리즘'이다..

[알고리즘] 스트링 처리 알고리즘 | 허프만 코드, 허프만 알고리즘

압축이란 파일의 크기를 줄이는 방법을 의미한다. 즉, 시간 보다는 공간을 절약하는 방법에 대해 연구한다. 대부분의 컴퓨터 화일에서는 데이터가 중복되어 있다고 착안하고 있다. 압축을 하게되면 한정된 컴퓨터자원을 효율적으로 사용할 수 있다. 1) 런-길이 인코딩 화일에서 기본적인 중복은 같은 문자가 연속적으로 나타나는 것이다. 하나 예시를 들어보자면, AAAABBCCCCC = 4A2B5C 와 같이 표현할 수 있다. 위와 같이 동일한 문자가 여러개 나올 경우 숫자와 문자 쌍으로 화일을 압축하는 기법을 '런-길이 인코딩'이라고 한다. 그러나 실제 문서에서는 같은 문자가 여러번 연속해서 나오는 경우가 많지 않기에 런-길이 인코딩은 주로 이진수로 표현되는 비트맵 이미지를 압축하는데 사용된다. 예를들어 이진수 000..

[알고리즘] 스트링 처리 알고리즘 | 화일 압축 알고리즘 | 허프만 인코딩

파일 압축 1. Huffman Encoding 1) 특징 1. 무손실 압축 허프만 인코딩은 무손실 압축이라는 점에 있어서 매우 큰 장점을 가진다. 즉, 압축을 할 때, 원본의 정보가 전혀 손상되지 않고 압축이 가능하다는 것이다. 2. 가변 길이 인코딩 가변 길이 인코딩이란? 자주 나타나는 문자에는 길이가 작은 비트를 사용하고 적게 나타나는 문자에는 길이가 긴 비트를 사용해 encoding하는 압축 기법이다. 즉, 해당 파일의 형태에 따라 압축 방법이 달라진다는 것이다. 3. 가변 길이 인코딩의 주의점 가변 길이 인코딩을 사용할 때, 정말 아무생각 없이 시도한다면 다음과 같이 코드를 할당할 수 있다. 여기에는 큰 문제점이 존재한다. 예를들어 BAC라는 문자를 Encoding한다고 하면 1010이 될 것이다..

[알고리즘] 스트링 처리 알고리즘 | 패턴 매칭 알고리즘

패턴 매칭 알고리즘 이 알고리즘은 정해진 문자를 찾는것이 아니라 특정 패턴의 문자를 찾는 알고리즘이다. 1) 정규 표현식 (아래의 표현식 이외에도 수많은 식들이 있는데 이는 구글링을 통해 참고하자.) AB : AB를 찾는다. A+B : A또는 B를 찾는다. ()* : ()안의 문자들이 0번 이상 나타나는 경우를 찾는다. ? : 해당 자리에 어떤 문자라도 들어올 수 있다. (0개 또는 1개) (예시) ?*(ie+ei)?* : ie 또는 ei를 갖고 있는 모든 단어 (1+01)*(0+1) : 두개의 0이 연속적으로 나오지 않는 0과 1로 이루어진 문자열 2) 패턴 매칭 장치 그리기 패턴 매칭 장치는 위에서 보았던 KMP의 유한 상태 장치처럼 현재 상태에 따라 다음에 어떤 것을 해야할 지 그림으로 표현한 장치..