CS(76)
-
[CS] blocking, non-blocking, asynchronous I/O Model에 대한 나름의 이해
blocking은 동기, 무조건 return이 되어야 다음을 실행 non-blocking은 short polling 방식 클라이언트 쪽에서 다되었는지에 관한 요청을 원하는 답이 올때까지 보낸다. 얘의 단점은 여러 클라이언트가 동시에 많은 요청을 보내게 되면 서버 과부하가 생길 수 있다는 것이다. asynchronous는 long polling 방식 서버 쪽(OS)에서 다 되었으면 클라이언트 쪽(user application)으로 답(이벤트)을 보낸다. Reference http://asfirstalways.tistory.com/348 blocking, non-blocking and Async blocking, non-blocking and AsyncBlocking I/O Model일단 I/O작업은 Use..
2023.09.05 -
[CS] 장기 중기 단기 스케줄러에 대한 나름의 이해
장기: 메모리와 디스크 사이에서 스케줄링하며 어떤 프로세스를 메모리에 올릴지를 결정 (ready state가 됨) 중기: 메모리와 CPU 사이에서 스케줄링하며 어떤 프로세스를 CPU에 올릴지를 결정 (running state가 됨) 단기: 메모리와 디스크 사이에서 스케줄링하며 어떤 프로세스를 디스크로 내보낼지를 결정 (이런 state를 suspended state라고 함)
2023.09.03 -
[CS] 플로이드 워셜 이해 안되는 점
과연 시작되는 순서가 바뀐다고 해도 결과는 같을까? 결과적으로 for문의 순서를 바꿔도 같고 iteration 숫자를 바꿔도 같다. 왜 그런지는 잘 모르겠다. def floyd(): # k는 경유하는 노드 for i in range(1, NODE_CNT+1): for j in range(1, NODE_CNT+1): for k in range(1, NODE_CNT+1): # k노드를 경유하는 거리값이 더 작으면 갱신 graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) if __name__ == "__main__": NODE_CNT = 4 INF = 2147000000 graph = [[INF] * (NODE_CNT + 1) for _ in range(NO..
2023.08.23 -
[CS][X] 프림 알고리즘 시간 복잡도에 대한 이해
모든 간선(E)에 대해 최소힙을 하는 시간 O(logE)를 곱하면 O(ElogE)인데 이해가 잘안됨 다음에 해보겠다.
2023.08.20 -
[CS] 크루스칼 알고리즘 시간 복잡도에 대한 이해
E를 정렬하는데 걸리는 시간 O(ElogE), 그리고 E를 loop하며 union-find를 하는 시간 O(E) = O(ElogE + E) = O(ElogE)
2023.08.20 -
[CS] DFS, BFS의 O(V+E)에 대한 이해
인접리스트를 이용해 구현시 DFS, BFS 모두 O(V+E)의 시간복잡도를 가진다. 이는 다음과 같이 이해해볼 수 있다. V가 1억개 있고 E는 0 즉 간선이 하나도 없다고 생각해보자. 그러면 탐색하기 위해서는 V를 모두 돌며 결국 하나도 연결되지 않았다는 것을 알아야 할 것이다. 그래서 이 경우에는 O(V)가 될 것이다. 이번에는 V가 1억개 있고 서로 모두 연결 되어 있다고 생각해보자. 그러면 모든 간선에 대해서 확인하는 절차(이 노드가 이미 방문했던 노드라도 바로 그걸 '확인'해야 한다)가 들어가기 때문에 간선의 개수는 O(V+E)가 된다. 그런데 여기서 E는 V * (V-1)이므로 O(V)보다 훨씬 크게 된다. 그래서 O(E)가 된다. 결국 O(V+E)가 의미하는 것은 간선이 연결되어 있는 상황에..
2023.08.20