자료구조·알고리즘, 질문하며 배우기

수업 진행

🎬

애니메이션

아래 SVG 단계 재생

🤖

질문

원리를 LLM에 물어보기

⌨️

구현

자바/파이썬으로 코딩

👩‍🏫

리뷰

복잡도·언제 쓰는지

애니메이션 사용법: 각 섹션 SVG 아래 ◀ ▶ 버튼(원본 교안과 동일)으로 단계 진행. 이미지는 images/, SVG 스프라이트는 images/datastructure.svg 를 이 폴더에 복사하세요.

1. 알고리즘 소개

🤖 AI에게 물어보자

알고리즘 정의와 단계(문제정의→설명→검증→성능), 시간복잡도 O 표기를 초보자용으로 설명해줘. 예: 선형 탐색 O(n), 이진 탐색 O(log n).

알고리즘 단계

문제 정의 — 무엇을, 어떤 형태로 풀 것인가
알고리즘 설명 — 컴퓨터가 수행할 순서를 정의
정확성 검증 — 오류 없이 결과가 나오는지
성능 테스트 — 시간복잡도 · 공간복잡도

2. 정렬

삽입정렬 — 자신의 위치를 찾아 삽입

🤖 AI에게 물어보자

삽입정렬 아이디어를 3줄로 설명하고, [4,8,3,1,6,2]를 삽입정렬하는 자바 코드를 완성해줘. 매 단계 배열 상태를 출력.

퀴즈 — 빈칸(❓)을 채우세요. 정렬되지 않은 앞쪽과 비교하며 뒤로 밀어내는 조건은?

int[] data = {4, 8, 3, 1, 6, 2};
int numSorted = 1;
while (numSorted < data.length) {
    int temp = data[numSorted];
    for (int index = numSorted; index > 0; index--) {
        // ❓ temp와 data[index-1] 비교 후 이동
    }
    data[index] = temp;
    numSorted++;
}

👩‍🏫 선생님 리뷰 · 삽입정렬 정답 코드

if (temp < data[index - 1]) {
    data[index] = data[index - 1];
} else {
    break;
}

평균·최악 O(n²), 거의 정렬된 배열에서는 매우 빠름.

선택정렬 — 최소/최대를 선택해 교환

🤖 AI에게 물어보자

선택정렬 의사코드를 단계로 쓰고, [4,8,3,1,6,2] 자바 구현을 보여줘. 매 라운드 최소값 위치와 교환 대상을 출력.

퀵정렬 — 피벗 기준 분할 · 재귀 고급

🤖 AI에게 물어보자

퀵정렬의 partition과 재귀 호출 구조를 설명해줘. 자바로 swap, partition, quickSortRecursive를 포함한 전체 코드를 짜줘. 데이터 {1,8,3,4,6,2}.

평균 O(n log n), 최악 O(n²) — 피벗 선택이 성능에 큰 영향

3. 검색

순차검색

처음부터 끝까지 비교
정렬 불필요 · 최악 O(n)

이진검색

정렬된 데이터에서만
한 번에 범위 1/2 · O(log n)

🤖 AI에게 물어보자

이진검색 while 루프에서 middle 계산 후 key와 비교해 low/high를 갱신하는 자바 코드를 완성해줘. 정렬된 배열에서 3을 찾는 예제 포함.

퀴즈 — low ≤ high 인 동안 middle = (low+high)/2 일 때, key가 middle보다 크면?

else if (key > data[middle]) ❓ = middle + 1;
else high = middle - 1;

4. 문제접근법 고급

종류	아이디어	예
Brute-Force	모든 경우	약수, 비밀번호 시도
Divide & Conquer	하위 문제 독립	합병·퀵정렬
Dynamic Programming	하위 결과 재사용(메모)	피보나치
Greedy	지금 최선	거스름돈

🤖 AI에게 물어보자

피보나치 순수 재귀의 문제점과, 메모이제이션 배열을 쓰는 버전, bottom-up DP 버전 자바 코드를 비교해줘. 호출 횟수가 왜 줄어드는지 설명해줘.

자료구조 1. ADT

🤖 AI에게 물어보자

ADT(Abstract Data Type)를 데이터·연산·에러 상태로 나누어 설명하고, 스택 ADT(push/pop/peek/isEmpty) 예로 들어줘.

자바 컬렉션 대응

유형	클래스
Stack	java.util.Stack, Deque
Queue	LinkedBlockingQueue 등
List	LinkedList, ArrayList
Tree	TreeMap, TreeSet
Hash	HashMap, HashSet

2. 스택 (LIFO)

연산	상태 예	리턴
isEmpty()	[]	true
push(3)	[3]
push('cat')	[3,'cat']
peek()	[3,'cat']	'cat'
pop()	[3]	'cat'

🤖 AI에게 물어보자

배열 기반 스택(full, empty, push, pop) 자바 클래스를 짜줘. top 인덱스 사용. 이어서 십진수 98을 이진수로 바꾸는 convert 메서드도.

실습 — {5,4,3,2,1}을 push한 뒤 pop하면서 3 이상/미만을 구분해 출력.

3. 큐 (FIFO)

🤖 AI에게 물어보자

배열 기반 큐(front, rear, offer, peek/empty) 자바 구현을 보여줘. 스택과의 차이를 한 문단으로.

실습 — {5,4,3,2,1} offer 후 순서대로 peek 출력 (5→1).

4. 연결리스트

🤖 AI에게 물어보자

단일 연결리스트 Node(data, next)와 LinkedList(addFirst, addLast, add(index), delete, print) 자바 코드를 짜줘. 배열과 비교한 장단점도.

더블 연결리스트: prev + next — 양방향 순회·중간 삭제에 유리

5. 트리와 힙 고급

트리 구조

이진트리 (차수 ≤ 2)

포화 이진트리

완전 이진트리: 마지막 레벨은 왼쪽부터 채움

이진 탐색 트리 (BST)

순회 (전위·중위·후위)

원본처럼 버튼으로 전위/중위/후위를 단계 재생합니다. (prebtn / inbtn / postbtn)

힙 (Heap)

🤖 AI에게 물어보자

이진 탐색 트리 삽입 규칙과 전위/중위/후위 순회 자바 코드를 보여줘. 힙의 삽입·삭제(위로/아래로 끌어올리기) 아이디어도 설명해줘.

6. 그래프 · DFS / BFS 고급

인접행렬

인접리스트

DFS (깊이 우선)

BFS (너비 우선)

🤖 AI에게 물어보자

인접리스트 그래프에서 DFS(재귀·스택)와 BFS(큐) 자바 구현을 보여줘. 스택 vs 큐가 탐색 순서를 어떻게 바꾸는지 설명해줘.

7. 해시테이블

🤖 AI에게 물어보자

해시테이블 원리, 해시 함수, 충돌(체이닝·개방주소법)을 초보자용으로 설명해줘. 평균 탐색이 O(1)에 가까운 이유도.

8. 더 알아보기 (확장)

우선순위 큐 — 힙으로 구현, Dijkstra 등에 사용
덱(Deque) — 양끝 삽입/삭제
트라이(Trie) — 문자열 접두사 검색
유니온-파인드 — 집합 병합·같은 집합 여부
AVL / Red-Black — 균형 이진 탐색 트리

🤖 AI에게 물어보자

우선순위 큐와 힙의 관계, Trie가 자동완성에 쓰이는 이유, Union-Find의 parent 배열 아이디어를 각각 짧게 설명해줘.

첨부 영상·추가 자료는 원본 교안 “첨부내용” 섹션을 참고하세요.