뭘 배웠지?

알고리즘 강의 마무리 하며 정리 ✅ 이론적으로 문제 해결 관점에서 반드시 만족해야 하는 알고리즘 조건 유효성 명확성 유한성 ✅ 선형 리스트의 한 쪽 끝에서만 자료의 삽입과 삭제가 이루어지는 자료구조 스택 ✅ 길이가 k인 이진트리가 가질 수 있는 노드의 최대 개수 2k -1 ✅ 높이가 4인 이진트리가 최대 개수의 노드를 갖을 때, 단말 노드의 개수 8개 ✅ 연결 리스트의 특정 노드에서 선행, 후행 노드 양쪽에 대한 접근이 가능한 것 이중 연결 리스트 ✅ 그래프 G에서 정점 v1에서 정점 vn 까지 경로란? 간선(v1, v2), (v2, v3), ... (vn-1, vn)으로 연결된 정점의 순서 리스트 v1, v2, ..., vn을 의미 ✅ 알고리즘의 시간 복잡도는 무엇의 함수일까? 입력 데이터의 크기 ✅ ..

알고리즘 12강을 보며 배운내용 탐색 데이터 형태 리스트, 트리, 그래프 등에서 원하는 데이터 찾는것 내부 탐색 vs 외부 탐색 탐색 연산 탐색 + 초기화(정렬), 삽입, 삭제 이번 강의에서는 순차 탐색 이진 탐색 탐색 트리 -> 이진 탐색 트리 다음 강의에서는 균형 탐색 트리(흑적트리, B-트리) 해싱 순차 탐색 배열이나 연결리스트 형태로 주어진 원소들을 처음부터 차례대로 비교하면서 원하는 값 찾는 방법 ⌛ 시간복잡도 탐색: O(n) 삽입: O(1) 삭제: O(n) ✨특징 모든 리스트에 적용 가능 원소가 순서 없이 저장된 경우 적합하다 데이터 큰 경우 부적합 알고리즘 간단 반복문 돌려서 앞에서부터 비교해주면 된다. 삽입 연산(배열) 맨 뒤에 붙여주면 된다 🤖삭제 연산(배열) 맨 마지막 데이터를 해당 원..

알고리즘 11강을 보며 배운내용 오늘은 알고리즘 10강에서 알아본 버블정렬, 선택정렬, 셸 정렬보다 향상된 성능의 알고리즘을 알아본다 합병 정렬 1. 배열을 쪼개지지 않을 때까지 반으로 나누고 2. 합쳐주며 정렬 이미 4강에서 알아봤다(4강 링크) ✨ 특징 안정적 알고리즘 10강, 11강의 비교 기반 알고리즘 7개 가운데 제자리 정렬 아닌건 이녀석 하나 ⌛ 시간 복잡도 O(nlogn) 퀵 정렬 1. 피벗을 중심으로 왼쪽, 오른쪽으로 나누고 정렬 ⌛ 시간 복잡도 피벗 임의성 보장 하면 O(nlogn) 최악은 O(n2) ✨ 특징 제자리 정렬 알고리즘 힙 정렬 1. 일차원 배열 => 힙으로 변환 2. 힙의 최댓값 삭제 3. 힙 재구성 최대 힙: 내림차순 정렬 최소 힙: 오름차순 정렬 !! 여기선 내림차순 최대..

알고리즘 10강을 보며 배운내용 정리(TL;DR) 밑의 4가지 정렬 모두 시간 복잡도 On2 1. 버블 정렬 1. 인접한 두 값 비교 2. 왼쪽 값이 크면 자리 바꾸기 안정적 정렬 ✅ 제자리 정렬 ✅ 2. 선택 정렬 1. 최솟값 찾고 2. 작은 값부터 나열 안정적 정렬 ❌ 제자리 정렬 ✅ 3. 삽입 정렬 1. 정렬 부분(첫 번째 값), 미정렬 부분(두 번째 값부터)으로 잡고 2. 정렬 부분 뒤부터 비교 3. 정렬 부분의 값보다 크거나 같으면 오른쪽에 삽입 안정적 정렬 ✅ 제자리 정렬 ✅ 4. 셸 정렬 삽입 정렬을 개선하고자 나온 정렬 삽입 정렬을 크기가 변하는 부분 배열로 실행 안정적 정렬 ❌ 제자리 정렬 ✅ 정렬 내부 정렬 모든 데이터가 주기억장치에 저장 외부 정렬 보조기억장치에 저장하고 필요할 때 주..

알고리즘 9강을 보며 배운내용 이번 강의는 10강부터 배울 정렬 알고리즘에 들어가기전에 1강부터 8강까지 배운 내용 리마인드 시간 정리(TL;DR) 1. 기본 자료구조 => 모든 구현은 배열과 연결리스트 2. 알고리즘 기초 => 대표적인 3가지 알고리즘, 점근 성능 3. 분할정복 => 이진 탐색, 퀵 정렬 4. 분할정복 => 합병정렬, 선택 문제 5. 동적 프로그래밍 => 동적 프로그래밍 원리, 연쇄 행렬 곱셈 6. 동적 프로그래밍 => 편집 거리, 모든 정점 최단 경로, 저울 문제 7. 욕심쟁이 => 동전 거스름돈, 배낭문제, 신장트리 8. 욕심쟁이 => 한 정점 최단 경로, 데이크스트라, 작업 스케쥴링, 작업 선택, 허프만코딩 1강 기본 자료구조 정의, 특징, 동작 등을 알아두자 배열, 연결리스트 스..

