Backtracking 뜻 그대로 "가다가 막히면 왔던 길 다시 되돌아가기"이다 "Tries to construct a solution incrementally by a sequence of correct of best decisions" 단계를 하나하나씩 늘려가면서(incrementally) 우리가 원하는 결과에 대한 sequence를 생성해낸다 하지만 이 때 끝에 도달했는데 결과가 나오지않는다면 다시 "Backtracking"한다 어떠한 탐색이든지 root node가 존재할 것이고 이 root node로부터 Tree 형태로 탐색 범위를 확장시킬 것이다 여기서 이렇게 탐색을 이어나간다고 하자 결국 node로부터의 여러 child node가 존재하는데 "모든 갈림길을 평가 후 best node를 선택"하..

Divide-and-Conquer 1. 일단 자르기 : Divide 2. 자른 subProblem들에 대한 해답은 Recursion으로 : Conquer 3. Recursion으로부터 얻어진 결과들을 종합/정리 : Combine 1) Merge Sort 가장 기본적인 "Divide and Conquer" 기법을 사용하는 정렬 알고리즘이다 static void Merge_Sort(int [] list, int left, int right){ if(left < right){ int mid = (left + right) / 2; Merge_Sort(list, left, mid); Merge_Sort(list, mid + 1, right); Merge(list, left, mid, right); } } 1. D..

Local Search Algorithms 많은 "최적화 문제"에서는 Goal까지의 경로가 중요한게 아니라 Goal에 도달하는 그 자체가 중요하다 상태 공간 탐색의 경우 초기 상태 & 목표 상태가 주어지고 Action들의 Sequence에 의해서 Goal에 도달한다 지역 탐색의 경우 초기 상태만 주어지고 목표 상태는 모르는 상태에서 오직 현재 상태보다 더 나은 상태로 가려는 탐색 방식이다 그에 따른 제약조건이 굉장히 많지만 지역 탐색은 제약조건을 최대한 많이 만족할 수 있는 Goal을 찾는 것이 목표이다 >> 목표 상태까지의 Path는 관심 X / 오로지 목표 상태에 도달하는 그자체가 중요하다 특징 1) "상태 공간"이란 해당 공간안에 존재하는 state들이 모두 그들만의 value를 보유하고 있다 - ..

이전에 Critical Section 문제에 대한 해결책으로 "하드웨어적 프로세스 동기화"를 설명했다. 하드웨어 기반 해결책은 매우 복잡하고 응용 프로그래머가 쉽게 사용할 수가 없다. 이러한 문제를 위해 OS에서는 몇가지의 소프트웨어 도구들을 개발했다 Mutex Lock Semaphore Monitor 1. Mutex Lock mutex는 사실 "Mutual Exclusion"의 축약 형태이다. "Mutual Exclusion"이란 'Critical Section에는 오직 하나의 프로세스만 들어갈 수 있고 Critical Section에 이미 프로세스가 존재한다면 나머지 프로세스들은 Critical Section에 접근할 수 없다'라는 Critical Section 해결 조건 중 하나이다 Mutex Lo..

공개키 암호시스템 대칭키 암호시스템의 경우 Encrytpion & Decryption에서 사용되는 key가 동일한 암호시스템이다 하지만 공개키 암호시스템의 경우 Encryption & Decyption에서 사용되는 key가 서로 다른 암호 시스템이다 Encryption Key : Public Key Decryption Key : Private Key 공개키 암호시스템은 "Trap Door - One Way Function"를 기본으로 하고 있다 단방향 함수의 목적은 "한쪽 방향은 쉽게 계산되지만 역으로 계산하려면 굉장히 힘들다" 1850 X 3957 = 7320450 : 단순 계산이므로 쉽다 but 7320450 = A * B ?? 역으로 계산하게 되면 굉장히 힘든 계산이 된다 >> 따라서 역으로 계산 ..

협력적 프로세스는 시스템 내에서 실행 중인 다른 프로세스에게 영향을 주거나 영향을 미칠 수 있다. Shared Memory라는 개념이 존재하기 때문이다 만약 두 프로세스가 공유 데이터를 동시에 접근한다면?? 어떠한 과정에 의해서 데이터의 일관성을 해칠 수도 있다. Producer-Consumer Problem에 어떠한 조건들을 추가해보자 1. "count" 변수 설정 Producer는 생산할 때마다 count++ Consumer는 소비할 때마다 count-- 2. Producer-Consumer 사이의 공유 버퍼를 유한하게 만들기 ## Producer Code ## while(true){ while(count == BUFFER_SIZE){ /* can't produce */ } buffer[in] = n..

