2시~ 3시 코어타임

G님은 3.3까지,
J님은 3.4를 읽으시고 3.5를 확인하심.

간단히 3.3까지 요점을 설명하고
3.4에서
J님이 확실히, 레지스터와 메모리의 이동,
메모리와 레지스터의 이동같은걸 이해하는 건 중요할 거같다고 하심.

맥에서 직접 어셈블리를 해보셨는데,
이상하게도 mov 뒤에 접미어로 데이터 크기가 붙지 않음.
또 레지스터를 명명하는 주소도 좀 달라서 다들 의아했다.

x86 기준의 책이라 그런게 아닌가? 라고 하자
x86식으로 컴파일한 어셈블리라고.

immediate와 레지스터의 이동에서
잠시 immediate가 뭔지 다들 고민하였는데
아마 상수값......자체의 이동이 아닌가 싶다.

또 뒤에 스택 데이터에 대해 언급하셨는데
C에는 스택이라는 개념이 없고, 구현을 하더라도
스택의 포인터? top 자체를
별개로 만들지 않고, int top으로 주어 그 값을 변환하는 식으로 쓰는 게 보편적인데 왜 이런 방법을 쓰는지 의문이셨다고 함.

그래서 내가 이건 어셈블리어를 설명하는 파트니,
mov를 하더라도 프로그램 스택,
단순히 데이터가 이동하는게 아니라 함수의 스택을 명시하기 위해
구분해서 명령어로 만든 게 아닌가 얘기함.

G님이 왜 레지스터가 여러 공간으로 나뉘어졌는지 궁금해하심.
그래서 내가 아마 연산마다 크기가 다른데
일단 연산을 처리할 때의 메모리를 배정해주어야하는데
작은 크기의 연산은 작은 메모리를 할당하는게 나으므로(메모리가 남으니까)
그에 따라 주소를 또 다르게 표기했고,
64bit, 32bit 등의 단위에 따라 다르다고 얘기함.

그리고 진행 중 궁금했던 점은
J님이 바이트 이동 인스트럭션 예제에 나온
$0x0011223344556677 부분에서
초기화된 부분에서 16진수인데 왜 숫자가 이렇게 나오는지..?
가짓수가 자릿수와 맞지 않은지? 하고 의문을 가지셨지만
기본이 되는 전제가 뭔지(아마 나의 .... 상식 부족으로 모르는 것같은데) 잘 모르겠어서 어려웠음.

아! 아마
64비트 정수라서 0,1 이진수로
64개까지 적어야하는데,

그에 대한 값을 표기를
0x 표기법, 16진수로 해서
0~F까지 16가지 값으로 각 자리 4비트를 나타내서
64비트라, 16자리를 쓰고,

0~F의 16가지 x 16자리 해서 16의 16승...?
의 경우의 수가 나오는 것 같다.(진짜?)

그 외에는 어셈블리 코드를 읽을 때 편하지 않을까 하고
얘기하는 식으로 함.

그리고 저녁에 각자 문제를 풀어보고
문제 풀이를 코어할 수 있지 않을까 얘기함.

앞으로는 토요일 낮 3.7, 월요일 낮 3.8 로
필수 챕터만 진행하기로 함.

7시? 8시~ 9시 코어 타임

9084 동전 문제.

동전의 종류와, 종류의 수를 제시하고,
목표 금액을 제시했을 때,

동전들을 써서
목표 금액에 도달할 수 있는 경우의 수
(즉, 2, 4로 4를 만든다면
2+2, 4로 2가지 경우가 나오니까 2.)

J님이 먼저 설명해주시고,
G님이 설명해주신 뒤,
내가 설명하다가,

서로 교차해서...어쩌고....

.......

J님이 처음 설명하신 건

위쪽 행을 [채워야하는 목표금액]
아래 열을 [넣는 동전의 종류]
로 2차원 배열을 만드셨다.

. 0 1 2 3 4 5 6 7 8 9
0
1
2
3
4

0자리는 계산을 위해 1을 채워넣고
(0이라는 자리 자체가,
그 값을 계산하겠다는 선언이라.)

1원, 을 넣을 때부터 순차적으로 계산해본다.

그렇게 넣어서,
1원만으로 만드는 경우의 수를 모두 채우면,

그 다음부터는 2원만으로 만드는 경우의 수에,
1원 만으로 만드는 경우의 수를 합한다...

...

. 0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1
2 1
3 1
4 1

아 자리 안 맞네 하

아무튼....

2원만으로 경우의 수를 만들때

2, 라는 금액을 만드는 경우의 수는
기존에 계산했던
(1 + 1) 경우에(경우의 수 1)
(2) 경우를 더해서(경우의 수 1)

총 경우의 수를 구한다(1 + 1 = 2)

...
이런 식으로 기존의 경우의 수에
새로운 경우의 수를 더해서 채워나간다.

수식은 이렇다.

백준 9084 | 동전 (다이나믹 프로그래밍) | 파이썬

import sys

input = sys.stdin.readline

#input을 받는 코드
t = int(input())
for _ in range(t):
    n = int(input())
    coins = list(map(int, input().split()))
    m = int(input())

    # memoization을 위한 리스트 선언
    d = [0] * (m + 1)
    d[0] = 1

	#현재 동전 종류 중에서 하나씩 동전을 뽑아서 비교할 건데,
    for coin in coins:
    	# 금액 m까지 확인할 거고.
        for i in range(m + 1):
			# 그 금액이 현재 보는 동전 값보다 크거나 같다면,
			if i >= coin:
            #새로운 최대 동전에는
            #그 빼고 남은 금액의 최적해에
            #더해서 새로 반환할 것이다.
                d[i] += d[i - coin]

    print(d[m])

