1. 힙 정렬 (Heap Sort)힙 복잡도 복습삽입/삭제 모두 O(log n) — 트리의 높이만큼만 이동하면 되기 때문힙 정렬 원리최대 힙을 이용해 정렬:n개 요소를 최대 힙에 하나씩 삽입 → 최대 힙 완성루트(최댓값)를 배열 마지막에 저장 → 힙에서 삭제 → 힙 재구성위 과정을 n번 반복 → 오름차순 정렬 완성sort(a[], n): h = create_heap, init_heap for i = 0 to n-1: insert(h, a[i]) // 최대 힙 구성 for i = n-1 to 0: a[i] = delete_max(h) // 큰 값부터 배열 뒤에 채움복잡도: O(n log n) — 빠른 편특장점: 전체 정렬보다 상위 k개 추출에..

1. 이진 트리 순회 복습순회순서특징전위 (preorder)루트 → 왼쪽 → 오른쪽 (VLR)루트를 자손보다 먼저 방문중위 (inorder)왼쪽 → 루트 → 오른쪽 (LVR)BST에서 오름차순 출력후위 (postorder)왼쪽 → 오른쪽 → 루트 (LRV)루트를 자손보다 나중에 방문재귀 구현이 기본 / 반복 구현은 스택 명시 사용 (인공지능 깊이 우선 탐색 응용)중위 순회의 핵심 성질: BST에서 중위 순회 = 오름차순 정렬 출력 → 스레드 이진 트리의 핵심 아이디어2. 스레드 이진 트리 (Threaded Binary Tree)NULL 링크 낭비 문제n개 노드 → 2n개 링크 중 n+1개가 NULL → 절반 이상 낭비스레드 이진 트리: NULL 링크에 중위 후속자(inorder successor) 포인터..

트리(TREE)란?지금까지 배운 리스트, 스택, 큐는 모두 선형 구조 — 데이터가 일렬로 나열된 형태다.트리(Tree) 는 비선형 구조(계층 구조) 로, 데이터 사이에 부모-자식 관계가 있다.선형 구조: [1] → [2] → [3] → [4]트리 구조: [A] / \ [B] [C] / | \ | [D][E][F] [G]트리의 응용 분야계층적 조직 표현 (회사 조직도, 책 목차)컴퓨터 디렉토리 구조 (탐색기의 폴더 트리)인공지능 결정 트리 (decision tree)트리의 용어트리 구조 예시 — A(루트) 아래 B, C, D가 있고 B의 자식이 E, F, G, D의 자식이 ..