Informed Search (= Heuristic Search)"지식"을 사용해서 여러 갈림길 중 최적의 node를 효율적으로 탐색하는 방법Best-First SearchA* SearchIterative Deepening A* (IDA*) SearchNode를 펼쳐놓고 탐색하기 전에 해당 Node가 문제 해결에 있어서 얼마나 좋고 최적의 Node인지 판단해주는 평가함수 : f(n)을 사용→ 평가함수가 좋은 Node부터 ExpandingGreedy Best-First Search전체적인 환경에서 각 후보 node(아직 확장 X)들에 대한 우선순위? 특정 Integer값이 존재한다그리고 각 우선순위는 "지식"을 활용해서 평가를 한다평가 함수 f(n)은 여러 후보 node들을 평가해준다평가 방법은 각 nod..

Problem-Solving Agents 1. 어떤 Agent든 "Sensor"를 통해서 인식하는 정보들이 존재할 것이다 :: Percept 2. Percept 정보와 State(직전 상태) 정보를 결합(Update-State)함으로써 새로운 State를 정의한다 ※ Sequence(Sequence Of Action)가 없다면? Sequence가 없다는 의미는 현재 "계획"이 없다는 의미이다 >> 따라서 계획을 먼저 수립해야 한다 1) 현재 State로부터 먼저 Goal을 정한다 Goal은 1) Agent가 스스로 정할 수 있고, 2) 외부에서 Agent에게 정해줄 수 있다 2) 현재 State & Goal을 통해서 Problem을 formulate한다 (탐색 대상이 될 수 있는 Problem으로 만들기..

다중 프로그래밍의 목적은 "CPU를 항상 바쁘게 하자"이다. 반드시 여러 프로세스들 중 하나의 프로세스에게는 CPU가 할당되어야 하고, 해당 프로세스가 I/O 요청을 기다리면 "context switch"를 통해서 다른 프로세스에게 CPU를 할당해줘야 한다. >> 이 때 필요한 기술이 CPU 스케줄링이다. 프로세스의 실행은 CPU burst - I/O burst 사이를 교대로 왔다 갔다 하며 수행된다 마지막 CPU burst에는 또 다른 I/O burst가 뒤따르는 대신, 실행을 종료하기 위한 시스템 요청과 함께 끝난다 "CPU Bound Process"는 CPU burst time이 굉장히 긴 프로세스이고, I/O burst time은 굉장히 짧기 때문에 user와 interactive하지 않은 bat..

아래의 key, IV, Ciphertext를 통해서 plaintext 구하기 "각 값들은 Base64 인코딩되어 제공된다" ## key ## 8iE3bf1se6N76HGPP8S0Xw== ## IV ## cHml3oX848/0uBwDJtChOA== ## Ciphertext ## QDr9NZNG9Bgc3TTnfRuqjjzf/kVSYwbP7F9mR4GQZ/IneIh7HTc/xnwzEeVBc H3pPlIbLFySKZruedJc9X87CGNDJ1f2Dat8BR3Ypbei5Q42xc306/AkSuGsjfqb X9/ELxmdKn7MyvY/Jbc0v0AJHV6odgNzygKRRrFJcUIF/50= ## 암호화 모드 ## AES/CBC/PKCS5PADDING Base64 인코딩? Base64 Encoding이란 Bina..

"거의 모든 현재 OS는 한 프로세스가 다중 스레드를 포함하는 특성을 제공한다" 스레드? 프로세스는 현재 실행중인 프로그램들이다. 그러면 스레드는? "스레드는 CPU 이용의 기본 단위이다" , "프로세스 내부에서 실제로 작업을 수행하는 주체" ??? 동일한 일을 수행하는데 여러개의 프로세스를 통해서 수행하면 각 프로세스마다 별도의 주소공간이 생성됨에 따라 메모리가 낭비되고 자원을 관리해주는 OS의 입장에서도 굉장히 힘들 것이다. >> 그래서 동일한 일을 수행하는데 일단 프로세스는 하나만 생성해주고, 해당 프로세스안에 여러개의 스레드를 통해서 일을 나누어서 동시에 작업을 수행하면 더 효율적이다 하나의 프로세스 내에서 여러 개의 실행 흐름(단일 / 동시 / 병렬)을 두어서 작업을 효율적으로 처리 하나의 프로..

1) Max max(A[0, 1, 2, ....., n-1]) // "Base Case" if n = 1 return A[0] // 1. Divide mid T(n) = 2 X T(n/2) + c ▶ Recursion Tree 결국 "value of node"는 해당 node에서 재귀호출을 제외한 비재귀호출의 연산 수행 횟수이고, C번 호출하기 때문에 모든 노드의 value는 C가 된다 이러면 결국 max알고리즘의 수행 시간은 모든 노드의 value의 합으로 볼수있다 leaf노드를 보게되면 n/2k로 나와있고 이 값은 leaf노드이므로 1이 되어야 한다 리프노드의 개수는 2k이고, 리프노드의 개수는 leaf 노드의 비용이라고 판단할 수 있다 >> 따라서 max-알고리즘의 시간복잡도는 O(n)이라고 할 수..