[CNU SW Academy] 16일차(22.12.22)

운영체제 - 김종익교수님

Process Synchronization

Producer - Consumer

Race condition

 

Solution to critical section problem

1. mutual exclusion(상호배제)

2. Progress

3. Bounded waiting

 

critical section handling in OS

1. Preemptive

2. Non-preemptive

 

mutex locks

busy waiting 문제 발생

 

semaphore usage

busy waiting을 해결하기 위해

block, wakeup 메소드를 활용

 

deadlock : 2개 혹은 이상의 프로세스가 하나의 자원을 들고 다른 자원을 기다릴 때 발생

starvation

 

readers - writers problem

읽는 경우에는 여러 명이 읽어도 상관없음

읽는 사람이 아무도 없는 경우 쓸 수 있도록

 

main memory

 

swapping

 

dynamic storage allocation problem

1. first fit

2. best fit

3. worst fit

의외로 worst fit이 성능이 좋다. 남기는 hole이 크기 때문에 다른 게 들어가기 좋다.

fragment(단편화)

1. external fragmentation

2. internal fragmentation

 

paging

---

프로그래머스 - 프론트엔드 미니 데브코스

백트래킹

모든 경우의 수를 탐색하는 알고리즘

DFS, BFS 이용 가능

탐색하지 않아도 되는 곳을 미리 막는 가지치기

 

JS는 재귀 효율이 나쁘기 때문에 DFS보다 스택을 이용하는 것이 좋다.

탐색에서 순환이 발생할 수 있다면 BFS를 이용하는 것이 편하다.

 

1. 모든 경우의 수를 찾을 수 있도록

2. 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머지는 탐색하지 않도록 조건문 작성

 

재귀로 구현한 N-QUEEN문제

function check(queen, row) {
  for (let i = 0; i < row; i += 1) {
      if (queen[i] === queen[row] || Math.abs(queen[i] - queen[row]) === row - i) {
          return false;
      }
  }
  return true;
}

function search(queen, row) {
  const n = queen.length;
  let count = 0;

  if (n === row) {
      return 1;
  }

  for (let col = 0; col < n; col += 1) {
      queen[row] = col;
      if (check(queen, row)) {
          count += search(queen, row + 1);
      }
  }
  return count;
}

function solution(n) {
  return search(Array.from({ length: n }, () => 0), 0);
}

 

동적계획법(DP)

메모리를 많이 사용하는 대신 빠른 성능을 자랑한다.

1. 메모이제이션

   하향식 접근법

   작은 문제들의 결과를 메모리에 저장해 필요할 때 꺼내 쓰는 

   필요할 때 계산(Lazy evaluaion)

2. 타뷸레이션

   상향식 접근법

   필요한 값들을 미리 계산해두는 것(Eager evaluation) 

 

동적계획법은 키워드만으로 동적 계획법 문제임을 알기 어렵다.

- 가장 작은 문제를 정의할 수 있는지

- 작은 문제를 통해 큰 문제를 해결할 수 있는 규칙이 있는지

 

단어 퍼즐

function solution(strs, t) {
    const dp = Array.from({ length: t.length + 1 }, () => 0);
    const strsSet = new Set(strs);

    for (let i = 1; i < t.length + 1; i += 1) {
        dp[i] = Infinity;
        for (let j = 1; j < Math.min(i + 1, 6); j += 1) {
            const start = i - j;
            const end = i;
            if (strsSet.has(t.slice(start, end))) {
                dp[i] = Math.min(dp[i], dp[i - j] + 1);
            }
        }
    }
    return dp[dp.length - 1] === Infinity ? -1 : dp[dp.length - 1];
}

---

웹서버 with Docker - 문현수박사님

1) 내 컴퓨터에서 띄운 nginx 서버에 접속해보기

2) 팀원 컴퓨터에서 띄운 nginx 서버를 내 컴퓨터에서 접속해보기

---

코딩테스트 - 집합 연산

A = set(map(int, input().split(" ")))
B = set(map(int, input().split(" ")))

u = list(set.union(A, B))
u.sort()
result = ""
for n in u:
    result += str(n) + " "
print(result)

i = list(set.intersection(A, B))
i.sort()
result = ""
for n in i:
    result += str(n) + " "
print(result)

d = list(set.difference(A, B))
d.sort()
result = ""
for n in d:
    result += str(n) + " "
print(result)

---

다 작성했는데 날아가서 다시 쓰느라 업로드가 늦었습니다...