[TIL][Krafton Jungle] 3주차 - (2) : Knapsack Problem / 컴퓨터 시스템 약간

오늘의 내용은 어제의 동적 프로그래밍 공부의 연장선인 Knapsack Problem에 대해 알아보고,

컴퓨터 시스템 정리를 간단히만 다뤄보겠다.

 

---

 

Knapsack Problem

 

배낭 문제라고도 하는 kapsack 문제는 정해진 무게 한도가 있는 배낭에다 물건을 담는데, 가치가 가장 높게 담는 경우를 찾는 문제이다.

 

이는 모든 경우를 다 셀 경우 특정 물건을 담는다 vs 안담는다로 하여 2의 n(물건의 수)승의 탐색이 걸린다.

 

따라서 이는 효율적인 탐색법이 필요한데

접근법은 다음과 같다.

 

1. 만약 물건의 무게가 배낭의 한도보다 크다면 continue,

2. 한도보다 작다면 2중 배열(dp)에 세로줄은 담은 물건의 수(i), 가로줄은 배낭의 한도무게(w)로 설정하여 선언한 뒤

그 배열안에 최대의 가치를 저장한다. (이때, 해당 로직에선 담는 물건은 따로 무게나 가치로 정렬할 필요가 없다.)

3. k번째 물건을 담을때는 다음과 같은 점화식을 이용하여 저장한다.

 ' dp[k][j] = max(dp[k-1][j] , 현재 k번째 물건의 가치 + dp[k-1][j-현재 k번째 물건의 무게] '

4. dp[모든물건의수][배낭의한도무게]를 출력하면 정답이 나온다.

 

 

이 과정은 정말 이해하기 난해하다.

일단 문제를 본 후 코드와 그림을 통해 설명해보겠다.

 

BaekJun - #12865 : 평범한 배낭 (Knapsack Problem)

 

일단 코드 꼬락서니를 보고 밑에 말을 이해하는게 더 좋을 듯 하다.

 

import copy
import sys

n,w = map(int,sys.stdin.readline().split())
#n : 물건의 개수 / w : 가방의 최대 무게 한도
dp = [[0 for _ in range(w+1)]for _ in range(n+1)]

# 배낭 문제에 각 1~w의 행에는 무게별로 가치의 최대값을 갱신
# 1~N 열에는 물건이 하나씩 들어가는 시간순이라고 생각하자
# 따라서 위의 행을 갱신하고 그 아래 행은 위의 행과 비교하면서 갱신된다.

for i in range(1,n+1):
    weight, cost = map(int,sys.stdin.readline().split())
    if i == 1: #첫번째 물건은 위의 행이 없으므로 이 물건의 무게에 따라 첫 줄의 최대 가치를 갱신 
        if weight>w: #물건의 무게가 가방의 최대 무게 한도보다 높으면 못넣으므로 0인 상태로 넘어감
            continue
        else:
            for j in range(weight,w+1): #이 물건의 weight보다 큰 기록에만 이 물건을 넣을 수 있으므로 weight이상부터 가치를 기록함.
                dp[i][j] = cost
    else:
        if weight>w: #윗행이 있는 조건에서 물건의 무게가 가방의 최대 무게 한도보다 높으면 이전 기록이 각 무게별로 최대 기록이므로 복사함
            dp[i] = copy.deepcopy(dp[i-1])
        else:
            for j in range(1,w+1):
                if weight > j:
                    dp[i][j] = dp[i-1][j] # 이 물건번째의 행에서 이 물건보다 낮은 무게의 행에는 이 물건을 넣지 못하므로 이전 값이 가치의 최대기록임
                else:
                    dp[i][j] = max(dp[i-1][j], cost + dp[i-1][j-weight])
                    #max 괄호의 오른쪽은 이 물건을 넣기 위해 weight만큼 배낭에서 덜어내고 넣으면서 올라가는 가치를 더한 수식임 , 왼쪽은 이 물건을 안넣었을 때 현재 무게의 최대 가치 기록임
                    #둘 중 더 높은걸 기록화 하는 코드

print(dp[n][w]) #모든 물건을 검사하고, 가방의 최대 무게 한도시에 기록된 값을 출력

 

내가 본 알고리즘 중에 제일 이해하기 까다로운 것 같아서, 주석을 길게 달아봤다.

 

로직은 각 물건을 행인 무게별로 넣을 수 있는지 없는지를 결정하고, 또 이전 최대 기록과 비교하면서 더 높은 가치를 갱신해주는 방식이다.

 

j는 dp의 행(w 무게)을 for문 순환하는 변수인데, '가방의 한도가 j일 때의 물건을 넣을 수 있는 최대 가치'라고 생각하면 된다.