핵심 연산 3가지삽입 (Insert): insert_first (앞에 삽입), insert (중간 삽입)삭제 (Delete): delete_first (앞 삭제), delete (중간 삭제)방문 (Traversal): print_list — head부터 NULL까지 순회노드 정의typedef int element;typedef struct ListNode { element data; struct ListNode *link;} ListNode;insert_first — 맨 앞에 삽입ListNode* insert_first(ListNode* head, element data) { ListNode *node = (ListNode *)malloc(sizeof(ListNode)); node-..

연결 리스트 도입배열 리스트의 한계배열로 리스트를 구현하면 연속된 메모리 공간(순차적 표현, sequential representation)이 필요중간 삽입/삭제 시 원소를 한 칸씩 밀거나 당겨야 함 → 비효율크기가 정해져 있어 유연하지 않음연결 리스트로 해결노드들을 메모리 어디든 흩어져 두고 포인터로 연결삽입/삭제 시 링크(포인터)만 바꾸면 됨 → 이동 불필요리스트 ADT 기본 연산insert(list, pos, item) // pos 위치에 삽입insert_last(list, item) // 맨 끝에 삽입insert_first(list, item) // 맨 처음에 삽입delete(list, pos) // pos 위치 삭제get_entry(list, pos) /..

스케줄링 알고리즘여러 개의 프로세스를 어떻게 효율적으로 처리하느냐성능 기준: 단위 시간당 처리량(Throughput) 과 평균 반환 시간 최소화간트 차트(Gantt Chart): 각 프로세스의 실행 구간을 시간 축에 표현한 막대 그래프 → 스케줄 결과 시각화에 사용선입 선처리 (FIFO / FCFS — First Come First Served)먼저 도착한 프로세스를 먼저 처리비선점 방식오버헤드 없음, 구현 간단호위 효과(Convoy Effect): CPU를 오래 사용하는 프로세스 하나 뒤에 짧은 프로세스들이 줄줄이 기다리는 현상 → 전체 평균 대기 시간 증가예시 계산 (도착 순서대로 P1~P5, 실행 시간: 10, 28, 6, 4, 14초):프로세스도착 시간실행 시간반환 시간대기 시간P1010100P2..

세마포 (Semaphore) — 상호배제 기법표식을 나타내는 장치. 상호배제 알고리즘의 한 기법으로, 1965년 네덜란드의 다익스트라(Dijkstra)가 제안.기존 방법(while 루프로 계속 체크)의 문제: 바쁜 대기(Busy Waiting) → CPU 낭비세마포의 해결: 상태가 바뀔 때만 반응 → CPU 낭비 없음세마포 변수 S음이 아닌 정수 변수 (양의 정수 + 0)현재 공유 자원을 사용할 수 있는지를 나타내는 깃발비유: 기차역 차단기차단기 올라감(빨간불) → 선로 사용 중, 진입 불가차단기 내려감(초록불) → 선로 비어있음, 진입 가능P연산과 V연산연산네덜란드어동작의미P연산Proberen (검사)S 확인 → 양수면 감소 후 진입, 0이면 대기임계 영역 진입 전 수행 = wait(S)V연산Verho..

선행 그래프 (Precedence Graph)프로세스 사이의 실행 순서(선행 관계) 를 그래프로 표현하는 것.복잡한 알고리즘을 설계할 때 프로세스 간 우선순위를 시각화이 그래프를 통해 교착 상태(Deadlock) 가 발생할지 예측 가능순환 구조가 있으면 데드락 위험 존재예시 :S1, S2 ──→ S3 ──→ 종료(S1, S2는 동시 실행 가능, S3는 둘 다 끝나야 실행 가능)예시 (fork/join 코드로 구현):구문설명a := x + yS1 실행fork L1L1 라인부터 새 흐름 분기 (S2 동시 실행 시작)goto L2S1 흐름은 L2로 이동L1: b := z + 1분기된 흐름에서 S2 실행join countcount(=2)개 흐름이 모두 끝날 때까지 기다림 (S1, S2 합류)L2: c := a ..

프로세스정의: 실행 중인 프로그램 (가장 일반적인 정의)디스크에 저장된 프로그램을 메인 메모리에 적재하여 CPU가 실행하고 있는 상태단순히 메모리에 올라갔다고 프로세스가 되는 게 아니라, 자원이 필요하다필요한 자원: 점유 시간, 메모리, 파일, 입출력 장치프로세스 메모리 구조:높은 주소 (0xFFFF)┌──────────────────┐│ Stack │ 함수호출, 지역변수, 복귀주소 (SP)│ ↓ │ ← 아래 방향으로 증가│ ││ ↑ │ ← 위 방향으로 증가│ Heap │ 동적 할당 (malloc 등)├──────────────────┤│ Data │ ..

CPU 내부 구조 — 레지스터CPU 내부에는 레지스터(Register) 라는 초고속 소형 메모리가 있다. 속도 순서:레지스터 > 캐시 > 메인 메모리 > 보조기억장치사용자 가시 레지스터 (프로그램에서 직접 사용 가능)종류설명데이터 레지스터연산할 데이터 저장, ALU 계산에 사용기준 주소 레지스터메모리 시작 위치(Base Address) 저장인덱스 레지스터배열·반복 접근 시 특정 위치 계산에 사용스택 포인터 레지스터LIFO 구조 스택의 현재 위치 저장사용자 불가시 레지스터 (OS·CPU 내부 전용)종류설명프로그램 카운터(PC)다음에 실행할 명령어의 주소 저장명령어 레지스터현재 실행 중인 명령어 저장누산기(Accumulator)ALU 연산 결과 저장메모리 주소 레지스터(MAR)접근할 메모리 주소 저장메모리 ..