홈 > 강의소개
자료구조Ⅰ
신흥철 교수
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
KAIST 대학원 전산학부 석사과정
KAIST 대학원 전산학부 박사졸업
숙명여자대학교
Microsoft
현) 유니와이즈 전임교수
AI가 이끄는 스마트한 학습 경험, AI 튜터와 함께 더 빠르고, 더 깊게 학습하세요.
긴 강의 내용을 AI가 핵심만 요약하여 복습 시간을 단축시킵니다.
강의에서 가장 중요한 키워드와 개념을 자동으로 추출해 제공합니다.
학습한 내용을 바탕으로 AI가 생성한 퀴즈를 풀며 이해도를 점검합니다.
모르는 부분을 24시간 언제든 AI 튜터에게 질문하고 답변을 받습니다.
총 6개 챕터, 19강으로 구성되어 있습니다.
| 제목 | 강의시간 | 상세내용 |
|---|---|---|
| 1장. 자료구조와 알고리즘 | ||
|
[1강] 자료구조와 알고리즘
|
0:
58:
09
|
|
|
자료구조와 알고리즘 기초 개념 및 알고리즘 표현 방식 정리
• 자료구조 기본 개념: 리스트·스택(LIFO)·큐(FIFO)·트리·그래프·탐색 구조 정의와 C 언어 배열을 통한 자료 저장 구조 이해 • 프로그램 구성 원리: 전역/지역 변수, 상수 정의, 배열, 함수 반환형과 매개변수, call by value·call by reference(포인터 활용), 스택 기반 함수 호출 구조 • 알고리즘 형식 체계: 알고리즘 정의와 5가지 조건(입력·출력·명확성·유한성·유효성) 및 자연어·흐름도·유사코드·프로그래밍 언어 표현 방식 특징 정리 |
||
|
[2강] 추상데이터 타입. 알고리즘의 성능 분석. 자료구조 표기법
|
1:
08:
37
|
|
|
추상 데이터 타입과 알고리즘 성능 분석 및 자료구조 표기법 핵심 정리
• 추상 데이터 타입(ADT) 개념: 객체와 연산 명세를 구현과 분리하여 정의하고, 자료구조(구조체·typedef)와 연산 함수(push, pop, 탐색 등)를 독립적으로 설계하는 데이터 추상화 원리 • 알고리즘 성능 분석: 성능 측정 vs 성능 분석 구분, 입력 크기 기준 시간·공간 복잡도 정의, Big-O·Big-Ω·Big-Θ 표기와 지배항 개념, 순차 탐색 알고리즘의 최선·최악·평균 시간 복잡도 도출 • C 자료구조 표기 관례: 상수·변수·함수 네이밍 규칙, typedef로 논리적 타입 정의, 구조체 기반 리스트·스택(StackType)의 데이터 구성과 포인터를 활용한 연산 함수 구현 방식 정리 |
||
| 2장. 순환 | ||
|
[3강] 순환의 소개. 거듭제곱 값 계산
|
1:
01:
55
|
|
|
순환 알고리즘과 거듭제곱 계산 알고리즘 핵심 정리
• 순환(recursion)과 재귀 관계: 자기 호출 구조와 초기/종료 조건을 기반으로 선행항으로 현재항을 정의하는 재귀 관계 개념 및 스택 기반 호출·복귀 메커니즘 정리 • 순환 vs 반복 알고리즘: 팩토리얼 예제를 통해 두 방식의 시간 복잡도 O(n) 동일성, 스택 오버헤드에 따른 실제 성능·메모리 차이, 표현 간결성과 실행 효율성 트레이드오프 비교 • 거듭제곱 계산 알고리즘: 단순 반복 i_power의 O(n) 구조와 대비되는 지수 이진 분할 기반 r_power·i2_power 알고리즘의 O(log n) 시간 복잡도, 이진 표현 활용 절차 및 연산 최적화 원리 정리 |
||
|
[4강] 피보나치 수열의 계산. 하노이탑 문제
|
0:
49:
52
|
|
|
피보나치 수열과 하노이 탑: 순환 vs 반복 알고리즘 시간복잡도 비교
• 피보나치 수열 알고리즘: 점화식 f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)에 기반한 순환 알고리즘의 중복 호출로 인한 지수 시간복잡도 O(2^n)와 반복 알고리즘의 선형 시간복잡도 O(n) 비교 • 순환 알고리즘과 Divide & Conquer: 점화식을 그대로 구현하는 순환 구조와 연산 횟수를 감소시키는 Divide & Conquer 기법(분할·정복·합병)의 개념, 피보나치 순환의 비효율성과 빠른 거듭제곱·이진 탐색·정렬 알고리즘 등의 대조 • 하노이 탑 문제: n개 원반 이동 최소 횟수 점화식 H_n=2H_{n-1}+1, 해 H_n=2^n-1 도출과 이에 따른 순환 알고리즘 구조(ht(n-1, from→temp, temp→to) 패턴) 및 고정적인 지수 시간복잡도 O(2^n)의 특성 정리 |
||
| 3장 배열, 구조체, 포인터 | ||
|
[5강] 배열
|
0:
37:
01
|
|
|
배열과 2차원 배열, 함수 매개변수 배열의 메모리 구조 핵심 정리
• ADT Array와 배열 개념: 동질적 요소 집합을 <인덱스, 요소> 쌍과 create·retrieve·store 연산으로 정의하는 추상 자료형 구조 • 배열 메모리와 주소 계산: 1차원·2차원 배열의 연속 메모리 배치에서 base + 인덱스(또는 i×n+j) × sizeof(요소)로 물리 주소를 계산하는 규칙 • 배열 이름과 포인터·함수 전달: 배열 이름을 첫 요소 주소를 나타내는 상수 포인터로 해석하고, 함수 인자에서 주소 복사에 의해 배열 요소 변경이 호출자에게 반영되는 메커니즘 |
||
|
[6강] 배열의 응용: 다항식
|
1:
06:
00
|
|
|
다항식의 배열 표현과 덧셈 알고리즘 정리
• 다항식 배열 표현 방식: dense 구조(poly)의 최대차수·계수 배열 기반 표현과 sparse 구조(term)의 (계수, 차수) 쌍·구간 인덱스 기반 표현 및 메모리 효율 비교 • 덧셈 알고리즘 설계: poly_add1의 최대차수 기준 인덱스·차수 동기화 순회와 poly_add2의 term 전역배열·comp 비교·att 삽입을 이용한 sparse 덧셈 절차 정리 • 전역 배열·예외 처리: term·avail 전역 관리, 시작·끝 인덱스(sA,eA,sB,eB,sC,eC) 기반 다항식 구간 표현, 경계 검사와 side effect·포인터 인자 처리 원리 설명 |
||
|
[7강] 배열의 응용: 희소 행렬. 구조체
|
1:
00:
54
|
|
|
배열의 응용: 희소 행렬과 구조체 기본 개념 정리
• 희소 행렬 및 인덱스 넘버: 0이 아닌 원소만 (행, 열, 값) 구조로 저장하고 index_number=row×열수+col 공식을 이용해 2차원 위치를 1차원 인덱스로 변환·비교하는 메모리·연산 최적화 개념 정리 • 희소 행렬 연산 구조(SM 방식): element, SM 구조체로 희소 행렬을 표현하고 ts(0이 아닌 항 개수) 기반 병합 알고리즘(sm_add2)으로 덧셈을 수행하는 절차와 자료구조 설계 원리 정리 • 구조체 문법 및 활용: struct/typedef 기반 사용자 정의 타입, 구조체 대입과 필드 비교 규칙, 자기 참조 구조체를 통한 연결 구조, 구조체 배열·중첩 구조체를 이용한 복합 데이터 모델링 방식 정리 |
||
|
[8강] 포인터. 동적 메모리 할당
|
1:
00:
22
|
|
|
포인터와 동적 메모리 할당 핵심 개념 정리 (C 언어)
• 포인터와 포인터 유형: 주소를 저장하는 포인터의 개념과 &·* 연산자, 배열 이름과의 관계, 구조체 포인터와 → 연산자, 포인터의 포인터와 함수 포인터 선언 및 호출 방식 정리 • 포인터 활용과 주의점: 함수 매개변수로서의 포인터를 통한 call by value 보완(swap 등), 포인터 연산(증가·감소, 간접참조) 의미 구분, NULL 초기화·명시적 캐스팅 등 안전한 포인터 사용 규칙 정리 • 메모리 할당 방식: 정적 메모리 할당의 특성과 한계, 동적 메모리 할당의 개념과 malloc·free·calloc 사용 절차, sizeof 연산자를 이용한 이식성 있는 메모리 크기 계산 방법 정리 |
||
| 4장. 리스트 | ||
|
[9강] 리스트 추상 데이터 타입. 배열로 구현된 리스트
|
1:
06:
11
|
|
|
배열로 구현한 리스트 ADT와 C 구조체·포인터 핵심 정리
• 리스트 추상 데이터 타입과 배열 기반 구현: 순서가 있는 요소 집합으로서 리스트 ADT 연산(add, delete, get, length, is_empty, is_full, display)을 정의하고, 이를 `element list[]`와 `int length` 필드를 가진 ArrayList 구조체로 구현하며 인덱스와 길이, 공백/포화 및 경계 조건을 관리하는 구조 • 배열 리스트 연산 절차: add(pos)에서 뒤에서 앞으로 한 칸씩 이동 후 삽입하고 delete(pos)에서 앞에서 뒤 값을 한 칸씩 당겨 삭제하며, 항상 `0 ≤ pos ≤ length`, `length ≤ MAX_LIST_SIZE` 조건을 검증하고 display는 `0`부터 `length-1`까지 순차 접근해 실제 저장된 요소만 출력하는 절차 • 구조체·포인터와 메모리 관리: C의 값 전달과 주소(포인터) 전달 차이를 기반으로 `ArrayList *L` 형태 구조체 포인터 인자로 원본을 조작하고, `.`와 `->` 연산자 차이를 구분하며, 정적 배열과 `malloc/free`를 이용한 동적 할당에서 리스트 논리 구조는 동일하되 메모리 확보 시점·수명·메모리 누수 관리가 핵심인 개념 |
||
|
[10강] 연결 리스트 (1)
|
0:
38:
16
|
|
|
연결 리스트와 단순 연결 리스트 삽입 함수 핵심 정리
• 연결 리스트 자료 구조: 배열과 대비되는 물리적 자료 구조로, 동적할당 기반 노드(데이터+링크) 연결을 통해 메모리 효율·삽입·삭제 성능을 확보하며 포인터 오버헤드와 선형 탐색 비용을 가짐 • 연결 리스트 유형과 구조: 단순·원형·이중 연결 리스트로 구분되며, 헤드 포인터/헤드 노드 사용 방식, 단방향·양방향 링크, 마지막 노드 링크(NULL·첫 노드) 차이를 통해 탐색·삽입·삭제 동작 특성이 결정됨 • 단순 연결 리스트 구현과 삽입 알고리즘: C 구조체(ListNode)와 malloc 기반 create_node로 노드를 생성하고, insert_node(ListNode **phead, ListNode *p, ListNode *node)에서 공백 리스트·첫 노드 앞·중간 삽입 3가지 경우를 헤드 포인터의 포인터와 링크 갱신 순서(node->link, p->link)로 제어함 |
||
|
[11강] 연결 리스트 (2)
|
0:
40:
27
|
|
|
단순 연결 리스트 삭제·방문·탐색·연결·역순 및 main 적용 정리
• 단순 연결 리스트 기본 연산: 노드 삭제(remove_node), 반복·재귀 방문(i_traverse, r_traverse), 선형 탐색(search)을 통해 헤드 포인터·선행/현재 노드 포인터 활용과 공백 리스트·NULL 처리 원리 정리 • 리스트 구조 변환 연산: 두 리스트 연결(concat)과 역순 변환(reverse)을 통한 링크 재설정 절차, p·q·r 포인터 역할, in-place 링크 방향 변경 및 결과 헤드 포인터 반환 구조 정리 • 동적 메모리 관리: create_node·insert_node·main 예시를 통한 동적 노드 생성·삽입 과정과 연산 후 노드 단위 free를 수행하는 리스트 해제 절차 및 메모리 누수 방지 원리 정리 |
||
|
[12강] 연결 리스트 (3)
|
1:
04:
16
|
|
|
원형·이중 연결 리스트와 다항식 연결 리스트 구현 요약
• 원형·이중 연결 리스트 구조: 원형 연결 리스트와 tail 포인터로 앞·뒤 삽입을 상수 시간에 수행하고, 이중 연결 리스트의 양방향 링크(llink, rlink)와 헤드 노드로 선행·후속 노드 직접 접근 및 포인터 재연결 기반 삽입·삭제 구현 • 다항식 연결 리스트 표현: 계수(co)·차수(ex)를 가진 PolyNode와 길이(len)·head·tail을 가진 PolyHeader로 다항식을 단순 연결 리스트로 표현하고, append 연산으로 후단 노드 추가 및 공백/비공백 리스트 관리 • 다항식 덧셈 알고리즘: 차수 내림차순 정렬된 두 다항식 리스트를 순차 비교(ex 같음/큼/작음)하여 결과 리스트에 병합(append)하는 poly_add 알고리즘으로, 계수 합이 0인 항은 생략하고 O(m+n) 시간에 다항식 합을 구성 |
||
|
[13강] 연결 리스트로 구현된 리스트. 선형 리스트의 응용
|
0:
59:
16
|
|
|
연결리스트 기반 리스트 ADT 구현과 텍스트 에디터 응용 정리
• 리스트 ADT와 자료구조 개념: 배열·연결리스트 등 물리적 구조와 리스트·스택·큐·트리·그래프 등 논리적 구조, 리스트 ADT의 순서·위치·연산 집합 정의 및 단순 연결리스트(헤더 LinkedList, 노드 ListNode, 0-based 인덱스)로의 구현 원리 정리 • 연결리스트 기본 연산과 구현 절차: is_empty·get_length·get_nodeptr 기반 탐색, add·add_first·add_last·delete·get_entry·clear·display·is_in_list 연산의 인덱스 범위 조건, 선행 노드/대상 노드 포인터 사용, 링크 조정과 메모리 할당·해제 원리, ADT 기반 구현과 포인터 직접 조작 방식의 효율성 비교 • 텍스트 에디터 응용 구조: 한 줄을 element(문자 배열)로, 한 줄 노드를 ListNode로, 전체 문서를 LinkedList로 구성하는 라인 리스트 구조와 줄 단위 삽입·삭제·수정 연산을 리스트 ADT 연산(add, delete, get_entry, replace 등)에 매핑하는 설계 원리 정리 |
||
|
[14강] 동치 부류
|
1:
18:
32
|
|
|
동치 관계와 연결리스트를 이용한 동치 부류 알고리즘 요약
• 동치 관계·동치 부류 개념: 반사·대칭·이행 관계로 정의되는 동치 관계와 집합의 분할로서의 동치 부류 구조, 모듈로 3 예(세 동치 부류)로 분할 개념 정리 • 동치쌍 리스트·스택 기반 equ_class 알고리즘: seq 포인터 배열·ListNode 구조·out 방문 배열을 이용해 equ_pairs로 양방향 인접 리스트(동치쌍 리스트)를 만들고, 연결리스트를 재사용한 스택(top)과 DFS 유사 탐색으로 각 동치 부류를 한 번씩만 추출하는 절차 • 시간 복잡도 O(m+n): n개 원소 초기화와 바깥 루프가 O(n), m개 동치쌍(2m개 노드) 처리와 리스트·스택 탐색이 각 노드를 최대 한 번씩만 방문하여 O(m), 전체 동치 부류 계산이 선형 시간에 수행됨 |
||
|
[15강] 희소 행렬
|
1:
14:
43
|
|
|
희소행렬 다중 연결 리스트 구조와 구현 요약
• 희소행렬 노드 및 헤더 구조: tagfield와 union을 사용하는 mNode(head/entry 통합 구조), 행·열 겸용 헤더 노드 배열 H, right/down 포인터를 이용한 원형 다중 연결 리스트 표현 • 희소행렬 입·출력 및 삭제 절차: mread의 헤더 생성과 (row,col,val) 기반 행·열 동시 연결, mwrite의 행 헤더 순회 기반 (row,col,val) 출력, merase의 행별 엔트리 및 잔여 헤더 노드 해제 과정 • 시간복잡도 및 메모리 효율: mread·merase의 O(Rows+Cols+Terms), mwrite의 O(Rows+Terms) 분석과 0이 아닌 항목만 저장하는 방식의 공간 절약 및 연결 구조 설계 원리 |
||
| 5장. 스택 | ||
|
[16강] 스택 (1)
|
1:
06:
28
|
|
|
스택 구현과 응용: 배열·연결리스트, 괄호 검사 정리
• 스택 추상 데이터 타입과 LIFO 구조: top 기반 상태관리, create/is_empty/is_full/push/pop/peek 연산 정의 및 후입선출 동작 원리 정리 • 스택 구현 방식: 배열 기반 스택과 연결 리스트 기반 스택의 자료구조 정의, 초기화·공백/포화 검사, push/pop 절차 및 정적 크기 제약 vs 동적 메모리 활용 비교 • 스택 응용: 함수 호출 스택 프레임(복귀 주소·매개변수·지역변수) 관리와 undo 기능, 괄호 검사 알고리즘(올바른 괄호열 조건·스택 기반 검사 절차) 구조화 정리 |
||
|
[17강] 스택 (2)
|
1:
01:
24
|
|
|
수식 계산과 스택 응용: 후위 표기, 중위 변환, 미로 탐색
• 수식 표기법과 후위 표기식 계산: 중위·전위·후위 표기 개념과 특징, 후위 표기식에서 피연산자 push·연산자 시 op2/op1 pop 후 연산·결과 재 push 구조, 한 번의 순차 스캔으로 연산자 우선순위·괄호 없이 계산하는 스택 기반 알고리즘 정리 • 중위 → 후위 변환 알고리즘: 피연산자 즉시 출력, 연산자·괄호만 스택 저장, 우선순위 함수 pr(op)로 “현재 연산자 ≤ 스택 top 연산자”이면 pop 후 출력, 괄호 쌍 처리와 종료 시 스택 비우기를 통해 연산자 순서를 재배치하는 구조적 변환 절차 정리 • 스택 기반 미로 탐색(DFS): 좌표(r,c)를 원소로 하는 스택 구조와 상·하·좌·우 후보 pushL 조건(인덱스 범위·벽·방문 여부 검사), 방문 위치 마킹과 스택 empty 시 실패·출구 'x' 도달 시 성공으로 정의되는 비재귀 깊이 우선 탐색 알고리즘 정리 |
||
| 6장. 큐 | ||
|
[18강] 큐 (1)
|
1:
01:
30
|
|
|
큐 ADT와 배열·연결리스트 구현 핵심 정리
• 큐 추상 데이터 타입 개념: 선입선출(FIFO) 선형 자료구조로, create·init·is_empty·is_full·enqueue·dequeue·peek 연산과 front·rear 포인터 의미 정의 • 배열 기반 큐 구현: 선형 큐와 원형 큐에서 front/rear 인덱스, 공백·포화 조건, 모듈러 연산을 이용한 원형 큐 구조, 큐 구조체(QueueType)와 is_empty·is_full·enqueue·dequeue 절차 정의 • 연결 리스트 기반 큐 구현: 노드 구조체(QueueNode)와 헤더(LinkedQueue)에서 front·rear 포인터 의미, 동적 메모리(malloc/free)에 기반한 enqueue·dequeue 알고리즘과 빈 큐/단일 노드 예외 처리 규칙 정의 |
||
|
[19강] 큐 (2)
|
0:
42:
29
|
|
|
덱(deque)과 큐의 응용 핵심 정리
• 덱과 Linked Deque 구조: 양쪽 끝에서 삽입·삭제 가능한 double-ended queue 개념과 create/init/is_empty 연산, head·tail·llink·rlink로 구성된 양방향 연결 리스트 기반 Linked Deque 구조 및 노드 생성/에러·경계 처리 원리 정리 • 덱 연산 알고리즘: add_front/add_rear, del_front/del_rear, get_front/get_rear 연산에서 공백·단일 노드·일반 경우별 head·tail 및 양방향 링크 조정 절차와 O(1) 시간 복잡도 구현 원리 정리 • 큐의 응용 개념: 장치 간 버퍼링과 작업 순서 제어(프린터 서버·사용자별 큐) 및 은행·콜센터 대기 행렬 시뮬레이션에서 도착 패턴, 서비스 처리기 수, 서비스 시간, 평균 대기시간을 큐 모델로 분석하는 기법 정리 |
||
신흥철 교수님
자료구조Ⅰ
