mojo's Blog

문제 링크 => 3648번: 아이돌 (acmicpc.net) 3648번: 아이돌 각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다. www.acmicpc.net 2-SAT 문제이다. 각 심사위원은 자신이 행사한 두 표 중 적어도 하나는 결과에 영향을 미쳐야 한다고 생각을 한다. 두 표 모두와 반대되는 결과가 나오면, 심사위원은 투표 결과에 대해서 의심을 하게 된다. 즉, 두 표 모두와 반대되는 결과가 나오면 투표 결과에 대해서 의심을 하게 되는데 이를 방지해야 한다. 예를 들어서 심사위원 X 가 1번째 참가자(A) 에게 찬성, 2번째 참가자(B) 에게 반대를 던졌다고 하자. 그렇다면 f(A, B) = A ..

Hard Disk Drives Hard drive 의 특성을 이해해야 내부적으로 어떻게 돌아가는지에 대해 알 수 있다! Base Geometry hard drive를 옆에서 본 측면이다. platter가 3개 있고 platter 위아래 부분은 surface 이다. (density를 높이기 위해 아래에도 있음) arm이 왔다 갔다하고 위아래에 존재함 예를 들어 foo파일이 첫번째 platter에 있다면 6개의 Disk head가 병렬적으로 센싱하지 않는다. => 하나만 active 상태가 되서 파일을 찾아감 (controller가 다 잡을 수 없기 때문 + 충분히 빠른 이유) 이번엔 위에서 본 hard drive 이다. Arm이 왔다 갔다 하고 Sector가 512 byte로 존재한다. 읽거나 쓸 때 51..

Maximum Non-overlapping Intervals 이전에 Earliest finish first 방법이 가장 그럴듯 해 보인 방법임을 확인하였다. 따라서 이에 대한 알고리즘을 알아보도록 한다. Greedy algorithm Input : A = {a1, a2, ..., an} with ai = [si, fi] for 0 ≤ si S = S ∪ {aj}, k = j, aj를 담아주고 담아준 인덱스 j를 k에 넣어준다. (j..

Semantic Analysis: ● Syntax tree와 symbol table을 이용하여 소스 프로그램이 언어 정의에 의미적으로 (semantically) 일치하는지 검사 ● identifier가 프로그램 내의 수식과 문장에서 해당 언어의 type 규칙에 따라 올바르게 사용되고 있는지를 검사하는 data type checking 수행, 그 결과를 syntax tree 혹은 symbol table에 저장 의미 분석기(semantic analyzer)가 수행 ● 입력: ○ parsing으로 얻은 parse tree 또는 syntax tree ● 출력: ○ Semantic analysis가 이뤄진 parse tree 또는 syntax tree ○ Syntax directed translation을 이용하..

Integer partitioning 어떻게 해결해야 할지에 대한 접근법을 들어보자. 1. Greedy strategy 예를 들어 S = {4, 5, 6, 7, 8} 가 있을 때, Greedy strategy 로는 solution을 찾을 수 없다. 2. Dynamic programming To solve an instance of subset sum, need to calculate f(1, t). Note that f(j, t) = f(j + 1, t) or f(j + 1, t - xj). The boundary condition is f(l, t) = true if t = 0 or t = xl and false otherwise. The running time is propotional to the ..

Semaphore: A definition #include sem_t s; sem_init(&s, 0, 1); // initialize s to the value 1 int sem_wait(sem_t *s) { decrement the value of semaphore s by one wait if value of semaphore s is negative } int sem_post(sem_t *s) { increment the vlaue of semaphore s by one if there are one or more threads waiting, wake one } sem_t 에 대한 객체 s는 integer value 를 가지고 있으며 sem_wait(), sem_post() 으로 조작이 가능하다..