알고리듬 및 자료구조 (Java)
프로그래머에게 필수인 문제해결 능력을 다음 단계로 업그레이드 해주는 강좌입니다. 핵심 알고리듬의 작동원리를 제대로 배워 탑 1% 개발자의 사고방식을 갖추세요. 프로그래머로 일을 해나가다 보면 새로운 문제를 계속해서 마주치게 되지만 이 강좌를 통해 문제 해결력을 갖춘 여러분은 그 문제의 해결법을 찾아낼 수 있을 겁니다.
배울 내용
- 핵심 알고리듬의 동작 원리 및 사용법
- 알고리듬의 시간/공간 복잡도 분석
요구 사항
- '개체지향 프로그래밍 및 설계 (Java)' 수료
설명
본 비디오 강좌는 POCU 아카데미에서 진행하는 COMP3500 수업의 비디오 강좌입니다.
프로그래머의 업무를 간단히 표현하면 '문제를 해결하는 것'입니다. 그렇기에 '문제를 해결하는 확실한 방법'인 알고리듬(algorithm)은 프로그래머의 필수 지식으로 종종 거론되곤 합니다.
그럼 어떤 사람이 진짜 개발자일까요? 최신 기술을 많이 아는 사람? 시중에 나와있는 모든 알고리듬 문제를 달달 외우고 있는 사람? 아닙니다. 제대로 된 개발자는 어떤 문제라도 확실히 해결할 수 있는 사람입니다. 알고리듬 문제 사이트에 없는 문제까지 말이죠. 그런 개발자가 되려면 몇몇 핵심 알고리듬을 확실히 이해하는 것이 가장 중요합니다. 새로운 문제는 핵심 알고리듬을 응용하여 풀 수 있으니까요. 이제 아셨나요? 왜 기술 면접(코딩 테스트)에서 알고리듬 문제가 단골손님처럼 나오는지?
모든 문제 해결에 토대가 되는 핵심 알고리듬. 그것이 바로 이 강좌에서 가르치는 내용입니다. POCU 아카데미가 지향하는 10년 후에도 살아남는 Top 1% 개발자. 그런 사람이 되려면 수박 겉핥기 식이 아닌 핵심 알고리듬의 동작 원리까지 확실히 알아야겠죠? 이 강좌에서 확실히 이해시켜드립니다. 이 강좌를 들으신 후 알고리듬 문제 사이트에 가서 본인의 실력을 테스트해보세요. 처음 보는 문제인데도 어렵지 않게 해법을 찾아내는 한 단계 업그레이드된 본인의 문제 해결능력을 느끼실 수 있을 겁니다. 앞으로 실무에서 마주치게 될 새로운 문제들도 큰 어려움이 없겠죠?
꼭 기억하세요. 업계가 원하는 프로그래머는 많은 문제의 정답을 외우고 있는 사람이 아니라 핵심 알고리듬의 확실한 이해와 응용을 통해 새로운 문제를 해결할 수 있는 사람입니다.
이 강좌를 성공적으로 수료한 프로그래머는 다음과 같은 실력을 갖추게 됩니다.
- 각 알고리듬의 장단점 및 성능에 대해 잘 이해하고 있다
- 어디에 어떤 알고리듬을 적용해야 하는지 안다
- 핵심 알고리듬을 응용해 새로운 문제를 풀 수 있다
기본기의 중요성을 강조하는 표현으로 '하나를 가르치면 열을 안다'라는 말이 있습니다. 이것저것 배우는 대신 핵심이 되는 기본 지식을 습득하여 문제 해결능력을 갖춘 진정한 프로그래머로 거듭나기를 바랍니다.
이 강좌의 대상
- 컴퓨터 공학의 기본기를 배우고 싶은 분들
- 프로그래머로서 평생 커리어를 꿈꾸는 분들
강좌 콘텐츠
- 알고리듬의 정의 (1:32)
- 영상 퀴즈
- 간단한 알고리듬 예 (5:05)
- 훌륭한 알고리듬이 갖춰야 할 자질 1 (8:48)
- 훌륭한 알고리듬이 갖춰야 할 자질 2 (5:49)
- 훌륭한 알고리듬이 갖춰야 할 자질 3 (9:40)
- 알고리듬의 효율성과 실제 성능 (7:36)
- 영상 퀴즈
- 알고리듬의 올바름 검증 (3:51)
- 복습 퀴즈
- 빅오 표기법 (6:47)
- O(1), O(N), O(N^2) (6:54)
- O(logN), O(NlogN) (4:52)
- '대략 그 정도'의 의미 (4:28)
- 영상 퀴즈
- 흔히 볼 수 있는 O 표기법의 성능 비교 (5:42)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 배열 (8:07)
- 스택, 큐 (5:59)
- 연결 리스트 (4:18)
- 해시 테이블, 해시 맵 (8:54)
- 자료구조의 시간 복잡도 정리 (3:34)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 복습 퀴즈 3
- 정리 (3:57)
- 재귀함수의 호출 과정 (8:33)
- 재귀함수의 장단점 (9:09)
- 꼬리 재귀 (9:40)
- 영상 퀴즈
- 꼬리 재귀 함수 작성하기 (5:55)
- 코드보기: 재귀 함수로 총합 구하기 (7:36)
- 복습 퀴즈
- 주먹구구식 알고리듬이란? (5:48)
- 간단한 주먹구구식 알고리듬의 예와 시간 복잡도 (5:26)
- 주먹구구식 비밀번호 깨기와 외판원 문제 (8:33)
- 기하급수적 알고리듬의 문제 (4:58)
- 복습 퀴즈
- P 분류 (4:35)
- NP 분류 (7:11)
- 영상 퀴즈
- P 또는 NP가 아니다! (4:17)
- NP 완전, NP 난해 (7:34)
- P vs NP 문제 (6:51)
- 복습 퀴즈
- 탐색 알고리듬 (4:59)
- 이진 탐색 (6:58)
- 영상 퀴즈
- 이진 탐색의 시간 복잡도 (10:33)
- 코드보기: 회전된 배열에서의 검색 (6:31)
- 정리 (6:49)
- 정렬 알고리듬 (5:42)
- 정렬 알고리듬의 안정성 (4:49)
- 대표적인 정렬 알고리듬 (3:57)
- 정렬 알고리듬 비교 (7:54)
- 상황에 따른 정렬 알고리듬 선택 (1:36)
- 버블 정렬 (2:40)
- 버블 정렬의 동작 모습 (4:32)
- 버블 정렬의 복잡도와 안정성 (2:52)
- 버블 정렬 코드 (2:36)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 선택 정렬 (5:07)
- 삽입 정렬 (5:43)
- 복습 퀴즈
- 퀵 정렬 (2:54)
- 퀵 정렬의 동작 모습 1 (7:11)
- 퀵 정렬의 동작 모습 2 (6:01)
- 퀵 정렬의 동작 모습 3 (2:03)
- 퀵 정렬 코드 - 재귀 (9:01)
- 퀵 정렬 코드 - 분할 (3:40)
- 퀵 정렬의 복잡도와 분할법 (7:25)
- 코드보기: 안정성 (3:43)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 병합 정렬 (9:31)
- 힙 정렬 (2:33)
- 힙 정렬의 동작 모습 (8:17)
- 코드보기: 배열 요소의 최소 차이 찾기 (3:45)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 정리 (4:19)
- 해시 알고리듬의 정의 (8:01)
- 해시 알고리듬의 분류와 속성 (2:09)
- 균일성 (8:33)
- 지역 민감 해시 (3:10)
- 효율성 (2:29)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 비암호학적 해시 함수 (6:07)
- 올바른 해시 함수를 고르는 법 (3:00)
- Lose Lose 해시 (5:47)
- Murmur, FNV-1 해시 (8:44)
- 체크섬 (4:34)
- 체크섬의 사용례 (5:43)
- 체크섬이 보장하는 것 (6:08)
- 패리티 비트 (2:14)
- 순환 중복 검사(CRC) (3:10)
- 영상 퀴즈
- CRC 계산법 (7:15)
- 복습 퀴즈
- 코드보기: CRC-32 체크섬 (4:10)
- 암호학적 해시 알고리듬 (9:08)
- 암호학적 해시 알고리듬의 추가 속성 (7:48)
- 생일 문제 (4:25)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 보안 이야기: 비밀번호 터는 법 (10:17)
- 보안 이야기: 비밀번호 덜 털리는 법 (9:36)
- 코드보기: 비밀번호 해시 만들기 (6:22)
- 복습 퀴즈
- 정리 (5:44)
- 암호화란? (5:15)
- 암호화의 역사 (8:41)
- 정수론 (5:21)
- 복습 퀴즈
- 대칭 키 암호화 (7:54)
- 복습 퀴즈
- AES 알고리듬의 구성 (5:34)
- AES의 내부 연산 1 (7:43)
- AES의 내부 연산 2 (6:26)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 복습 퀴즈 3
- 복습 퀴즈 4
- AES의 내부 연산 3 (1:57)
- 복습 퀴즈
- 코드보기: AES (6:53)
- 비대칭 키 암호화 (6:40)
- 비대칭 키 암호화의 두 가지 주요 용도 (3:37)
- 복습 퀴즈 1
- 복습 퀴즈 2
- RSA와 큰 소수 (8:54)
- 공개 키/비밀 키의 특수한 관계 (6:56)
- RSA 키 생성 (8:30)
- RSA를 이용한 암호화/복호화 (4:08)
- RSA 증명 1 (7:55)
- RSA 증명 2 (8:00)
- 증명에서 배울 것들 (2:08)
- 영상 퀴즈
- 대칭 키 vs 비대칭 키 암호화의 속도 비교 (1:40)
- 코드보기: RSA (3:43)
- 정리 (4:30)
- 트리 소개 (3:33)
- 트리 관련 용어 (9:08)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 복습 퀴즈 3
- 복습 퀴즈 4
- 복습 퀴즈 5
- 트리와 재귀 (3:06)
- 트리의 저장법 및 용도 (8:48)
- 이진 탐색 트리 (8:46)
- 영상 퀴즈
- BST 탐색 (6:12)
- 영상 퀴즈
- BST 탐색 코드 (3:17)
- BST 삽입 (3:01)
- 영상 퀴즈
- BST 삽입의 시간 복잡도 (1:08)
- 코드보기: BST 삽입 (5:45)
- BST 삭제 (10:23)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 중위 순회 (3:02)
- 전위 순회, 후위 순회 (8:23)
- 전위/중위/후위 선택법 (2:52)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 복습 퀴즈 3
- 코드보기: 전위 순회 (3:20)
- 코드보기: 깊은 트리 복사 (3:32)
- 레드-블랙 트리 (5:13)
- 레드-블랙 트리의 특성 (8:55)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 복습 퀴즈 3
- 복습 퀴즈 4
- 복습 퀴즈 5
- 복습 퀴즈 6
- 레드-블랙 트리의 삽입 방법 (9:24)
- 레드-블랙 삽입 문제 1~4 (9:21)
- 레드-블랙 삽입 문제 5~6 (8:28)
- 레드-블랙 삽입 문제 7 (7:36)
- 레드-블랙 삽입 문제 8 (4:29)
- 레드-블랙 삽입 전략 (4:35)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 복습 퀴즈 3
- 레드 블랙 트리의 삭제 방법 (9:22)
- 레드-블랙 삭제 문제 1~3 (5:14)
- 영상 퀴즈
- MC THE BLACK (4:46)
- 레드-블랙 삭제 문제 4~8 (9:23)
- 레드-블랙 삭제 문제 9 (2:54)
- 레드-블랙 삭제 전략 1 (6:40)
- 레드-블랙 삭제 전략 2 (4:39)
- 복습 퀴즈
- 정리 (5:04)
- 깊이 우선 탐색(DFS) (7:43)
- 깊이 우선 탐색 코드 (4:42)
- 너비 우선 탐색(BFS) (7:16)
- 깊이 우선 vs 너비 우선 (3:22)
- 그래프와 깊이/너비 우선 탐색 (9:21)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 복습 퀴즈 3
- 코드보기: 디렉터리 트리 출력하기 (2:48)
- 틱택토 게임 (6:35)
- 영상 퀴즈
- 틱택토 게임 트리와 전략 (미니맥스) (8:11)
- 틱택토 평가 함수 (6:44)
- 영상 퀴즈
- 미니맥스 알고리듬 (6:44)
- 깊이 제한 미니맥스 (8:49)
- 미니맥스 알고리듬의 성능 (4:34)
- 코드보기: 틱택토 (6:23)
- 정리 (4:52)
- 주먹구구식 배낭 문제 풀기 (9:24)
- 영상 퀴즈
- 메모이제이션 (7:05)
- 영상 퀴즈
- 메모이제이션을 사용한 피보나치 함수 (9:06)
- 타뷸레이션 (6:48)
- 동적 계획법으로 푸는 배낭 문제 1 (8:57)
- 영상 퀴즈 1
- 영상 퀴즈 2
- 영상 퀴즈 3
- 영상 퀴즈 4
- 동적 계획법으로 푸는 배낭 문제 2 (9:09)
- 영상 퀴즈 1
- 영상 퀴즈 2
- 영상 퀴즈 3
- 영상 퀴즈 4
- 동적 계획법을 적용할 수 있는 문제 (5:18)
- 동적 계획법으로 문제를 푸는 과정 (5:03)
- 코드보기: 배낭 문제 (3:29)
- 복습 퀴즈
- 그리디하게 푸는 배낭 문제 (8:26)
- 영상 퀴즈 1
- 영상 퀴즈 2
- 영상 퀴즈 3
- 쪼갤 수 있는 배낭 문제 (4:10)
- 그리디 알고리듬을 사용할 수 있는 경우 (3:17)
- 동전 교환 문제 1 (2:40)
- 영상 퀴즈
- 동전 교환 문제 2 (0:44)
- 영상 퀴즈
- 동전 교환 문제 3 (1:39)
- 인터벌 스케줄링 (8:57)
- 인터벌 스케줄링 증명 (5:15)
- 복습 퀴즈
- 압축 알고리듬의 큰 두 부류 (11:31)
- 양자화 1 (6:19)
- 양자화 2 (6:04)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 문자열 전송과 비트 수 (1:18)
- 영상 퀴즈
- 전송 데이터 비트 수 줄이기 (4:21)
- 허프만 코딩 (4:09)
- 허프만 트리 만들기 (5:00)
- 복습 퀴즈
- 허프만 디코딩 (3:54)
- 복습 퀴즈
- 정리 (3:26)
- 그래프의 정의 (8:35)
- 그래프의 예 (8:19)
- 복습 퀴즈
- 그래프의 종류 (9:35)
- 그래프의 다양한 표현 방법 (4:10)
- 인접 행렬 (4:00)
- 영상 퀴즈
- 방향 그래프의 인접 행렬 (1:11)
- 영상 퀴즈
- 인접 행렬의 장단점 (2:41)
- 인접 리스트 (4:42)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 그래프의 깊이 우선 탐색 (9:33)
- 올바른 노드 기억법 (3:37)
- 영상 퀴즈
- 후위 순회 DFS (6:10)
- 영상 퀴즈
- 그래프 DFS의 시간 복잡도 (1:24)
- 복습 퀴즈
- 위상 정렬 (8:56)
- DFS를 사용한 위상 정렬 (8:59)
- 코드보기: POCU 수강 순서 (4:08)
- 복습 퀴즈
- 강한 결합 요소 (6:01)
- 영상 퀴즈
- 위상 정렬과 강한 결합 요소 (9:09)
- 코사라주 알고리듬 (6:09)
- 코사라주 알고리듬의 이해 (7:54)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 정리 (4:56)
- 그래프의 너비 우선 탐색 (4:37)
- 영상 퀴즈
- 그래프 BFS의 시간 복잡도 (0:16)
- 최단 경로 찾기 (6:14)
- BFS로 최단 경로 찾기 (7:03)
- 다익스트라 알고리듬의 기초 (7:59)
- 다익스트라 알고리듬 1 (5:27)
- 다익스트라 알고리듬 2 (4:47)
- 다익스트라의 시간 복잡도 (6:31)
- 다익스트라와 음의 가중치 (3:15)
- 복습 퀴즈
- 코드보기: 우선순위 큐를 사용한 다익스트라 알고리듬 (8:07)
- A* (8:17)
- A*의 노드 선택 기준 (5:18)
- A* 알고리듬 (9:23)
- h(n) 함수에 대한 이해 (5:57)
- A*의 중복 방문과 시간 복잡도 (5:52)
- 복습 퀴즈 1
- 복습 퀴즈 2
- 플로이드 워셜 알고리듬의 기초 (7:42)
- 플로이드 워셜 공식 (3:32)
- 플로이드 워셜 알고리듬 1 (7:42)
- 플로이드 워셜 알고리듬 2 (6:32)
- 플로이드 워셜의 복잡도 (1:15)
- 복습 퀴즈
- 정리 (6:58)
- 최소 신장 트리(MST) (7:34)
- 영상 퀴즈
- MST 알고리듬의 기본 원리 (6:40)
- 크러스컬 알고리듬 (6:39)
- 서로소 집합(disjoint set) (6:33)
- 복습 퀴즈
- 코드보기: 크러스컬 알고리듬 (5:10)
- 외판원 문제(TSP) (7:13)
- 우리가 볼 TSP 그래프 (6:42)
- TSP 2-근사 알고리듬 (4:39)
- MST에서 해밀턴 순환 만들기 (9:27)
- TSP 변형과 꼼수 (9:26)
- 복습 퀴즈
- 흐름 네트워크와 최대 유량 (9:47)
- 수요와 유통 문제 (3:33)
- 에드몬드-카프 알고리듬 1 (8:07)
- 에드몬드-카프 알고리듬 2 (10:21)
- 복습 퀴즈
- 기타 그래프 문제들 (1:53)
- 정리 (4:25)