📚 Journal
내일이 발표고 오늘 사실상 끝나는 줄 알고 답지나 보면서
학습해보려고 했는데 갑자기 일정이 잘못 적혀있었다면서 핀토스가 하루 더 늘어났다.
🖥️ PintOS
🔷 Virtual Memory
처음부터 다 다시 점검
static struct frame *
vm_get_frame(void)
{
struct frame *frame = (struct frame *)malloc(sizeof(struct frame));
frame->kva = palloc_get_page(PAL_USER | PAL_ZERO);
if (frame->kva == NULL) // 나중에 스왑 아웃 처리로 바꿔야 함
PANIC("TO DO");
frame->page = NULL;
ASSERT(frame != NULL);
ASSERT(frame->page == NULL);
return frame;
}내 코드
static struct frame *
vm_get_frame(void)
{
struct frame *frame = NULL;
/* TODO: Fill this function. */
void *kva = palloc_get_page(PAL_USER); // user pool에서 새로운 physical page를 가져온다.
if (kva == NULL) // page 할당 실패 -> 나중에 swap_out 처리
PANIC("todo"); // OS를 중지시키고, 소스 파일명, 라인 번호, 함수명 등의 정보와 함께 사용자 지정 메시지를 출력
frame = malloc(sizeof(struct frame)); // 프레임 할당
frame->kva = kva; // 프레임 멤버 초기화
ASSERT(frame != NULL);
ASSERT(frame->page == NULL);
return frame;
}답지 코드
내 코드를 쓰면 터지진 않는데
답지 코드를 쓰면 Kernel PANIC at ../../vm/vm.c:209 in vm_get_frame(): assertion frame->page == NULL' failed. 이런 오류가 뜬다.
답지 코드가 잘못됨.
새로운 프레임을 할당하는 것이므로
frame->page = NULL로 초기화를 시켜줬어야 됨.
이제야 뭐가 통과가 되기 시작한다. (분명 참고한 블로그에는 여기까지하면 36개까지 남기고 통과돼요~ 라고 돼있었는데 왜 55개나 남은건지는 의문...)
project2도 아직 제대로 돌아가는거 맞나? 의심이 들어서 돌려봤더니 15개 fail.
올패스 코드 아예 처음 받았던 버전으로 돌아가봤는데 올패스가 되는 건 맞음.
(후에 다른 사람한테 물어보니 Project2 안 돌아가는거 생기는건 맞는듯)
내가 건드리는 과정에서 무언가를 터트렸던 것 같음.
이제까지 했던 깃 버전들 싹 다 밀어버리고 새로 시작하는게 나을듯.
다 밀고 다시 했는데 다 터짐
다른 브랜치 파서 할 걸 그랬나;
깃북 다시 열고 찬찬히 뭐 빠뜨렸나 확인
Differences in `diff -u' format:
- (args) begin
- (args) argc = 1
- (args) argv[0] = 'args-none'
- (args) argv[1] = null
- (args) end
- args-none: exit(0)
+ args-none: exit(-1)이것저것 고쳤는데 처음 보는 오류가 생겨남
exit(-1)을 검색하고 디버깅 문구들 앞뒤로 넣어서 확인해봤더니
exception.c에 있는 if(user)의 문제였음.
PF_U를 검색해봤는데 건드려주는거 아무것도 없음.
error_code도 검색해봤는데 어셈블리 파일까지 가버려서 일단 후퇴.
블로그 코드와 동기 코드가 다른 부분을 확인하는데
spt_find_page를 바꿔줬더니 살아남.
malloc 문제인줄 알았더니 va에 pg_round_down() 안해줘서였다.
저번에 이거 해야된다는거 알긴 했는데
깃북에 명시가 안돼있는 사항이라 까먹음
이것 때문에 마음 꺾여서 포기할뻔
아 근데 '아 그러면 55개 통과되는것도 정상인거구나'라고 생각했는데
동기가 fork 통과하면 30몇개 통과되는게 맞다고 함.
이번에는 42개로 줄어들긴 함.
37개까지 줄어듦
앞서나간 사람들이 집에 가려고 할 때 붙잡고 도와달라고 함.
문제점들이 이내 발견됨.
void check_address(void *addr)
{
struct thread *cur = thread_current();
if (addr == NULL || !(is_user_vaddr(addr)) || pml4_get_page(cur->pml4, addr) == NULL)
{
exit(-1);
}
}syscall.c의 pml4_get_page(cur->pml4, addr) 이 문제였다고 한다.
페이지 폴트를 일으키기도 전에 페이지를 얻어버리니까 그렇다고 함.
if (user)
exit(-1);여기의 if문에도 || not_present 조건을 추가해줘야 했다고 함.
깃북의 요구사항이 전부라는듯이 생각해버린게 패착.
안되면 바로바로 되는 사람한테 가서 물어봤어야 했는데
나 혼자 해보겠다고 끙끙댄 것도 패착.
디테일한 부분들 안 나오는 블로그 글들만 믿은 것도 패착.
⚔️ 백준
📌 3255 WINDOWS
N=int(input())
# 버튼을 가린다면 선행 버튼 정보를 해당 칸에 추가
# 창이 100개 뿐이니까 매번 순회해도 문제 x
# 버튼의 위치 : (왼위세, 우아가)
# 그래프를 만든 후에 탐색하며 삭제
# 창이 어떤 버튼을 가린다면,
# 해당 버튼에 지금 창의 버튼을 연결해준다.
clicked=set()
cnt_first=1
btn_graph=dict()
for _ in range(N):
# (왼위세,왼위가,우아세,우아가)
lur,luc,rdr,rdc = tuple(map(int,input().split()))
# 첫 버튼 기억해두기
if cnt_first==1:
first_btn=(lur,rdc)
cnt_first+=1
# 버튼들 순회하며 가리는지 안 가리는지 확인
for btn in btn_graph:
btn_r,btn_c = btn
if lur <= btn_r <= rdr and luc <= btn_c <= rdc:
btn_graph[(btn_r,btn_c)].append((lur,rdc))
btn_graph[(lur,rdc)] = []
# dfs로 순회하며 필요한 버튼들 다 눌러주기
stack=[]
stack.append(first_btn)
cnt=0
while stack:
cnt+=1
btn = stack.pop()
# 클릭 안 했었다면 클릭 예약
for btn_needed in btn_graph[btn]:
if btn_needed not in clicked:
clicked.add(btn_needed)
stack.append(btn_needed)
print(cnt)버튼 사이의 관계를 그래프로 만들어서
클릭한거 안 한거 저장해가면서 순회하며 클릭
1트에 성공
역시나 티어도 골드5
시간은 내가 제일 짧긴 함.
주석도 다 지워보니까 코드 길이도 심각하게 차이나진 않는데
n=int(input())
squares=[]
dp=[-1]*n
for _ in range(n):
r1,s1,r2,s2=map(int,input().split())
squares.append((r1,s1,r2,s2))
def dfs(node):
dp[node]=1
curr_r1,curr_s1,curr_r2,curr_s2=squares[node]
for i in range(node+1,n):
if dp[i]>0:
continue
next_r1,next_s1,next_r2,next_s2=squares[i]
if next_r1<=curr_r1<=next_r2 and next_s1<=curr_s2<=next_s2:
dfs(i)
dp[node]+=dp[i]
dfs(0)
print(dp[0])dp 풀이가 어떻게 푼 건지 조금 신경쓰임
# 입력으로 주어질 사각형의 개수
n = int(input())
# 각 사각형의 좌표 (r1, s1, r2, s2)를 저장할 리스트
squares = []
# dp 배열: 해당 노드에서 시작하여 도달할 수 있는 사각형의 개수를 저장 (-1로 초기화)
dp = [-1] * n
# n개의 사각형 좌표를 입력받아 squares 리스트에 저장
for _ in range(n):
r1, s1, r2, s2 = map(int, input().split())
squares.append((r1, s1, r2, s2))
# 깊이 우선 탐색(DFS) 함수
def dfs(node):
# 현재 노드에서 시작하여 도달 가능한 사각형 수를 1로 초기화 (자기 자신 포함)
dp[node] = 1
# 현재 노드의 사각형 좌표
curr_r1, curr_s1, curr_r2, curr_s2 = squares[node]
# 다음 노드(사각형)를 탐색
for i in range(node + 1, n):
# 이미 방문한 노드는 건너뜀 (dp[i]가 0보다 크면 이미 방문한 것)
if dp[i] > 0:
continue
# i번째 노드의 사각형 좌표
next_r1, next_s1, next_r2, next_s2 = squares[i]
# 현재 사각형이 다음 사각형에 포함될 경우에만 탐색 진행
# 즉, 현재 사각형의 좌표 (curr_r1, curr_s2)가 다음 사각형의 좌표 안에 포함되는지 확인
if next_r1 <= curr_r1 <= next_r2 and next_s1 <= curr_s2 <= next_s2:
# 다음 노드를 DFS로 재귀적으로 탐색
dfs(i)
# 현재 노드의 dp 값을 갱신 (다음 노드에서 도달할 수 있는 사각형들의 수를 더함)
dp[node] += dp[i]
# 첫 번째 사각형 (0번째 노드)에서부터 탐색 시작
dfs(0)
# 0번째 노드에서 시작하여 도달할 수 있는 사각형의 총 개수를 출력
print(dp[0])gpt한테 주석 달라고 하니까 대충 어떤 느낌인진 알 것 같음
근데 문제를 쪼개서 푸는 풀이가 아니라 조금 어려울듯
📌 14552 Mahjong
# 머리 : 같은 패 2개
# 몸통 : 연속 패 or 같은 패 3개
# 패가 4개면 머리도 몸통도 될 수 없음
# 36개 패 중 14개 모아서 (머리 1개, 몸통 4개) or (머리 7개)로 만들어야 함
# (머리 7개) : 같은 종류 머리 2개 있으면 안됨
# 패 13개가 있을 때 적당히 패 1개를 더 가져와서 패 14개로 완성하려고 함.
# 패 13개가 있고 남은 23개 중 어떤 패를 한 개 가져왔을 때,
# 그 패가 완성될 수 있다면 그 패는 "대기패"라고 함.
# 13개의 패가 있을 때 대기패를 찾기
# def check_head_body():
def check_ready(holding,result,w):
holding[w]+=1
# 머리 7개 체크
seven_head = True
for h in holding:
if holding[h] != 0 and holding[h] != 2:
seven_head = False
break
if seven_head:
result.add(w)
# 머리 1개, 몸통 4개 체크
# check_head_body()
holding[w]-=1
# waiting에 남은 숫자 중 하나 가져와서 판별
holding={i:0 for i in range(1,10)}
waiting={i:4 for i in range(1,10)}
temp=list(map(int,input().split()))
for t in temp:
holding[t]+=1
waiting[t]-=1
result=set()
for w in waiting:
if waiting[w]>0:
check_ready(holding,result,w)
print(result)일단 머리 7개인 경우에 대해선 체크하는 로직 완성
(머리 1개, 몸통 4개)일 경우에 대해 대기패를 판별하는 걸 어떻게 해야될지 모르겠음
백트래킹 해야되나?
무조건 높이 3개 몸통을 만들어 본다거나
무조건 연속 3개 몸통을 만든다거나 하는 로직은 불가능
모든 경우의 수를 만들어봐야됨
반례)
311이면 연속 3개 몸통을 만들어야 하고,
233이면 첫번째 거르고 두번째 숫자부터 높이 3개 몸통을 만들어야 한다.
def check_head_body(holding,result,idx,found_head):
Sum=0
for i in holding:
Sum+=holding[i]
if Sum == 0:
return True
for i in range(idx,10):
# 내가 머리가 돼볼게
if holding[i]==2 and not found_head:
holding[i]-=2
check_head_body(holding,result,i+1,True)
holding[i]+=2
# 내가 연속 3개 몸통이 돼볼게
if i<8 and holding[i]>0 and holding[i+1]>0 and holding[i+2]>0:
holding[i]-=1
holding[i+1]-=1
holding[i+2]-=1
check_head_body(holding,result,i+1,found_head)
holding[i]+=1
holding[i+1]+=1
holding[i+2]+=1
# 내가 높이 3개 몸통이 돼볼게
if holding[i]억지로 경우의 수 하드코딩 해보려고 했는데,
각 숫자들에 대해 머리와 몸통이 동시에 될 수 있는 경우에 대해 판별할 수 없는 로직이었음.
백트래킹으론 경우의 수를 죄다 나눠줘야 하니 근본적인 한계가 있을지도?
def check_head_body(holding,result,idx,found_head):
Sum=0
for i in holding:
Sum+=holding[i]
if Sum == 0:
return True
for i in range(idx,10):
# 1개면 (연속 3개)의 일원이 될 수 있음
# 2개면 (연속 3개)x2 혹은 머리가 될 수 있음
# 3개면 (높이 3개) 혹은 (연속 3개)+(머리)가 될 수 있음
# 4개면 (연속 3개)x2+(머리)가 될 수 있음일단 경우의 수를 나눠보긴 했는데... 5개는 에바. 좀 더 효율적인 방식이 있을거임.
짱구 굴려봐도 안됨. 일단 이대로 풀어보자.
for i in range(idx,10):
# 1개면 (연속 3개)의 일원이 될 수 있음
if i<8 and hold[i]==1 and hold[i+1]>0 and hold[i+2]>0:
hold[i],hold[i+1],hold[i+2]=hold[i]-1,hold[i+1]-1,hold[i+2]-1
if check_head_body(hold,result,idx+1,found_head): return True
hold[i],hold[i+1],hold[i+2]=hold[i]+1,hold[i+1]+1,hold[i+2]+1
# 2개면 (연속 3개)x2 혹은 머리가 될 수 있음
if hold[i]==2 and not found_head:
hold[i]-=2
if check_head_body(hold,result,idx+1,True): return True
hold[i]+=2
if i<8 and hold[i]==2 and hold[i+1]>1 and hold[i+2]>1:
hold[i],hold[i+1],hold[i+2]=hold[i]-2,hold[i+1]-2,hold[i+2]-2
if check_head_body(hold,result,idx+1,found_head): return True
hold[i],hold[i+1],hold[i+2]=hold[i]+2,hold[i+1]+2,hold[i+2]+2
# 3개면 (높이 3개) 혹은 (연속 3개)+(머리)가 될 수 있음
if hold[i]==3:
hold[i]-=3
if check_head_body(hold,result,idx+1,True): return True
hold[i]+=3
if i<8 and hold[i]==3 and hold[i+1]>0 and hold[i+2]>0 and not found_head:
hold[i],hold[i+1],hold[i+2]=hold[i]-3,hold[i+1]-1,hold[i+2]-1
if check_head_body(hold,result,idx+1,True): return True
hold[i],hold[i+1],hold[i+2]=hold[i]+3,hold[i+1]+1,hold[i+2]+1
# 4개면 (연속 3개)x2+(머리)가 될 수 있음
if hold[i]==4 and hold[i+1]>1 and hold[i+2]>1:
hold[i],hold[i+1],hold[i+2]=hold[i]-4,hold[i+1]-2,hold[i+2]-2
if check_head_body(hold,result,idx+1,found_head): return True
hold[i],hold[i+1],hold[i+2]=hold[i]+4,hold[i+1]+2,hold[i+2]+2근성으로 어떻게든 해봤는데 예제 다 틀림...
# 머리 : 같은 패 2개
# 몸통 : 연속 패 or 같은 패 3개
# 패가 4개면 머리도 몸통도 될 수 없음
# 36개 패 중 14개 모아서 (머리 1개, 몸통 4개) or (머리 7개)로 만들어야 함
# (머리 7개) : 같은 종류 머리 2개 있으면 안됨
# 패 13개가 있을 때 적당히 패 1개를 더 가져와서 패 14개로 완성하려고 함.
# 패 13개가 있고 남은 23개 중 어떤 패를 한 개 가져왔을 때,
# 그 패가 완성될 수 있다면 그 패는 "대기패"라고 함.
# 13개의 패가 있을 때 대기패를 찾기
def check_head_body(hold,result,idx,found_head):
Sum=0
for i in hold:
Sum+=hold[i]
if Sum == 0:
return True
made=False
for i in range(idx,10):
# 1개면 (연속 3개)의 일원이 될 수 있음
if i<8 and hold[i]==1 and hold[i+1]>0 and hold[i+2]>0:
hold[i],hold[i+1],hold[i+2]=hold[i]-1,hold[i+1]-1,hold[i+2]-1
if check_head_body(hold,result,i+1,found_head): made=True
hold[i],hold[i+1],hold[i+2]=hold[i]+1,hold[i+1]+1,hold[i+2]+1
# 2개면 (연속 3개)x2 혹은 머리가 될 수 있음
if hold[i]==2 and not found_head:
hold[i]-=2
if check_head_body(hold,result,i+1,True): made=True
hold[i]+=2
if i<8 and hold[i]==2 and hold[i+1]>1 and hold[i+2]>1:
hold[i],hold[i+1],hold[i+2]=hold[i]-2,hold[i+1]-2,hold[i+2]-2
if check_head_body(hold,result,i+1,found_head): made=True
hold[i],hold[i+1],hold[i+2]=hold[i]+2,hold[i+1]+2,hold[i+2]+2
# 3개면 (높이 3개) 혹은 (연속 3개)+(머리)가 될 수 있음
if hold[i]==3:
hold[i]-=3
if check_head_body(hold,result,i+1,found_head): made=True
hold[i]+=3
if i<8 and hold[i]==3 and hold[i+1]>0 and hold[i+2]>0 and not found_head:
hold[i],hold[i+1],hold[i+2]=hold[i]-3,hold[i+1]-1,hold[i+2]-1
if check_head_body(hold,result,i+1,True): made=True
hold[i],hold[i+1],hold[i+2]=hold[i]+3,hold[i+1]+1,hold[i+2]+1
# 4개면 (연속 3개)x2+(머리) 혹은 (연속 3개)+(높이 3개)가 될 수 있음
if i<8 and hold[i]==4 and hold[i+1]>1 and hold[i+2]>1 and not found_head:
hold[i],hold[i+1],hold[i+2]=hold[i]-4,hold[i+1]-2,hold[i+2]-2
if check_head_body(hold,result,i+1,True): made=True
hold[i],hold[i+1],hold[i+2]=hold[i]+4,hold[i+1]+2,hold[i+2]+2
if i<8 and hold[i]==4 and hold[i+1]>0 and hold[i+2]>0:
hold[i],hold[i+1],hold[i+2]=hold[i]-4,hold[i+1]-1,hold[i+2]-1
if check_head_body(hold,result,i+1,found_head): made=True
hold[i],hold[i+1],hold[i+2]=hold[i]+4,hold[i+1]+1,hold[i+2]+1
return made
def check_ready(holding,result,w):
holding[w]+=1
# 머리 7개 체크
seven_head = True
for h in holding:
if holding[h] != 0 and holding[h] != 2:
seven_head = False
break
if seven_head:
result.add(w)
# 머리 1개, 몸통 4개 체크
if check_head_body(holding,result,1,False):
result.add(w)
holding[w]-=1
# waiting에 남은 숫자 중 하나 가져와서 판별
holding={i:0 for i in range(1,10)}
waiting={i:4 for i in range(1,10)}
temp=list(map(int,input().split()))
for t in temp:
holding[t]+=1
waiting[t]-=1
result=set()
for w in waiting:
if waiting[w]>0:
check_ready(holding,result,w)
result=list(result)
result.sort()
if result:
for r in result:
print(r,end=' ')
else:
print(-1)맞춰내기야 맞춰냈다.
머리를 고정시키면 까지는 알겠는데
연속된 패들을 몸통으로 먼저 하고 3개인 패들을 몸통으로 쓰기 or 순서 반대로 이건 뭔 소리지?
import sys
# 대기패 추가된 카드 리스트, 머리 수, 몸통 수, 현재 카드번호 인자로 받기
def check_card(card_2, head, body, num):
# 머리 1 몸통 4 완성이라면 return
if head == 1 and body == 4:
return True
# 패 복사해주기
card_3 = card_2[:]
# 1부터 시작
while num < 10:
# 패 가지고 있다면 확인 시작
if card_3[num] > 0:
# 가지고 있는 카드 3개이고 몸통이 4개가 안된다면 몸통으로 넣고 확인
if card_3[num] == 3 and body < 4:
card_3[num] -= 3
flag = check_card(card_3, head, body+1, num)
# 된다면 바로 종료
if flag:
return True
# 안되면 원상복구
card_3[num] += 3
# 가지고 있는 카드 2개이상이고 머리가 없다면 머리로 넣고 확인
if card_3[num] >= 2 and not head:
card_3[num] -= 2
flag = check_card(card_3, head+1, body, num)
if flag:
return True
card_3[num] += 2
# 연속된 세 숫자 있으면 몸통에 넣고 확인
if num < 8 and card_3[num+1] and card_3[num+2]:
card_3[num] -= 1
card_3[num+1] -=1
card_3[num+2] -=1
flag = check_card(card_3, head, body+1, num)
if flag:
return True
# 위 조건 모두 안된다면 남는패가 있으므로 불가능 선언
return False
else:
num += 1
#카드 받아 준 후 기록해주기
info = [*map(int, input().split())]
card = [0] * 10
for i in info:
card[i] += 1
# 머리 7개 되는 경우 확인
result = []
# 4장이 이미 사용되었다면 넘어간다.
for i in range(1,10):
if card[i] == 4:
continue
# 대기패 돌아가며 추가해줄 리스트
card_2 = card[:]
card_2[i] += 1
head_7 = 0
# 대기패 하나씩 넣어주며 2개라면 +1 해준다
for j in range(1, 10):
if card_2[j] == 2:
head_7 += 1
# 머리 7개가 된다면 결과에 넣어주고 다음 패 확인
if head_7 == 7:
result.append(i)
# 아니라면 몸통 4, 머리 1의 경우가 되는지 확인
elif check_card(card_2,0,0,1):
result.append(i)
if result:
print(*result)
else:
print(-1)복잡하게 다시 복원시키는게 아니라
쿨하게 복사시켜버리면 간단했다.
어째서인지 메모리 사용량도 똑같.
복사하는 방법 : arr = arr_old[:]