알고리즘 8강을 보며 배운내용 들어가기 전 7강 욕심쟁이 방법 강의를 듣고 욕심쟁이 알고리즘 문제를 풀었는데 강의를 들을 때처럼 꽤 직관적으로 해결됐다 포인트는 1. 최솟값 or 최댓값 합이나 축적된 값을 반환해야 된다면 2. 반복문 or 동적 프로그래밍처럼 값 저장 상기는 이렇게 마치고 8강 시작!! 정리(TL;DR) 각 단계에 충실하는 욕심쟁이 알고리즘으로 문제를 풀 수 있어보인다 최단 경로를 생각하면 지도 앱이 생각나기도 작업 스케쥴링, 작업 선택 문제를 욕심쟁이 방법을 모르고 처음 접했을 때 어버버 했던 기억도 난다 알고나니 간단하구나 한 정점에서 가는 모든 정점의 최단 경로 => Dijkstra 알고리즘 모든 작업 마무리하는 최소 기계 개수 구하기 => 작업 스케쥴링 한 기계로 할 수 있는 최대..

알고리즘 7강을 보며 배운내용 동적 프로그래밍을 6강으로 정리하고 Greedy(욕심쟁이) 알고리즘을 7강, 8강에 걸쳐 배운다 7강에서는 욕심쟁이 알고리즘에 대한 개념과 원리, 특징을 알아보고 예를 살펴본다 정리 그리디(욕심쟁이) 방법은 동적 프로그래밍 방법보다 조금 더 간단하게 다가왔다 최소를 구할 땐 최소의 값을 택하고 최대를 구할 땐 최대의 값을 택하는 직관적인 방법으로 보인다 이것 역시 유명한 알고리즘을 풀어보고 변형으로 넘어가면 꽤 이해가 되지 않을까 싶다 욕심쟁이 방법 전후 선택과 상관없이 해당 단계에서 가장 최선이라고 여겨지는 해를 선택해서 전체적인 최적해를 구한다 탐욕적 방법, 그리디(Greedy) 라고도 불린다 동적 프로그래밍 vs 욕심쟁이 공통 최적화 문제에 주로 사용 최적성의 원리가 ..

알고리즘 6강을 보며 배운내용 5강에 이어 6강도 동적 프로그래밍! 동적 프로그래밍의 포인트는 문제를 작은 문제로 쪼개고, 작은 문제에 대한 점화식을 이용해서 값을 구하고 저장 저장된 값과 점화식을 반복해서 이용해서 마지막까지 가서 문제의 답을 구하는 것 BUT 점화식 구하는게 쉽지않다 그럼 어떻게 할까? 유명한 점화식 그러면 우선은 유명한 점화식 이해를 먼저 하자 유명 점화식이 아무래도 여러 문제에 적용되어 있을 것 자주 보고, 사용하며 제대로 이해하면 다른 문제에 조금씩 변형하면서 사용가능할 것 같다 스트링 편집 거리 X = x1x2 ... xn Y = y1y2 ... ym 문자열 X를 Y로 변환하는데 필요한 편집 연산의 최소 비용 구하는 것 삽입, 삭제, 변경에 대한 최소 비용 X = SNOWY Y..

알고리즘 5강을 보며 배운내용 앞에서 분할정복에 대해 2강에 들었는데 동적 프로그래밍 알고리즘도 방법, 원리 특징을 2강에 걸쳐 배운다 동적 프로그래밍 알고리즘 원리 문제 크기가 작은 문제에 대해 해를 구하고, 크기가 조금 더 큰 문제의 해를 단계적으로 구해가는 상향식 접근 방법(bottom up) 작은 문제의 해는 테이블에 저장 해놓고 재사용 해를 구축하는 테이블을 이용한다고 해서 동적 프로그래밍이라 한다 소문제들 서로 독립적일 필요 없고, 중복되는 부분 존재한다 주로 최적화 문제 최적화 문제에 사용한다 최솟값, 최댓값, 피보나치 수열, 연쇄 행렬 곱셈 ... 사용하려면 최적성의 원리(Principle of optimality) 만족해야 동적 프로그래밍을 적용할 수 있다 => 주어진 문제의 최적해는 소..

알고리즘 4강을 보며 배운내용 분할정복 알고리즘 2탄 => 분할정복 알고리즘 1탄: 이진 탐색, 퀵 정렬 복습 순환적으로 문제를 하향식 접근으로 푼다 분할 - 정복 - 결합으로 문제를 푼다 분할된 문제는 크기만 작고 원래 문제와 같다 오늘은 합병정렬과 선택문제 합병 정렬 분할 정복 방법으로 정렬 분할, 정복, 결합을 잘 지키는 정렬 n만큼 저장장소(왼쪽배열, 오른쪽배열)가 필요하다 ⌛ 시간 복잡도 O(nlogn) ✨ 방법 분할: 동일한 크기로 나누기 정복: 부분배열을 순환적으로 정렬 결합: 합병해서 정렬된 배열 만든다 🤖 코드 // 합병 정렬 JavaScript function mergeSort(원배열, 길이) { if(n > 1) { let mid = Math.ceil(길이 / 2) let 왼쪽배열 =..