오래 못 할 짓 하지 않기

우리는 문자를 0과 1로 표시하여 나타내려고 한다. Huffman 알고리즘은 Text Encoding 을 위한 알고리즘이다. : 문자의 출현 빈도에 따라 다른 길이를 사용하여 압축한다. = 많이 나오는 문자는 짧은 길이로, 그렇지 않으면 길게 표현하여 비트 수를 줄인다. 우선 이걸 이해하기 전에 Prefix라는 개념을 이해해야한다. Prefix (free) code : 어느 하나의 코드가 다른 하나 코드의 접두code가 되지 않아야 한다. - 목적 : 모호성( Ambiguity ) 을 피하기 위해 - 원인 : Huffman 코드는 각 문자마다 다른 길이를 사용하기에 어느 길이만큼 잘라야 하는지에 대한 Ambiguity 이 있다. ex) [ A, B, C, D ] 라는 문자를 각각 [ 0, 01, 10 ,..

An Activity-Selection Problem : 각 Exclusive한 Activity 에 스케줄이 있고, 그 Activity들의 수를 최대한 많이 선택하는 문제 ex) 주어진 시간동안 많은 놀이기구를 타는 경우 [ 2 ,3 ) [ 3, 5 ) 는 서로 Mutually compatible하다. *Compatible : 'Overlap이 없다' ▶ Compatible한 Activity들을 최대한 많이 선택하기 si = 시작하는 시간 → [ fi = 끝나는 시간 → ) ● S 라는 set은 n 개의 activity 가 있다. ● Si,j 는 ai로 시작해서 aj로 끝나는 S의 Subset이다. 얘를 DP로 풀어보자. 1. 우선 Si,j에 대한 Optimal schedule을 구한다. - 양 끝 ai..

먼저 알아야 하는 내용: ● pthread_create(): 새로 Thread를 만든다. ( Process에서는 Fork ) ● pthread_join() : 현재 있는 Thread를 다른 Thread가 return될 때까지 멈춘다. ( Process에서는 wait ) 예제 1) ● 배열 값이 1,5인 range1 을 parameter로 받는 thread 하나 생성 > thread_summation 에서 계산, > start = 1 , end 5 > 전역변수 sum에 1~5의 값을 더함 ※ Thread는 하나의 Process의 자원을 공유하기 때문에 다른 Thread에서도 이 값을 사용가능하다. > pthread_join를 해서, id_t1가 끝날 때까지 기다린다. ● 배열 값이 6,10 인 range2..

Thread - Process : 실행중인 프로그램 - Thread : 하나의 프로그램에서 2개 이상으로 나뉘어져 동시에 실행되는 하나의 단위 = 그냥 프로그램이라는 옷에 있는 한 가닥 실 이라는 표현이 정확할 것 같다. 스레드 특징 ) 하나의 프로세스 안에 있는 Thread끼리는 Resources를 공유한다. Process가 공장 Thread가 일꾼이라고 생각하면 된다. Thread Control Blcok (TCB) : Thread에 관련된 정보를 담아둔다. ● 정보 : - Thread id - Thread 상태 - Stack pointer - Prograrm counter - Pointer to PCB ( 자기가 속해있는 프로세스의 PCB 를 가리킨다. ) 근데 Thread를 쓰는 이유는? 하나의 ..

다이나믹 프로그래밍은 Blind 된 게 많다. 어느 것이 Optimal solution인지 판단하기 위해서 계산해야 하는 게 많다. 그렇게 Optimal인지도 모르는 solution을 계산하느라 시간이 많이 날라간다. 지난 번에 DP를 이용해서 MCM을 구할 땐, 색칠되어 있는 모든 칸들을 계산했다. 그런 뒤에 값이 가장 최적인 값을 구했다. 따라서, 어떤 선택이 최선인지 정하고 필요없는 옵션들을 조금 더 제한한다면 더 좋은 성능을 낼 수 있을 것이다. Greedy 알고리즘은 어느 것이 최고의 선택인지 정할 수 있게 해준다. (당연히 이걸 쓸 수 있는 문제들이 있음, MCM은 DP가 맞음) Greedy 알고리즘 : 매 순간에서 가장 최고의 선택을 한다고 생각하면 된다. ex) 여기에서 가장 괜찮은 식당은..

