본 포스팅은 인프런 공룡책 강의를 기반으로 한 스터디 개인 정리를 위한 포스팅입니다. 잘못된 부분이 있다면 언제든 지적해주시면 감사하겠습니다! Concept 멀티 프로그래밍 된 운영체제에서 적용하는 개념 💡 멀티 프로그래밍이란? ⇒ 한 개의 프로세서가 하나의 프로세스를 수행하는 동안 다른 프로세스에 접근할 수 있도록 하는 방법 ⇒ 멀티 프로그래밍을 하려면 CPU의 처리속도가 빠르고 남는 시간이 있는 경우 Context Switching을 통해 다수의 프로세스를 접근할 수 있어야 함. 간단하게 설명해서 Ready Queue에 있는 프로세스들 중에 어떤 것을 Running Queue에 넣어 CPU할당을 시킬 것인지를 CPU Scheduling이라 함. 단순히 FIFO-Queue를 통해 먼저 큐에 들어온 프로..

본 포스팅은 인프런 공룡책 강의를 기반으로 한 스터디 개인 정리를 위한 포스팅입니다. 잘못된 부분이 있다면 언제든 지적해주시면 감사하겠습니다! Overview 메모리 상에 여러개의 프로세스가 적재되어있고 하나의 CPU가 Context Switch를 통해 작업이 수행되는 멀티 프로그래밍 구조를 배웠음. 하나의 프로세스가 여러개의 threads of control을 가질 수 있음. 프로세스(process)란? 프로세스(process)란 단순히 실행 중인 프로그램(program) 즉, 사용자가 작성한 프로그램이 운영체제에 의해 메모리 공간을 할당받아 실행 중인 것. 이러한 프로세스는 프로그램에 사용되는 데이터와 메모리 등의 자원 그리고 스레드로 구성. 스레드(thread)란? 스레드(thread)란 프로세스(..

본 포스팅은 인프런 공룡책 강의를 기반으로 한 스터디 개인 정리를 위한 포스팅입니다. 잘못된 부분이 있다면 언제든 지적해주시면 감사하겠습니다! Process 란? 프로그램 : 해당 프로그램이 하드디스크에 존재할 때를 의미 프로세스 : 해당 프로그램이 실행되어 메인메모리로 올라오게 되면, 그 프로그램을 프로세스라고 부름. Process 메모리 구조 Code 영역 실행할 프로그램의 코드가 저장됩니다. CPU는 이 영역에서 명령어를 하나씩 가져와 처리하게 됩니다. Data 영역 전역변수와 정적변수가 저장됩니다. 이 변수들은 프로그램이 시작될 때 할당되어 프로그램 종료 시 소멸됩니다. Stack 영역 지연변수, 매개변수, 리턴값 등 잠시 사용되었다가 사라지는 데이터를 저장하는 영역입니다. Heap 영역 동적 데..

문제 2294번: 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 풀이 다이나믹 프로그래밍으로 분류된 문제로 간단한 메모이제이션을 통해 풀이가 가능. 접근법 입력으로 주어진 동전으로 목표가치 K를 만드는 최소 개수를 구하는 문제로 DP문제인 만큼 Sub Problem을 찾으려 했음. Sub Problem : 각각의 동전으로 1원부터 목표(K)까지의 가치를 만들기위한 사용한 동전의 최소개수 부분 문제를 찾았으니 먼저 해야할 것은 부분 해를 저장할 dp배열을 선언하는 것...

Concept 그리디 알고리즘의 한 분류 다이나믹 프로그래밍 메모이제이션 기법 활용 부분 문제 : 한 정점까지의 최단거리는 방문하는 여러개의 정점들의 최단거리로 이루어져있음. 주어지는 그래프에서 시작 정점으로부터 각 정점까지의 최단경로를 찾는 알고리즘 Feature 우선순위 큐와 거리배열(DP)을 활용하여 로직 구성. 한 정점 V까지의 최단거리를 구할 때 V까지로 가는 여러 정점들의 최단 거리 정보를 활용한다는 특징을 가짐. 가중치를 가진 그래프에서 최단거리를 구할 때 쓰이는 알고리즘 음수 가중치를 가진 그래프에서는 사용불가. 우선순위 큐를 활용함으로써 시간복잡도 : O(N * NlogN) Implement 인접 리스트를 통한 구현 우선 데이크스트라 소스코드를 보자. private static int d..

Concept 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. 아래와 같은 수열이 있을 때 오름차순으로 정렬된 부분 수열은 1,3,5 1,3,4 3,5 1,2,4 등과 같이 존재하며, 해당 수열에서 최장 증가 부분 수열은 3 Feature 이러한 LIS의 길이를 구하는 방법 중 단순한 접근법은 Brute-Force방법으로 수열의 총 길이가 K라고 가정할 때 1개 이상의 원소를 가지는 모든 부분수열의 경우의 수는 2^K개로 모든 부분 수열의 오름차순 정렬을 확인하는 것은 시간이 매우 오래 걸린다. LIS의 길이를 구하는 최적 방법에는 2가지가 있다. 다이나믹 프로그..

문제 https://www.acmicpc.net/problem/20165 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 풀이 역시 구현+시뮬레이션 답게 장황한 문제의 지문에 조금 당황했지만.. 이해하고 나면 막상 수월하게 풀이가 가능했던 문제 해당 문제에서 핵심 로직 : 공격에 관한 상태배열 관리 입력의 방향은 Switch~case문으로 처리. 시작 좌표 큐에 추가. while문을 수행하면서 큐에서 꺼낸 좌표에 대해 로직 수행. 큐에서 꺼낸 좌표의 상태값이 0이라면(넘어져있는 경우) contin..

Concept 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제 Feature 배낭 문제에는 두 가지 유형이 존재 Fractional Knapsack : 물건을 쪼갤 수 있음. 무게나 가치가 소수점 단위로 나뉠 수 있는 문제. 0-1 Knapsack : 물건을 쪼갤 수 없음. 무게나 가치가 무조건 정수타입을 가지는 문제. Implement Brute-Force 가장 기본적인 풀이방법으로써 N개의 물건에 대해 가능할 수 있는 모든 조합을 만들어 보는 접근법. 시간복잡도는 O(2^N)으로 많이 느리다고 볼 수 있다. Dynamic Programming DP의 핵심은 메모이제이..