전체 글
-
Multi Threaded ProgrammingCS/OS 2021. 2. 18. 18:59
2021/01/17 - [Study/OS] - Process & Thread (OS) Process & Thread (OS) 기본기의 중요성은 항상 느끼고 있는데요. 막상 제대로 알고 있는가 생각했을 때 그렇진 않은 것 같아 하나씩 정리합니다. Process 운영체제로부터 자원을 할당받은 작업의 단위 Thread 프로세스가 exponential-e.tistory.com 윗글에서 간략하게 다중 스레드 및 다중 프로세스에 대한 이야기를 다뤘습니다. 지난번 그림을 가져와 Multi-Threaded와 Single-Threaded를 표현해보면 아래와 같습니다. 공통점은 프로세스의 수, 차이점은 스레드의 수입니다. 그림에 나타난 표현으로만 봤을때 이야기입니다. 그리고 스레드의 수와 관계없이 Code, Data, H..
-
9 - 1. Dijkstra 예제 (Parity Constraint Shortest Path)CS/ProblemSolving 2021. 2. 1. 18:55
백준 20128번: Parity Constraint Shortest Path 20128번: Parity Constraint Shortest Path 첫째 줄부터 N개의 줄에 걸쳐, i번째 줄에 1번 정점에서 i번 정점으로 이동하는 최소의 홀수 경로의 비용과, 최소의 짝수 경로의 비용을 공백으로 구분하여 출력한다. 해당 경로가 존재하지 않는 www.acmicpc.net 풀고 나면 꽤나 쉬운 문제인데.. 방법을 적용하기 위해 증명을 생각하기 조금 어려웠던 문제입니다. 제목을 대충 해석하면 뭔 최단 경로입니다. ㅎㅎ 대략적인 문제 내용을 요약하자면 아래와 같습니다. 1번부터 N번까지 모든 노드의 최단 경로를 구하는 문제입니다. 임의의 두 노드 사이에 존재하는 간선은 단 하나 양방향 노드로 구성되며, 노드수: ..
-
Process State & SchedulingCS/OS 2021. 1. 31. 17:04
프로세스는 어떠한 상태(state)를 가집니다. Process State 멀티 태스킹 컴퓨터 시스템에서 프로세스는 다양한 상태를 차지할 수 있다. 각각의 상태는 OS 커널에서 인식되는 상태는 아닐 수 있으나, 프로세스를 이해하기 위한 추상적 개념이다. Process & Thread (OS) 기본기의 중요성은 항상 느끼고 있는데요. 막상 제대로 알고 있는가 생각했을 때 그렇진 않은 것 같아 하나씩 정리합니다. Process 운영체제로부터 자원을 할당받은 작업의 단위 Thread 프로세스가 exponential-e.tistory.com 지난번 포스팅에서 단일 프로세스와 멀티 프로세스 환경에 대해 말씀드렸습니다. 그 중 프로세스 상태에 대한 이야기도 살짝 했었는데요. 이번엔 프로세스 상태와 멀티 프로세스 환경..
-
10 - 1. Prefix Sum 예제 (11660: 구간 합 구하기 5)CS/ProblemSolving 2021. 1. 28. 19:21
백준 11660번: 구간 합 구하기5 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 구간 합 구하기, 제목만 봐도 Prefix Sum을 사용해야 할 것 같은 문제입니다. 아닌 경우도 있습니다. ㅎㅎ 그 중에서도 2차원 Prefix Sum 문제 입니다. 왜 Prefix로 풀어야하는 지는 아래와 같습니다. N은 최대 1024, M인 쿼리문은 최대 10만개까지 들어옵니다. 무식하고 돌리면 O (N * N * M) = 약 1000억, 따라서.. 일반 반복문으로 풀긴 어렵겠죠..
-
10. Prefix SumCS/Alogrithm 2021. 1. 28. 16:55
Prefix Sum, 유명하고 상당히 쉬운 측에 속하는 알고리즘입니다. 물론.. 알고리즘이라 부르기도 조금 민망할 정도로 간단한데.. 활용하기 좋은 방법이라 소개드립니다. Prefix Sum 누적합, 구간합이라 불리며 누적합 또는 구간합을 빠르게 구하는 알고리즘입니다. Prefix라는 단어를 사전에서 찾아보면 '접두사'라는 뜻을 갖습니다. 접두사라는 용어보다는 단어를 분해해 이해하는 것이 좀 더 와 닿습니다. pre- ~ 이전의, 미리 fix 고정시키다. 정하다. 즉, 미리 어떤 것을 고정시킨다. Sum, 합을 미리 고정시킨다로 받아들이시면 이해가 더 빠를 수도 있겠습니다. 어떻게 고정시키고 어떻게 활용할 것인지 알아봅시다. 우선, 어떤 수들의 합을 구하는 문제를 해결해 보겠습니다. arr = {0, 8..
-
9. Dijkstra (최단 경로 알고리즘)CS/Alogrithm 2021. 1. 26. 16:05
최단 경로 알고리즘 중 가장 많이, 자주 접할 수 있는 다익스트라 알고리즘에 대해 설명합니다. Dijkstra Alogrithm 그래프 내에서 꼭짓점간 최단 경로를 찾는 알고리즘이다. 알고리즘을 고안한 에츠허르 다익스트라의 이름을 따 다익스트라 알고리즘이라 불립니다. 일반적으론 하나의 노드에서 다른 하나의 노드까지의 최단 경로를 구하는 알고리즘입니다. 파생된 방식으로 1:1 탐색이 아닌, 1:N, N:1, N:M 탐색 방식이 있습니다. 기초는 1:1 방식이나, 하나의 노드에서 다른 모든 노드로 향하는 최단 경로를 찾아 트리를 구성하는 방식 또한 주로 쓰입니다. 사실 1:N 방법이 더 많이 쓰이긴 합니다. 우선 자주 쓰일 용어에 대해 살짝 짚고 넘어가겠습니다. V: Vertex를 의미합니다. Node, 꼭..
-
User Collaborative-Filtering (Cos Similarity)CS/Math 2021. 1. 25. 15:06
추천 시스템에 사용되는 Collaborative Filtering에 대해 정리합니다. 그중에서도 User Collaborative-Filtering에 중점을 뒀습니다. 최근에 출전한 공모전에서 적용해보려 알아본 것인데, 조건이 제한적이라 제대로 적용은 하지 못했습니다. 언젠간 추천 기능 구현을 위해 한 번쯤 고려해볼 만한 방법으로 정리하고 다시 공부해보기 위해 포스팅합니다. Collaborative-Filtering (협업 필터링) 많은 유저들의 취향이나 정보를 수집(Collaborative)함으로써 어떤 유저의 취향을 자동으로 예측(Filtering)하는 방법론이다. 즉, 비슷한 관심사를 가진 사람들을 매칭하고 이를 기반으로 추천하는 방식입니다. 좀 더 자세히 써보면, 어떤 사람 'A'가 임의의 주제 ..
-
Process & Thread (OS)CS/OS 2021. 1. 17. 18:06
기본기의 중요성은 항상 느끼고 있는데요. 막상 제대로 알고 있는가 생각했을 때 그렇진 않은 것 같아 하나씩 정리합니다. Process 운영체제로부터 자원을 할당받은 작업의 단위 Thread 프로세스가 할당받은 자원을 이용하는 실행 흐름의 단위 Program 파일이 저장되어 있지만 메모리에는 올라가 있지 않은 상태 간단하게 Process, Program의 차이부터 보면 아래와 같습니다. Process는 자원을 할당받아 메모리에 올라간 상태로 실행된 상태를 의미합니다. Program은 자원을 아직 할당받지 못한 Process가 되기 전의 상태로 이해하시면 됩니다. 즉, Program이 메모리에 적재되고 실행되면 Process가 됩니다. Process 특징 Code, Data, Stack, Heap으로 구성된..