본문 바로가기
728x90

전체 글480

Knapsack Problem(배낭 문제) 오늘은 배낭 문제(Knapsack Problem, 냅색 프라블럼) 에 대해 배워보겠습니다. 배낭 문제는 조합 최적화의 유명한 문제 입니다. :도둑이 다른 가치와 다른 무게가 있는 보석을 훔치는데 넣을 수 있는 무게가 정해진 가방에 최대한 많이 넣는 문제입니다. 이 배낭문제는 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem) 과 짐을 쪼갤 수 없는 경우 0-1 배낭문제(0-1 Knapsack Problem) 라 부릅니다. 저희 분할 가능 배낭문제를 그리디 관점에서 살펴보도록 하겠습니다. (다항시간에 풀 수 있습니다. 0-1 배낭문제는 DP로 풀 수 있습니다.) 훔친 물건 중에 가치가 가장 높은 거 부터 넣습니다. 그리디는 쉽게 생각할 수 있지만 항상.. 2020. 6. 21.
운영체제5 CPU Scheduling 안녕하세요. 이번 챕터 5에서는 CPU Scheduling 에 대해 배워 볼거예요. 아래는 그전 포스팅 'Threads' 이니깐 참고해주세요ㅎㅎ https://com24everyday.tistory.com/161?category=1114126 운영체제4 Threads 이번 단원에서는 아래 목표를 가지고 공부를 할 것 입니다. 1. Thread의 개념 이해 2. APIs (Pthreads, Windows ,and Java thread libraries) 3. Thread의 기본적 특성 4. multithread programming 5. Window, Lin.. com24everyday.tistory.com CPU Scheduling 에 대한 다음과 같은 순서로 배울 겁니다. 1. Basic Concept.. 2020. 6. 21.
BOJ1018 체스판 다시 칠하기 C++ 사용언어 C++ 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각.. 2020. 6. 21.
하루를 시작하기 전 다짐#24 안녕하세요. 옆집 컴공생입니다. 일요일이네요. 어제 문득 자기 전에 시험 공부를 제대로 하지 않았다는 불안감이 엄습하더라구요. 허허...이제 시험 8일 남았는데 무서워지네요. 플젝도 다 끝내야하는데... 오늘 열심히 공부해 보겠습니다. 빡공!!! 오늘 할 일 1. 운영체제 마무리 및 복습 2. 보안 과목 복습 3, 알고리즘 공부 시작 4. 집가서 플젝 2020. 6. 21.
728x90