미새문지

깊이 우선 탐색(DFS, depth-first search) 깊이 우선 탐색(DFS)은 그래프의 모든 노드를 탐색하는데 사용되는 알고리즘 중 하나이다. 루트 노드에서 시작해 한 방향으로(주로 왼쪽부터) 들어갈 수 있는한 끝까지 탐색하여 더 이상 들어갈 수 없는 경우, 가장 최근의 분기점으로 돌아가 다른 방향의 노드를 탐색하는 방식으로 진행된다. DFS의 구현 // 그래프를 인접 리스트 형태로 표현 const graph = { A: ['B', 'C'], B: ['A', 'D', 'E'], C: ['A', 'F'], D: ['B'], E: ['B', 'F'], F: ['C', 'E'] }; // DFS 함수 정의 function dfs(graph, startNode) { let visited = []; //..

https://moonmisae-cdpt.tistory.com/173 스택(Stack), 큐(Queue) 스택(Stack) 스택은 프로그래밍에서 사용되는 기본적이면서도 중요한 자료구조 중 하나이며, 선형 자료구조이다. 데이터를 임시 저장하고 관리하는데 사용되며, 특히 데이터의 입력과 출력순서 moonmisae-cdpt.tistory.com https://moonmisae-cdpt.tistory.com/174 pintOS - project2(Userprog) syscall.c syscall.c 더보기 #define MSR_STAR 0xc0000081 /* 세그먼트 셀렉터 MSR, 64비트 모드로 전환할 때 사용되는 셀렉..

스택(Stack) 스택은 프로그래밍에서 사용되는 기본적이면서도 중요한 자료구조 중 하나이며, 선형 자료구조이다. 데이터를 임시 저장하고 관리하는데 사용되며, 특히 데이터의 입력과 출력순서가 후입선출(LIFO, Last In First Out) 방식으로 이루어진다. 스택의 특징 스택은 한쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 자료 구조이다. 데이터의 추가(push)와 삭제(pop)가 같은 쪽에서 이루어지며, 가장 마지막에 들어온 데이터가 가장 먼저 나가는 구조를 가진다. 스택은 웹 브라우저의 뒤로 가기 기능, 함수 호출 시의 콜 스택 관리, 괄호 검사 , DFS(깊이 우선 탐색)등 다양한 애플리케이션에서 활용된다. 스택의 기본 연산 push() : 스택에 데이터를 추가하는 작업. 스택의 가장 위에 ..

연결리스트의 노드들을 큐를 사용해 저장하고 노드가 홀수 값이면 제거 void createQueueFromLinkedList(LinkedList *ll, Queue *q) { // 현재 노드를 가리키는 포인터를 선언 ListNode *cur; // 시작하기 전 매개변수로 받은 큐를 전부 없애기 removeAllItemsFromQueue(q); // 현재 노드에 리스트의 첫 노드를 넣기 cur = ll->head; // 현재 노드가 존재하는 동안 반복하며 while(cur != NULL) { // 큐를 삽입(enqueue에 큐와 현재 노드의 값을 인자로 보내기) enqueue(q, cur->item); // 현재 노드를 다음 노드로 변경 cur = cur->next; } } void removeOddValu..

스택과 레지스터의 용도와 장점 스택 프로시저 호출 시 지역 변수와 매개변수를 저장하기 위한 메모리 공간이며, LIFO(Last in First Out)이라는 마지막에 들어온 값이 먼저 나가는 구조를 가지고 있다. 용도 함수의 로컬 변수 저장 : 각 함수 호출 시 그 함수의 로컬 변수들이 스택에 저장된다. 함수의 제어 흐름 관리 : 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다. 장점 동적으로 메모리를 할당하고 해제할 수 있다. 구현이 간단하며, 메모리 관리의 오버헤드가 낮다. 레지스터 프로세서 내부의 고속 작동 메모리로, 프로시저 실행 중 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용 용도 중간 연산 결과 저장 : 연산 중 생성되는 중간 값을 빠르게..

어제에 이어서 알고리즘 문제만 하루종일 풀었다. ​ 나무 자르기 # # 입력 : # # 나무 개수값 n, 상근이가 가져가고 싶은 길이값 m, 나무 길이들 # # 출력 : # # 절단기의 설정 값 # import sys # namu = list(map(int, sys.stdin.readline().split())) # namu_length = list(map(int, sys.stdin.readline().split())) # namu_length.sort(reverse=True) # # 자른 길이 # # 톱 높이 나무가 제일 큰게 20이면 19로 설정 # saw_height = namu_length[0] - 1 # # 톱 높이를 제일 큰 나무의 -1부터 시작해서 1씩 감소 # for saw_count in..

하노이탑 3개의 기둥이 있고 하나의 기둥에 여러 개의 원반이 있는데 각자 크기가 다 다르며 한 번에 한 개의 원반만 옮길 수 있고 크기가 큰 원반은 작은 원반 위에 올릴 수 없다. 재귀 함수를 이용한 알고리즘의 대표 문제이며 다음과 같이 동작한다 옮겨야 할 원반이 하나 뿐이라면, 해당 원반을 출발지 기둥에서 목적지 기둥으로 옮기기 그렇지 않으면 재귀함수를 사용해 가장 큰 원반을 제외한 나머지 원반들을 보조 기둥으로 옮긴다. 가장 큰 원반을 목적지 기둥으로 옮기고, 보조 기둥에 있는 원반들을 목적지로 옮긴다. # 하노이 함수(원판의 갯수, 시작봉, 중간봉, 끝봉) def hanoi(n, start, sub, finish): # 만약 원판의 개수가 1개면 끝봉으로 1번 이동하면 끝이니까 리턴값 if n ==..