中庸 中庸

Decision Problem 에 Reduction 을 적용하는 사례들에 대해 살펴보도록 하겠습니다. 두 Decision Problem X, Y 에 대해 다음과 같은 관계가 존재하는 경우, X is reducible to Y 라고 할 수 있습니다. 임의의 X의 Instance Ix 를 2번을 만족하는 Y의 Instance Iy 로의 변환이 가능해야합니다. Instance Iy 에 대한 Y의 답을 이용하여 Instance Ix 에 대한 X의 답을 구할 수 있어야 합니다. Decision Problem 인 경우에 한하여 두 답은 언제나 동일해야 합니다. ( Ix 에 대한 X의 답 Iy 에 대한 Y의 답 (if and only if 로 양방향으로 같다는 것을 증명해야합니다.) ) X가 Y로 reducible ..

Reduction 이란 문제 X와 문제 Y가 있을 때 문제 Y를 해결하는 알고리즘 Ay 가 존재한다고 할 때, Ay 를 이용하여 문제 X를 해결하는 알고리즘 Ax 를 디자인 할 수 있는 경우 문제 X에서 Y로 reduction 이 가능하다 (X is reducible to Y)고 이야기합니다. (Strict 한 정의는 아닙니다.) 그리고 X에서 Y로의 reduction 이 가능함을 X

Shell lab trace 09 번은 부모 프로세스 (tiny shell) 이 sigtstp 를 수신하면, foreground 로 실행중인 job 을 suspend 시키고 tshref 의 출력에 맞추는 문제입니다. 먼저 trace09.txt 파일을 확인해보겠습니다. ./mytstpp 를 실행한 후 job 로 joblist를 출력하게 만들 것을 예상할 수 있습니다. 이번엔 mytstpp.c 파일을 열어보도록 하겠습니다. 먼저 mytstpp는 trace08 에서 살펴보았던 그것과 굉장히 유사한 구조를 갖고 있습니다. 차이점은 parent process 에 sigtstp 시그널을 보낸다는 것입니다. 그렇다면 부모 프로세스에서는 sigtstp 를 수신하면 handler를 통해서 foreground job 을 ..

Shell lab Trace 08 은 부모 프로세스가 sigint 를 수신하면 foreground 로 실행 중인 job 을 종료하는 문제입니다. myintp 의 소스 코드를 열어보면 다음과 같습니다. /* * myintp.c - Sends a SIGINT to its parent (the shell) * * A correctly written shell will echo the SIGINT back to the child. */ #include #include #include #include #include #include "config.h" void sigalrm_handler() { exit(0); } int main() { signal(SIGALRM, sigalrm_handler); alarm(JO..

Shell이란 무엇인지 알아봅시다. 쉘(Shell)은 사용자의 명령을 처리해 주는 응용 프로그램입니다. 다음의 그림으로 쉘과 유저, 쉘과 커널의 관계에 대해 이해해봅시다. 즉 쉘을 통해서, 유저는 커널에 명령을 내리고 커널은 수행결과를 쉘을 통해 유저에게 보여주게 되는 것입니다. 조금 더 거시적인 관점에서 설명하면 하드웨어 커널 쉘 유저의 형태로 서로 communicate하는 것입니다. Shell의 종류로는 sh - Original Unix Bourne Shell, csh - BSD UNIX C Shell, tcsh - Enhanced C Shell, bash - Bourne-Again Shell이 있습니다. 앞으로 설명에서 사용될 Shell은 Bash Shell입니다. 쉘에서 처리할 수 있는 명령어는 ..

문서 편집기나, 키보드에는 다음과 같이 오타가 났을 때 수정된 단어를 추천해주는 기능이 있습니다. 이렇게 오타를 정정해주기 위해선 어떤 단어와 "비슷한 (가까운) 단어" 를 정의할 수 있어야 합니다. 그렇다면 어떤 단어와 "비슷한" 단어는 어떻게 정의할 수 있을까요? 이와 관련된 문제가 바로 Edit Distance (편집 거리) 문제입니다. Edit Distance : 두 String 이 얼마나 가까운지 나타내는 척도. String S1 과 S2 간의 edit distance 는 S1 을 S2 로 만들 때 아래 3가지 type의 연산을 최소한 몇 번 수행하여 만들 수 있는가로 정의합니다. Insertion (삽입) : S1 에 Symbol 하나를 추가 (위치는 무관) ex. MONDT -> MONEDT..

Dynamic Programming 기법으로 해결할 수 있는 대표적인 문제인 LIS (Longest Increasing Subsequence) 문제입니다. 먼저 Subsequence 의 정의부터 알아보겠습니다. 길이 n인 Sequence (ordered list) S = a1, a2, ... , an 이 주어졌을 때, sequence S' = ai1, ai2, ..., aik 가 1

다이나믹 프로그래밍 (Dynamic Programming) 이란 재귀 (recursion)와 메모이제이션 (memoization) 을 사용하여 문제를 해결하는 기법입니다. memoization 은 recursive function 의 중간 결과를 저장하는 기법인데 말로 하면 와닿지 않으니 피보나치 수를 구하는 문제를 해결하며 다이나믹 프로그래밍과 메모이제이션에 대해 이해해보도록 하겠습니다. Fibonacci Number. 0을 포함한 자연수 n에 대해서 n-th Fibonacci Number Fn 은 다음과 같이 정의합니다. F0 = 0, F1 = 1 Fn = Fn-1 + Fn-2 (for n > 1) 얘를 들면 F5는 다음과 같습니다. 이제 재귀(Recursion)을 이용하여 Fibonnaci Numb..