📚 Journal
나만무 기획 준비
일요일이라 잠깐 기획 ppt 제작 (아직 아무것도 안 정해졌는데 그냥 제안용 정리)
피드백 (from 동기 A)
time police : 재미도 있을 것 같고 적당히 기술적 챌린지도 있고 좋은듯
sky island : 별로 와닿지 않음
idle backpack hero : 기획이 주인 장르라 별로
real-time pixel dungeon : 별다른 코멘트 x
heavy hammer knight : 액션 게임 만들기 어려움. 타격감 구현도 힘들고 상호작용 구현도 힘듦.
spaceship rts : rts는 그래픽 리소스 많이 필요하고 메모리 관리도 힘들긴 함
getting over it with 3d : 기술적으로 너무 간단함. 할 거면 멀티를 추가해야할듯.
etc 3 : 심리스 만들기 힘들 것 같음
피드백 (from 정글 게임랩 익명 B)
정글 게임랩 구경 가는 김에 피드백도 살짝 받아봤는데, 전체적인 코멘트를 주자면 '내 게임과 레퍼런스 삼은 게임과의 차별점이 무엇인가? 내 게임의 존재의의는 무엇인가?'를 고민해보면 좋을 것 같다고 하심. 정글은 취업을 위한 과정이니 재미보다는 우리가 무슨 기술적 챌린지를 구현하고 싶은가를 우선으로 두고 생각하는게 맞을 것 같다고도 하심.
time police : 데바데와 차별점이 무엇일까에 대해 생각해보면 좋을 것 같다
heavy hammer knight : 게임랩 누군가가 액션 게임 기획을 제안했는데 대차게 까였었다고 함. 타격감은 메카닉이지 게임 기획이 아니기 때문이었다고 함. (이건 그냥 썰 느낌)
spaceship rts : 컨셉이 비슷한 게임을 보여주셨음. 소행성대에서 자원 채취하고 함대 만드는, 굉장히 비슷한 게임이 이미 있긴 함.
getting over it with 3d : 역시 너무 구현이 너무 쉬울 것 같다는 이야기. 취업을 위한 과정이라면 멀티, 인벤토리, ai 등 기술적 챌린지가 있어야 한다.
📝 배운 것들
🏷️ dynamic programming
dp 문제 접근 방식
1. 큰 문제를 작은 문제로 표현할 수 있다
2. 어떤 문제를 점화식으로 표현할 수 있다
3. 캐싱은 쓸 수도 있고 안 쓸수도 있
모든 dp 문제는 Bottom-up과 Top-down이라는 2가지 방식으로 풀이될 수 있다.
Bottom-up : 데이터가 들어오는 순서대로 처리한다 (= 반복문)
Top-down : 패턴을 이용한다 (= 재귀 + 메모이제이션)
https://www.youtube.com/watch?v=0bqfTzpWySY
dp로 풀어야겠다고 판단할 수 있는 기준
1. DFS/BFS로 풀 수는 있지만 경우의 수가 너무 많은 문제
2. 경우의 수들에 중복적인 연산이 많은 문제
최악의 경우의 수 구하는 방법 : 처음 몇 개는 손으로 직접 세보고 패턴이 보이면 그 때 계산을 하기 위해 수학적인 식을 도출
혼자 생각해봐도 생각해내기 어려운 유형이니
30분 동안 머리 싸매고 해보다가 안되면 답지 보면서
dp식 사고 방법을 익혀야 한다
많은 문제를 풀어볼 것
여태까지의 최적의 답을 쌓아간다는 마인드로 프로그래밍
어떤 정보를 어떻게 쌓아야 연산 횟수를 가장 많이 줄일 수 있을까 고민
🖥️ PintOS
🔷 Virtual Memory
📌 Anonymous Page
Differences in `diff -u' format:
(args) begin
(args) argc = 5
(args) argv[0] = 'args-multiple'
(args) argv[1] = 'some'
(args) argv[2] = 'arguments'
(args) argv[3] = 'for'
(args) argv[4] = 'you!'
(args) argv[5] = null
(args) end
- args-multiple: exit(0)
+ : exit(0)어제 코드를 다시 돌려봤더니 갑자기 결과가 '거의' 정상적으로 나온다.
??? 어제는 분명 아예 안 돌고 패닉 떴는데?
저장을 제대로 안 하고 돌려서 그랬던 걸로 추측.
아무튼 vm_alloc_page_with_initializer()의 문제
if문을 두 개 쪼개서 하지 말고
삼항 연산자 (if-else 문 쓴 효과) 써서 로직 확실하게
메모리 누수도 일어나고 있었다고 함.
프로세스의 생애 주기를 따라 이름이 어디에서 누락되는지 확인해봄.
+ THREAD_CREATE :: NAME : args-single
+ INIT_THREAD :: THREAD'S NAME : args-single
+ PROCESS_EXEC :: F_NAME : args-single onearg
+ LOAD :: FILE : args-single(이거 잘하는 동기거 따라한 디버깅 코드 스타일인데,
// printf("PROCESS.C :: LOAD : command_line : %s\n", command_line);
파일 이름 빠뜨렸었음. 이것도 추가하는게 맞다. 없으니까 어디에 있는지 확인이 어려움.)
setup_stack도 바꿔 껴봤는데 안됨. (기존과 별 차이 없긴 했음)
근데 다른게 틀릴 일은 없을 것 같고
setup_stack이 인자 공간에 관한 함수니까
여길 봐야 되는데
여긴 이미 복붙 한데다 별 다를 것도 없었고
그렇다면 여기에 들어가는 vm_alloc_page랑 vm_calim_page를 점검해보자.
vm_alloc_page는 vm_alloc_page_with_initializer랑 똑같은데 인자만 미리 설정돼있는거고
그렇다면 vm_claim_page 네녀석이냐
vm_claim_page()
/* Claim the page that allocate on VA. */
bool vm_claim_page(void *va UNUSED)
{
struct page *page;
page->addr = va; // 빈 페이지에 찾으려는 페이지의 가상 주소 넣고
page = spt_find_page(&thread_current()->spt, va);
if (page == NULL)
return false;
return vm_do_claim_page(page); // 찾은 페이지 claim
}이전
bool vm_claim_page(void *va UNUSED)
{
/* TODO: Fill this function */
// printf("\n\nim claim page, addr : %p\n\n", va);
struct page *page = spt_find_page(&thread_current()->spt, va);
if (page == NULL)
return NULL;
return vm_do_claim_page(page);
}이후
이전에 완전 바보짓 했었네
페이지에 va 넣는 필요없는 짓 하고 있었다
아무튼 이거 바꿔줘도 그대로임
spt_find_page()
그렇다면 spt_find_page 너냐
정답이었다
/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
struct page *page;
page->va = pg_round_down(va);
struct hash_elem *e = hash_find(&spt->pages, &page->hash_elem);
return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL;
}이전
/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
/* TODO: Fill this function. */
struct page p;
struct hash_elem *e;
p.va = pg_round_down(va);
e = hash_find(&spt->pages, &p.hash_elem);
return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL;
}이후
포인터를 선언하고 malloc같은 걸로 초기화하지 않은 상태로 사용하니까 틀렸던 것.
malloc 해주면 동작은 한다.
물론 malloc을 쓰면 나중에 free를 하는게 귀찮으니까 답지 코드로 바꿔주면 될듯?
int main() {
int *p;
*p = 1;
printf("%d\n", *p);
return 0;
}분명 이거 나도 살짝 긴가민가해서 이걸로 테스트 해봤었는데 이건 됨.
왜 되는거지 하고 물어보니까
미정의 동작(undefined behavior):
C 언어에서 미정의 동작이 발생하는 경우, 프로그램이 예기치 않게 실행될 수 있습니다. 가끔은 프로그램이 정상적으로 동작하는 것처럼 보일 수 있지만, 이는 매우 불안정한 동작입니다.특히, 메모리 할당 없이 포인터를 사용하면, 해당 포인터가 어떤 메모리 주소를 가리키고 있는지 보장되지 않으며, 이로 인해 접근 불가한 메모리에 쓰기를 시도할 경우 세그멘테이션 오류(segmentation fault)가 발생할 수 있습니다.
라고 함.
드디어 테스트 통과 시작
나이스
근데 이제 뭐함?
📌 Stack Growth
프로젝트 2에서 스택은 USER_STACK 에서 시작하는 단일 페이지였으며, 프로그램은 이 크기(4KB)로 제한하여 실행했습니다. 이제 스택이 현재 크기를 초과하면 필요에 따라 추가 페이지를 할당합니다.
저번에 가졌던 의문이 해소됨, Project2 이전 프로그램은 4KB 이내가 맞았음.
왜 스택인지 아닌지만 판별해야되는건지 모르겠어서 gpt한테 질문
힙같은 거 접근해도 메모리 할당 새로 할당해야되는거 아님? 왜 스택에 접근하는거 아니면 페이지 안 늘려주는거임? 뭐 다른 세그먼트에 접근하는 건 안돼?
스택은 지역 변수와 함수 호출 스택을 저장하며, 이러한 저장이 동적으로 변할 수 있기 때문에 자동 확장이 필요합니다.
힙이나 데이터 세그먼트는 메모리가 명시적으로 관리되기 때문에, 자동 확장할 필요가 없습니다. 자동 확장이 필요한 경우라면, 프로그래머가 malloc()과 같은 함수를 사용하여 명시적으로 메모리를 요청해야 합니다.
다른 세그먼트(힙, 데이터 등)에 대한 접근 시, 그 영역은 이미 할당된 메모리 내에서만 접근이 허용되며, 할당되지 않은 메모리에 접근하면 페이지 폴트가 발생해 오류가 발생합니다.
깃북 읽어보니 여기서 원하는거
스택에 접근하는거면 추가 페이지(익명 페이지)를 할당해줘야 함.
스택에 접근하는게 아니면 언급은 없는 것 같은데 잘못된 접근이니까 프로세스 죽여버리면 될듯
⚔️ 백준
📌 1463 1로 만들기
실버3인데도 dp라서 도저히 모르겠어서 답지 봤더니
파이썬으로 시간안에 절대로 안될 것 같은 로직임.
??? 하고 봤더니
파이썬은 시간 더 주는거였음
(+ 최대 숫자가 1000000이라고 나와있었으면 약하다고 생각했을텐데
10^6이라고 나와 있으니까 강해보이기도 함)
접근 사고 방식 자체는 맞게 했던 것 같음
n = int(input())
# DP 테이블 초기화
d = [0] * 1000001
# 다이나믹 프로그래밍 진행(bottom-up)
for i in range(2, n+1):
# 현재의 수에서 1을 빼는 경우
d[i] = d[i-1] + 1
# 현재의 수가 2로 나누어 떨어지는 경우
if i%2 == 0:
d[i] = min(d[i], d[i//2] + 1)
# 현재의 수가 3으로 나누어 떨어지는 경우
if i%3 == 0:
d[i] = min(d[i], d[i//3] + 1)
# 결과 출력
print(d[n])↑ 정답 코드
내일 다시 해보자