특정 열은 그 열의 인덱스 i번째의 물건을 넣을지 말지 이전 최대 가치 기록과 비교해보며 기록해 나간다.

 

따라서 2중 배열의 작성 순은 편지쓰듯이 왼쪽에서 오른쪽으로, 위에서 아래쪽으로 기록해 나간다.

 

현재의 k번째 물건을 담기 전에 j만큼의 무게만큼 배낭이 담겼을 때,

가치의 최대 기록이 dp[k-1][j] 에 담겨있는 것인데,

 

그 최대 기록인 dp[k-1][j]에서 지금 k번째 물건의 무게만큼을 현재 가방에서 덜어냈을 때의 최대 가치(dp[k-1][j-현재 k번째 물건의 무게])랑 k번째 물건의 가치를 더한 값이, 지금 기록되어있는 dp[k-1][j]와 비교했을 때, 더 큰 값을 기록해 준다.

 

그림으로 이해해보자.

 

첫번째 물건은 무게가 6이므로 6이전의 행은 가치가 0이다.

하지만 6 이상의 무게를 넣을 수 있는 가방(말했지만 j줄은 'j만큼의 무게를 넣을 수 있을 때의 최대 가치'이다) 엔 최대 가치가 13이 된다.

 

그리고 두번째 물건을 넣을 때는 위에 기록된 최대 가치 판과 비교하며 넣을 지 말지를 정한다.

현재 물건의 무게는 4이므로 이전 물건이 기록된 6 이전엔 4를 넣는게 최대 가치이다.

 

하지만 j=6이 된다면 그때, 비교를 시작해야 한다.

만약 바로 위의 칸에 기록된 것이 6일때의 최대 기록이었는데,

여기서 지금 물건의 무게 만큼 덜어내고 현재 물건의 가치를 기록하는 것이 더 큰 값인지 판단하는 과정이다.

지금 상황에서는 위의 칸인 1번째 물건만 들어있을 때가 더 큰 가치를 가지므로 13을 기록한다.

 

그렇게 모든 칸을 기록해 나간다.

 

그림을 보면 dp[3][7] 일 때,

이전의 dp[2][7] (이 물건의 넣기 전까지 7의 한도 배낭에 넣을 수 있었던 최대 가치)보다 거기서 현재 물건의 무게만큼 덜어내고 덜어냈을 때의 가치와 현재 물건의 가치를 더한 값이 14로 더 크므로, 기록이 갱신된다.

 

그렇게 print(dp[4][7])을 통해 맨 마지막 행, 마지막 줄에 적힌 정답이 출력된다.

 

---

컴퓨터 시스템 정리

어제 진짜 빡 정리 해봤는데, 이러다가 이 책 다 못읽겠다 싶어서 진짜 이해 안되는 것만 혼잣말처럼 끄적여 보겠다.

---

 

유닉스 vs 리눅스, 뭔 차이인가?

 

유닉스와 리눅스, 이름도 비슷한데 둘다 운영체제라고 하는 것 같다. 근데 둘의 차이가 뭔지는 잘 모르겠다.

한번 알아보자.

 

유닉스(Unix)는 초기에 벨 연구소에서 개발된 운영체제인데, 상용 소프트웨어로 시작하여 유닉스와 관련된 여러가지 버전들이 생겨나면서 여러곳에서 사용하기 시작했다.

상용 유닉스 버전들, 그리고 오픈소스 유닉스 버전인 BSD(Berkeley Software Distribution) 등이 있다.

 

리눅스(Linux)는 리누스 토발즈 라는 사람이 만든 오픈 소스 운영체제 커널(운영체제가 아니라는 건 아님)이다.

리눅스 커널과 유닉스는 유사한 기능을 가지는데 그에 더해서 리눅스 배포판(우분투, 페도라, 센트OS 등)에서 제공되는 유틸리티, 라이브러리, 응용 프로그램도 같이 사용할 수 있다.

리눅스는 오픈소스라 무료로 사용하고, 여러 개발자들에 의해 지속적으로 개발되고 향상되고 있다.

 

둘다 각 독립적인 운영체제 이고, 리눅스는 유닉스와 호환성을 가지면서도 리눅스 커널의 리눅스 시스템의 핵심 부분이 되어 다양한 배포판이 만들어진다.

 

---

 

커널, 도대체 넌 뭐냐..?

 

커널은 운영체제 중 항상 메모리에 올라가 있는 운영체제의 핵심 부분으로서 하드웨어와 응용 프로그램 사이에서 인터페이스를 제공하고 컴퓨터 자원들을 관리하는 역할을 한다.

 

즉, 응용프로그램 수행에 필요한 인터페이스를 제공하고, 하드웨어 등의 리소스를 관리한다.

