Memory Layout of Programs (프로세스의 메모리 구조)

Memory Layout of Programs (프로세스의 메모리 구조)

메모리구조 영역의 구분 정적할당과 동적할당을 담당하는지 여부에 따라 영역을 구분합니다. 정적할당의 경우 text segment과 bss segment, data segment가 담당하고 동적할당의 경우 stack segment과 heap segment가 담당합니다. 정적할당 정적할당이란 컴파일 단계에서 메모리를 할당하는 것입니다. text segment(텍스트 영역) text segment은 메모리에 올라간 실행 중인 프로그램의 영역입니다. text segment은 실행 가능한 instruction들이 들어가 있습니다. 텍스트 영역은 오작동을 막기 위해 읽기만 가능합니다. initialized data segment(초기화 된 데이터 영역) 전역변수와 정적 변수 중에 초기화 된 변수들이 존재하는 영역을 ..

  • format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
  • · 2024. 4. 2.
다익스트라 알고리즘

다익스트라 알고리즘

다익스트라 알고리즘 개념 사용환경 가중치 그래프에서 시작점과 도착점이 주어졌을 때 최단 경로를 찾는 알고리즘 원리 방문할 수 있는 노드 중에 가장 비용이 작은 곳(우선순위가 높은 곳)을 방문 1. 우선순위 큐에 시작노드 추가 2. 우선 순위가 가장 높은 노드 추출 3. 방문 여부 확인 4. 비용 업데이트 5. 현재노드와 연결된 노드를 우선순위 큐에 추가 6. 목적지에 기록 된 비용 반환구현 다익스트라 알고리즘 import heapq def dijkstra(graph, start, final): costs = {} pq = [] heapq.heappush(pq, (0, start)) while pq: cur_cost, cur_v = heapq.heappop(pq) if cur_v not in costs: ..

  • format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
  • · 2024. 4. 2.
우선순위 큐

우선순위 큐

우선순위큐 개념 정의 우선순위큐는 들어온 데이터의 우선순위에 따라 데이터를 꺼내는 자료구조입니다. 큐는 들어온 순서에 따라 데이터를 꺼내는 반면에 우선순위큐는 우선순위에 따라 데이터를 꺼냅니다. 우선순위 큐는 3가지 방식으로 구현할 수 있습니다. ① 배열 ② 연결리스트 ③ 힙으로 구현할 수 있습니다. 배열과 연결리스트의 경우, 정렬의 유무에 따라 데이터 처리의 시간복잡도가 O(N) ~ O(NlogN)이나 힙의 경우 O(logN)으로 동일합니다. 따라서 우선순위큐는 힙으로 구현합니다. 힙 자료구조 구현 힙 자료구조는 완전이진트리의 한 형태로 리프노드를 제외한 모든 노드들이 점유되어 있고 자식노드는 왼쪽부터 채워지는 구조입니다. 완전이진트리의 특징은 다음과 같습니다. 1. 리프노드를 제외한 모든 레벨에 노드..

  • format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
  • · 2024. 4. 2.
트리의 구현

트리의 구현

배열로 트리 구현 이진트리를 배열로 표현할 수 있습니다. 부모노드와 자식노드는 다음의 인덱스 관계를 갖습니다. [배열활용] 부모노드와 자식노드의 인덱스 관계 부모노드의 인덱스: n 자식노드의 인덱스: 2*n + 1, 2*n + 2[배열활용] 부모-자식 노드의 관계 표현 my_tree = [&#39;A&#39;,&#39;B&#39;,&#39;C&#39;,&#39;D&#39;,&#39;E&#39;,&#39;F&#39;,None,&#39;G&#39;] i = 0 n = len(my_tree) while i < n: if my_tree[i]: print(f"Parent: {my_tree[i]}", end=&#39;, &#39;) left = 2 * i + 1 right = 2 * i + 2 if left < n..

  • format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
  • · 2024. 3. 30.
트리: 데이터 간의 계층구조

트리: 데이터 간의 계층구조

트리이론 트리개념 리스트는 데이터에 순서를 메겨 나열하는 자료구조입니다. 반면에 트리는 데이터의 계층관계를 표현하는 자료구조입니다. 위, 아래 개념을 컴퓨터에서 표현한 구조입니다. 트리는 재귀적으로 정의 된 자기참조형 자료구조입니다. 트리는 특수한 그래프의 일종입니다. 트리는 비순환적 구조를 가집니다. 노드: 루트, 리프, 부모, 자식, 형제, 자손, 조상 트리는 노드와 가지로 구성됩니다. 트리의 가장 최상단 노드를 루트라고 합니다. 트리의 가장 말단 노드를 리프라고 합니다. 노드에서 더 이상 뻗어나갈 가지가 없을 경우 리프노드로 봅니다. 노드 간에 가지로 연결되어 있을 때 아래쪽 노드를 자식 노드, 위쪽 노드를 부모 노드라고 합니다. 부모노드를 공유하는 노드를 형제노드라고 합니다. 어떤 노드가 가지를 ..

  • format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
  • · 2024. 3. 30.
자료구조와 알고리즘 공부 로드맵

자료구조와 알고리즘 공부 로드맵

https://roadmap.sh/datastructures-and-algorithms Data Structures and Algorithms Roadmap Learn about Data Structures and Algorithms using this roadmap. Community driven, articles, resources, guides, interview questions, quizzes for modern backend development. roadmap.sh 자료구조와 알고리즘 로드맵입니다.

  • format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
  • · 2024. 3. 30.