결론적으로는
d[i]는..
동전을 새로 넣을 수 있을 때에만
경우의 수를 누적해서 쌓아나가는 식이다.

그래서 바로 옆 행의 값을 그대로 계승하지않고
위의 열의 값에서 계승하되, (동전을 넣었을 때만)
여태까지의 경우의 수를 누적해서 산출한다...

...
흠...

나는 대충 알겠는데
아니 잘 모를거같기도 하고

아 그거구나
현재 d[i]에 d[i-coin]을
더한 값...

그러니까 new + old
를 조건이 성공할 때만 반환하는....것인듯.

.....

G님은 규칙이랑 문제는 잘 알고 계셨는데,
규칙이 어째서 이렇게 되는지는 좀 헤매셨다.

그렇지만 멋지게...
내가 설명하고 진우님이 어떻게 되는거냐고 묻는동안

멋지게 이해하셨음...(그렇죠?)

진행하는 방식은 비슷했음...(풀이가 그게 그거라)

나는 솔루션을 안보고 내가 생각하는 조건문으로 만들어서
그걸 수식으로 했는데,

그냥 대충? 이렇게 하면?
안되는구나? 라는 느낌만 알았는데?

J님이 '재귀함수면 어떻게 돌아가는지 트리(정확한 단어가 있었던거같은데...구조인가? 스트럭쳐?)를 그릴 수 있어야한다.' 라고 하셔서

그려보느라 좀... 처음해봐서 애먹었고...

정말 조건을 아는거랑...
조건.....문을 세우는거랑
코드로 짜는 건 다르구나 싶었다...

내가 한 게 뭐였냐면

나는.... 역으로
10짜리를 채울때(2, 3, 5)로
5부터 채운다면
5 + [5] 라
5를 또 채우면 되는 거니까
5를 채우는 문제로 넘어가서
5 + [0]
5 + [2+3]
뭐 이런식으로.....

해서,

#큰 값부터 시작하니 리버스.
coin_list.reverse()

count = 0

def coin_is(n, count):
	#코인 리스트 전부를 보기위해 인덱스 생성.
    for i in range(1,n+1):
    # 근데 그 동전이 가장 작은 동전이라면(역순이니까)
        if i == n+1:
        #다른 동전 가짓수가 없으므로, 하나로 나눠진다면
            if m%coin_list[i-1] == 0:
            	# 경우의 수 +1
                count += 1
                return True
                # 큰 값에서 True인지 False인지 요구할때 쓰기 위한 값.
        
        # 만약 전체 금액에서 현재 코인을 뺀 값이, 현재 코인값보다 크다면
        if m-coin_list[i-1] > coin_list[i-1]:
        #그리고 그보다 작은 가짓수를 넣었을 때 그 값이 True로 존재한다고 돌아왔다면,
            if coin_is(n-1, count) is True:
            # 경우의 수 +1.
                count += 1
                # 후에 더 큰 값이 필요하다고 할까봐 True 리턴.
                return True
        
        #만약 전체 금액에서 현재 코인을 뺀 값이, 현재 코인값보다 작다면
        if m-coin_list[i-1] < coin_list[i-1]:
        	#이보다 작은 동전으로 나누었을 때
            #(근데 생각해보니 3, 2,1이 있으면 2로 되는 경우, 1로 되는 경우로 나뉘지 않나?
            싶기도 하고... 작으면 경우의 수를 올리는게 아니라 그냥 False 해야겠군.)
            if m-coin_list[i-1]%coin_list[i-2] == 0 :
                count += 1
                return True
    #아무튼 어떤 경우의 수도 반환하지 못 했다면, False.
    return False


coin_is(m, count)

print(count)

그렇지만 재귀 함수는

f(5)는 f(4)+f(3)으로 들어간다면
f(4)는 f(3)+f(2)로 들어가고
f(3)은 f(2)+f(1)로 들어간다든가

가장 작은 값에서 큰 값으로 올라오는걸 해야하고,
내가 한 방식으로 한다면

가장 높은 함수에서
가장 작은 함수까지 내려가는 걸 그릴 수 있어야했는데....

재귀 함수는 그렇게 파악한다는 걸?
알고 있었지만? 대충 감으로 썼지 실제로는?
해본적이 없었기에?
바로 그리자니 떨렸다....

그래서 잘 못그렸?던것 같다.

진짜 코드 내용이 아니더라도,
내가 이론적으로는 어떻게 생각했었는지 그려보고 싶다!

상향식? 대로 코드를 짜달라고 J님이
챗 지피티에게 부탁했더니 긴 코드가 나왔는데
출력값으로 돌아가는 걸 바로 파악하기가 쉽지 않았다.

그렇게 해매고 있는데
G님이 깨달으셨음...!
풀이의 의미를...!!

감동적....

아무튼 그렇게 한바탕 지나가고,
원래는 책과 문제 풀이 코어타임을...
아니 원래 하나만 하려했는데
책의 분량이 너무 많아서....

내일의 코어타임은
문제와 책 중에....
문제, 정석 문제인 knapsack문제와 LCS 문제를 보기로 했다!
책은 그래도 이해가 안 된다고 해서 다른 문제를
풀지 못하는 건 아니니까...!!

3.4, 3.7, 3.8만 코어타임에서 공유하고,
더 읽고 싶으면 각자 읽기로!

10시다....
.............