커널의 처음 기원은 유닉스를 상용화하고 싶어서 리누스 토발즈가 만든 리눅스 커널로 시작된다.

 

유닉스는 상용화된 모델이 아니어서 일반 대중들이 사용하기 힘들기 때문에 다양한 PC 하드웨어에서 동작할 수 있도록 하는 유동성 서비스의 무언가가 필요했다.

 

그래서 리누스 토발즈가 수많은 개개인들이 사용할 수 있도록 다양한 하드웨어 아키텍쳐를 지원하도록 설계했고, 이를 통해 여러 종류의 컴퓨터와 장치에서 사용할 수 있게 된 것이다.

 

오늘날에는 윈도우 운영체제의 윈도우 커널, MacOS 운영체제에는 또 그만의 터널을 개발자들이 만들어 놓아, 사람들이 편하게 사용하고 있다.

 

---

인스트럭션 집합 구조(ISA : Instruction Set Architecture)

링커까지 거쳐 프로세서가 직접적으로 이해하는 명령어 하나를 Instruction(인스트럭션) 이라고 하고,

C언어와 같은 프로그래머가 작성하는 코드는 처리 과정들을 거치면서 Instruction 집합으로 변한다.

 

이를 인스트럭션 집합 구조 라고 한다.

 

인스트럭션은 여러 종류가 있는데,

크게는 사칙연산과 논리연산, 메모리를 읽고 쓰는 명령, 프로그램의 실행 흐름을 제어하는 분기 및 호출 명령(if/goto/call/return) 등이 있다.

 

 

---

그리디(Greedy) 탐색법

그리디 알고리즘이란 최적의 값을 구해야 하는 상황에서 사용하는 근시안적인 방법론으로,

"각 단계에서 최적이라고 생각되는 것을 선택"해 나가는 방식으로 최종적인 해답에 도달하는 알고리즘이다.

 

주로 문제를 분할 가능한 문제들로 분할한 후, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다고 한다.

 

말은 이렇게 되있지만,

그리디 탐색 문제를 접해보면, 뭔가 정형화 되있는 공식이 있다는 생각은 들지 않았다.

 

직접 문제를 풀어봐야 이해가 되는 부분도 있고, 실제 문제상황을 잘 파악하고, 맹점을 빠르게 캐치하는 것이 중요하다고 생각된다.

 

예를 들어 가능한 많은 회의를 예약하고 싶은 문제에서는

서로 다른 시간에 시작하고 끝마치는 회의를 오름차순으로 정렬해서 하나씩 끼워넣되,

"더 빨리 끝마치는 회의"를 예약하는 것이 더 많은 회의를 예약할 수 있다는 것은 논리적으로 생각해 낼 수 있다.

이러한 맹점을 빠르게 캐치하는 것이 중요하다는 말이다.

 

그 맹점을 빨리 캐치하기 위해서는 특정 상황이 가장 이상적이고 정답에 가깝게 되는지 예시를 잘 적용해 보는 것이 중요하다고 생각됬다.

 

탐욕 선택 속성, 최적 부분 구조 등의 그리디의 주요 알고리즘 속성이 있지만, 따로 다루지는 않겠다.

 

문제를 많이 접해보고 문제 해결능력을 키우는 것이 그리디 탐색법의 제일 중요한 포인트라고 생각된다.

 

 

 

---

백준 문제를 풀며 알게 된 PyThon 문법 정리

 

- 정규식으로 문자 나누기

문제를 풀려고 하는데 입력이 '55-45+50' 로 들어올 때,

기호와 숫자를 각각 분리하여 리스트에 [55,'-',45,'+',50] 이렇게 저장하고 싶었다.

 

어떻게 하는가?

 

정규식을 사용한다 !

import re

input_string = '55-50+40'
tokens = re.findall(r'(\d+|[+-])', input_string)

# 추출된 숫자를 정수로 변환하여 저장
numbers = [int(token) if token.isdigit() else token for token in tokens]

print(numbers)  # 결과 출력: [55, '-', 50, '+', 40]

 

re.findall() 함수 안에 왼쪽 인자에 들어있는 이상한 문자들의 조합은 정규식이다.

정규식을 잘 뜯어보자

r'(정규식)' 이런 꼴인 것 같다.

그안에 '\d+' 는 여러개의 정수를 뜻한다

중간의 '|'는 논리연산의 or 을 뜻한다.

 마지막으로 대괄호안에는 인식받을 기호들을 넣는다.

최종적인 뜻은 정규식 여러개의 정수나 혹은 대괄호 안의 기호들을 하나씩 쪼개서 리스트화 하겠다 라는 뜻이다.