프로세스의 종류는 2가지가 있다. ● 독립적 Independent 이건 자기가 할 거 알아서 하면 됨 (우리가 오늘 배울 건) ● 협력적 Cooperating → Cooperate하는 프로세스끼리 서로 영향을 주고 받는다. 그러기 위해서는 Inter Process Communication IPC가 필요하다. IPC의 종류 ● Shared memory ● Message Passing 그럼 하나씩 알아보자 ● Shared memory ( Producer / consumer 개념 ) : 프로세스 간에 소통하려고 하는 곳에 있는 메모리 서로 정보를 직접 던지는 게 아니라, 프로세스 사이에 있는 메모리에 두고 거기로 주고 받는다. (쉽게 생각하면 케이시 헌병 건물에서 물건 받는 창구라고 생각하면 된다.) * Sh..

MCM = Multiply Chain Matrix ▶ 행렬들을 곱할 때 어떤 순서로 곱해야 최소한의 연산을 하는지 구하는 알고리즘 [ 1,3 ] 에 표시되어 있는데 이는 A1, A2, A3까지 곱했을 때 최소한의 연산을 하는 값이 들어가있다. 만약 [1,4] 에 표시가 되어있다고 했을 떈, [1,3] * [ 4 ,4 ] 의 값이 [ 1,4 ]에 들어간다. 이 때 [1,3]의 값은 (새로 계산하는 것이 아니라) 이전에 계산해서 구했던 [1,3]의 최소 연산값을 참조해서 사용한다. A3 * A4 * A5 * A6을 곱하는 [ 3, 6 ] 은 위와 같이 3개의 경우의 수로 나눌 수 있다. 이 때 [ 3, 6 ] 에는 저 3가지 경우에서 가장 Optimal한 값이 들어간다. * A3 ~ A5 까지의 연산에서 O..

With : 임시적으로 만드는 Relation table 여기에서 VNDR_CODE가 1001이나 1002인것들만 추출한다고 해보자 위 테이블을 보면 2개의 Select 덩어리가 있다. 두 개의 덩어리는 다 같은 내용에다가 마지막 where절 부분만 다르다. Select + From + Join 만 같고 Where만 다르다면, Where 전 부분을 한 덩어리로 치환할 수 있지 않을까? 라는 생각에서 시작한다. 이렇게 완성 가능하다. 그냥 긴 구문을 하나의 변수에 담아둔다고 생각하면 편하다. 그걸 Table로 사용할 수 있기 때문에 From에 넣어도 된다. IN / NOT IN 다음과 같이 2017 2학기, 2018 1학기에 열린 수업을 조회한다고 했을 때 Outer 쿼리에는 2017 2학기 수업들을 골라..

Process Creation ● Parent 프로세스가 Child 프로세스를 만든다. - 모든 프로세스에 id가 있다. = Process identifier - 프로세스들의 parent,child관계로 오른쪽 그림과 같이 트리를 만들 수 있다. 이와 관련된 명령어로는 다음과 같이 3개가 있다. ● fork() : 새로운 Child process를 만들고, 그 프로세스의 Pid를 return받는다. ex) int pid = fork() 하면 자식 프로세스의 pid가 변수에 저장된다. ※ 부모 프로세스에서만 변수 pid에 자식 pid가 저장됨, 자식 프로세스에서는 저 값이 0이다. ● exec() : 프로그램을 실행한다. 근데 이제,, 여러 추가 기능을 곁들인 ● wait() : 자식 프로세스가 끝날 때까..

https://min-h-study-review.tistory.com/266Dynamic Programming알고리즘X디자인 패러다임이다. ● 언제 사용되느냐?  : Optimization 문제에서 사용된다. ex) Minimization / Max..~  → 최단 경로 찾기,Job scheduling 과 같이       선택해야 하는 문제에 쓰인다.   ● 방법하나의 큰 문제를 Dynamic한 여러 작은 문제로 나누어서 푼다.S라는 큰 문제 하나를 S1,S2,S3...Sm으로 나눈 뒤, 그들을 합한다. 이러면 Divide and Conquer 랑 다를 게 없어보이는데, 차이점으로는 DP는 가장 작은 케이스에서부터 시작한다는 것이다. - 공통점 : 작은 문제를 통해 큰..