SOLID BASIC

[알고리즘] 동적계획법 | 스트링 편집 거리(String edit distance)

스트링 편집 거리(String edit distance)는 두 스트링의 유사도를 측정하기 위해 사용되는 알고리즘을 말한다. 이 알고리즘을 제안한 수학자의 이름을 따서 레벤슈타인 거리 라고도 불린다. (LD) 원래 스트링: S 목표 스트링: T 라고 할때, 원래 스트링을 목표 스트링으로 변환하는데 필요한 삽입, 삭제, 대치 연산의 최소 비용을 편집 거리하고 한다. 삽입: 원래 스트링에 새로운 문자를 삽입하는 연산 삭제: 특정 위치에 있는 문자를 삭제 대치 : 특정 위치의 문자를 다른 문자로 바꾸는 연산 세 종류의 연산마다 비용이 정해져 있다. 예를 들어보자! S: "test"이고 T: "tent"라면, "s" 을 "n"으로 변경하는 하나의 대치 연산을 함으로써 S를 T로 변환할 수 있으므로 LD(S, T)..

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

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

[C언어] 헷갈리는 getchar() 함수 이해하기

전공수업 C 언어 문자열 단원을 공부하던 중 getchar() 함수의 버퍼 개념에 대해 확실히 알고자 글을 정리한다. getchar() 버퍼에 데이터가 있을 때 = > 버퍼 가장 앞의 데이터를 반환한다 버퍼에 데이터가 없을 때 = > 엔터(‘\n’)가 올 때까지 사용자로부터 문자를 받아서 버퍼에 저장하고 가장 앞의 데이터를 반환한다 이때, 버퍼는 라고 생각하면 된다. getchar()함수를 연속으로 썼을 때 오류가 생긴다면 버퍼의 데이터 문제일 가능성이 크다. int main(void) { char s1; getchar(); s1=getchar(); } 처음 getchar()에서 ‘h’입력 => 버퍼에 ‘\n’이 남..

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

동적 계획법을 복습할겸 연쇄 행렬 곱셈에 대해 다시 한 번 정리하고자 한다. 연쇄 행렬 곱셈 문제가 뭔데? 주어진 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..

[C언어] 포인터 헷갈리는 개념 정리

전공수업과정 공부중 헷갈리는 부분을 정리하고자 한다. 1. 포인터 C에서 int, char, 포인터 변수는 각각 다음 형태의 값을 저장한다. char : 문자형 값 int : 정수형 값 포인터 : 메모리 주소 &는 주소 연산자로, 해당 변수의 메모리 주소값을 반환한다. *는 간접지정 연산자로, 해당 메모리 주소값에 저장된 값에 접근한다. 위 문법을 통해 다음과 같은 연산이 이루어진다. 참고 Q. ptr에 저장된 값은 num의 주솟값인 &num이라 했는데, 그럼 이번엔 &ptr을 출력하면 어떤 값이 나올까? A. 당연하게도 ptr 포인터 변수의 주소값인 0104가 출력된다. 포인터 변수도 기본 변수와 마찬가지로 메모리 영역에 선언되기 때문이다. 2. 배열과 포인터 배열은 연속된 데이터를 저장하기 위한 자료..

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

캐시 기억 장치의 설계를 공부하던 중 직접 사상에서 모듈러 연산 개념이 나왔다. 이 개념에 대해 알아보고자 글을 작성한다. 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)

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