정글에서 온 개발자

list_begin VS list_front list_begin /* Returns the beginning of LIST. */ struct list_elem * list_begin (struct list *list) { ASSERT (list != NULL); return list->head.next; } list_front /* Returns the front element in LIST. Undefined behavior if LIST is empty. */ struct list_elem * list_front (struct list *list) { ASSERT (!list_empty (list)); return list->head.next; } 차이 list_begin은 초기화 여부(list_i..

배경 대부분의 PintOS 자료에서 sleep_list를 매번 순회하지 않기 위해서 next_tick_to_awake(이하 ‘글로벌 틱’)라는 전역변수를 하나 더 지정하여 sleep_list의 tick 최소 값을 표시하도록 한다.[Explicit] 이를 위해서는, sleep_list 전체 순회(thread_awake)를 할 때마다 ‘글로벌 틱’을 갱신한다. 전체 순회를 조금이라도 줄이기 위해서는 sleep_list에 넣을 때부터 깨야 하는 tick의 오름차순으로 정렬되게 삽입하여, 순회 중 깨우지 못하는 쓰레드를 만나면 순회를 중단시킬 수 있다. 이를 좀 더 생각해보면, sleep_list의 첫번째 요소는 항상 ‘글로벌 틱’이므로 get_next_tick_to_awake가 이를 활용하게 작성할 수도 있다..

문제링크 접근 재귀 재귀라고 써있기도 하고, 구조 자체가 큰 Z 안에 작은 Z가 들어가서 재귀로 접근하기로 함 색종이 자르기 등 다른 재귀와 유사함 재귀 함수 인자로 범위를 나타내는 인자를 주고, 안쪽 재귀에서는 범위를 줄여가면 될 듯 베이스 케이스는 범위가 좁아져서 최종 1일 때 범위는 가로, 세로가 같이 줄어드므로 둘 중에 하나만 검사하면 됨 수학적 계산 R,C가 있는 위치를 기준으로 앞쪽의 구역의 숫자 배치는 상관이 없고 맨 오른쪽 아래 귀퉁이 숫자만 중요함 각 범위별로 시작하는 숫자도 정해져 있음 결국에는 재귀적으로 범위를 줄여나가는 것이 편함 트라이 1. 재귀, 시뮬레이션 N,R,C = map(int, input().split()) M = [[0]*(2**N) for _ in range(2**N..

이런 문법 처음 보는 분 보세요 *a,=map(int,input.split()) Starred Expression(Star Unpacking) a=[1,2,3] b=[4,*a,5] # b=[4,1,2,3,5] 단독으로는 사용될 수 없다. 컨텍스트 안에서 써야 한다. (함수 호출, 리스트 생성 등) 동일한 변수 내에서 여러번 쓸 수 없다. 함수 인자의 언패킹 def func(a,b,c): return a+b+c values = [1,2,3] result = func(*values) list(*map) , print(*str) 도 이렇게 인자를 언패킹해 넘겨주는 것이였다. Extended Unpacking(리스트나 튜플 , 맵 등) 언패킹시 일부 원소들은 별도로 할당하고, 나머지는 다른 변수에 할당 firs..

“프로그래밍” 은 테이블을 이용한 방법을 뜻한다. (컴퓨터와 관련이 없다.) 부분 문제의 해를 결합해 문제를 해결한다. 일반적으로 **최적화 문제(optimization problem)**에 적용한다. 최적화 문제 해와 값을 구분하자 문제의 풀이를 “해(Solution)” 라 한다. 그 풀이가 낸 답을 “값(Value)” 라 한다. 최적해는 각 해의 값 중 최적의 값을 내는 해이다. 최적의 값은 하나이지만 그 값을 내는 해는 여러개이다. 최단 거리(값)를 크루스칼, 프림 등 여러 방법(해)으로 풀 수 있다. 즉 최적화 문제는 여러개의 해를 가진다. 분할정복과의 비교 분할 정복은 서로 겹치지 않는(disjoint) 문제를 부분 문제로 분할한다. DP는 부분문제가 서로 중복될 때(부분 문제끼리 부분문제를 공..

알고리즘을 풀다 보면 알고리즘의 유형을 정리하고 싶을 때가 많다. 이 문제를 어떤 알고리즘으로 풀면 좋을지, 내가 쓰고 싶은 알고리즘(동적 프로그래밍, 그리디)로 풀 수는 있는지, 아니면 아예 풀 수 없는 문제인지 그런 문제 분류를 좀 더 큰 그림에서 연구하는 학문을 계산 복잡도 이론이라 한다. 계산 복잡도 이론 각 문제를 해결하는 얼마나 빠른 알고리즘이 존재하는지를 기준으로 문제를 분류하고, 각 분류의 특성을 연구하는 학문이다. 여기서 말하는 복잡도는 시간 복잡도랑은 조금 다르다. 시간 복잡도는 알고리즘의 특성이다. 계산 복잡도는 해당 문제 특성이다.(문제를 풀 수 있는 빠른 알고리즘의 시간복잡도) 어려운 문제, 쉬운 문제 다항시간에 풀 수 있는 문제는 “쉽다”고 하고, 다항시간 알고리즘은 “빠르다” ..

이진 탐색 트리(BST; Binary Search Tree) 이진 트리 : 각 노드가 왼쪽, 오른쪽. 최대 두개의 자식 노드만 가질 수 있는 트리 왼쪽 가지를 따라 내려가면 더 작은 수 오른쪽 가지를 따라 내려가면 더 큰 수를 만남 이진 검색트리를 중위 순회하면 크기 순서로 정렬된 원소를 얻을 수 있다. 정렬된 배열의 특징 루트부터 왼쪽으로 쭉 내려가면 최소 값이 나온다. 루트부터 오른쪽으로 쭉 내려가면 최대값이 나온다. 루트가 배열의 중앙값은 아니다(트리가 불균형하게 생길수도 있다.) 이걸 원하면 다른 트리 써야 함 부모 노드가 항상 나보다 한 등수 높은 것도 아니다. (오른쪽 리프를 생각해보자) 정렬된 배열보다 뛰어난 점 특정 원소가 존재 하는지 빠르게 확인할 수 있다 노드의 값을 기준으로 다음 검색..

계층 관계를 갖는 객체를 표현하기 위해 만들어진 자료구조 계층 관계가 없는 자료를 트리로 표현해서 같은 연산을 빠르게 할 수 있는 경우가 많다. 용어. 개념 정리 노드(node)와 간선(edge)로 이루어져 있다. 노드 간에는 상/하위 관계가 있다. 두 노드가 연결되었을 때는 한쪽이 상위, 다른쪽이 하위여야 한다. 상위는 부모(parent), 하위는 자식(child), 부모가 같은 노드는 형제(sibling) 부모와 부모들은 선조(ancestor), 자식과 그 자식들은 자손(descendant) 자식은 여러개 가질 수 있어도 부모는 하나만 가질 수 있다. 가장 윗쪽 노드는 **루트(**root;뿌리) 자식이 하나도 없는 노트는 리프(leaf;잎) 깊이(depth) :루트에서 어떤 노드에 도달하기 위해 거..

객체들의 상호 관계를 표현하기 위해 고안된 자료 구조 계층 관계만을 표현하는 트리에 비해 훨씬 다양한 현실 세계의 문제 표현 개요 그래프 표현 인접 행렬 표현 - 모든 정점의 관계를 표현. 밀집 그래프에서 유리 인접 리스트 표현 - 그래프 간 간선의 관계만 표현. 희소 그래프에서 유리 암시적 그래프 표현 ex) 좌표 표현 - 연결관계가 암시적(바로 옆의 좌표)으로 표현됨 문제가 비교적 단순한 경우 . 그래프 표현이 번거로워 사용 그래프가 아주 큰데, 일부만 사용(정점을 모두 그리지 않음) 단점. 그래프를 사용하는 알고리즘과 변환과정이 합쳐짐 → 코드가 복잡해짐 깊이 우선 탐색(DFS) 대표적 그래프 알고리즘. 재귀 사용 내부적으로 스택이 됨. 너비 우선 탐색(BFS) 가중치가 없는 그래프에서 두 점 사이..

현재 방법이 맥에서는 되고, 윈도우에서는 디버그 까지만 적용이 됩니다. 좀더 보완하겠습니다.ㅜㅜㅜ 2023.10.14 - [정리] - 백준 문제 편하게 풀기 지난번 포스팅에서 명령어를 통해 실행을 했다.(Redirection) 그런데 그것도 귀찮아지기 시작했다. 결정적으로는 디버깅할 때는 stdin redirection이 작동을 안했다. VSC 가 Hackable 하다는 걸 어디서 주워들었기 때문에, 이럴 때 쓰라고 있는 GPT한테 방법을 물어봤다. 요약 tasks.json 를 통해 빌드 명령을 실행할 수 있다. launch.json을 통해서 디버깅 환경을 설정할 수 있다. 상세 .vscode 폴더를 내가 작업하려는 디렉토리에 만들고, 그 안에 아래 두 파일을 넣는다. tasks.json { "versi..