Algorithm

[SWEA] 그래프의 기본과 탐색

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현 그래프의 기본과 탐색 강의를 보고 정리한 글입니다 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYG3y62EcDFAVT SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 그래프의 기본과 탐색 목차 01 그래프 기본 02 그래프 탐색 03 상호배타 집합들 01 그래프 기본 그래프(Graph)란? 객체들과 이들 사이의 연결 관계를 표현하는 것으로 정점(Vertex/Node)들의 집합과 이들을 연결하는 간..

[SWEA] 탐욕 알고리즘(Greedy Algorithm)

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 완전 검색 강의를 보고 정리한 글입니다 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYEGw61n8DFAVT# SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 탐욕 알고리즘(Greedy Algorithm, 그리디 알고리즘) 목차 01 탐욕 알고리즘 02 동전 거스름돈 문제 03 배낭 문제 04 활동 선택 문제 05 Baby-Gin 다시 보기 01 탐욕 알고리즘 탐욕 알고리즘(Greedy Algor..

[SWEA] 동적 계획법(Dynamic Programming)

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 완전 검색 강의를 보고 정리했습니다 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYNNbK29EDFAVT# SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 동적 계획법(Dynamic Programming, 다이나믹 프로그래밍) 목차 01 피보나치 수 02 수학적 귀납법과 비둘기 집의 원리 03 메모이제이션과 동적 계획법 04 동전 거스름돈 문제와 이항 계수 문제 01 피보나치 수 피보나치 수(Fi..

[Algorithm : 알고리즘] 06 Dynamic Programming: DP

목차 0. Introduction: 동적프로그래밍 소개 1. 0/1-Knapsack 2.Weighted interval scheduling 3. Multistage Graph 4. All pairs shortest path - Floyd's algorithm

[Algorithm: 알고리즘] 05 Greedy Algorithm

목차 0. Basics: 그리디 알고리즘 기초 1. Minimum Spanning Trees : 최소 신장 트리 - 신장 트리 - 최소 비용 신장 트리 - Kruskal's Algorithm( Original ver.) : 크루스칼 알고리즘 - Kruskal's Algorithm( Improved ver.) : 크루스칼 알고리즘-성능향상 버전 - Prim's Algorithm : 프림 알고리즘 2. Knapsack Problem : 배낭 문제 3. Job sequencing with deadline : 데드라인이 있는 작업 순서 문제 - 문제 - 해결 전략 4. Optimal merge patterns : 최적 병합 패턴 - 문제 - 해결 전략 - Huffman encoding의 등장 배경 - Huffm..

[Algorithm: 알고리즘] 04 Graph

목차 0. Introduction: 그래프 소개 1. What is graph? : - 그래프의 정의 - 그래프의 종류 - 그래프의 표현 - 성능 분석 - 그래프 알고리즘의 분류 2. DFS : 무방향 그래프에서의 깊이우선탐색 - 자료구조별 탐색법 - DFS 3. DFS : 유향 그래프에서의 깊이우선탐색 - 엣지의 종류 - Directed Acyclic Graph(DAG) : 유향 비순환 그래프 4. Strongly Connected Components(SCC) : 강한연결요소 - 유향그래프에서의 연결성 - 알고리즘 5. Biconnected Components : 이중연결 요소 - Articulation point : 분절점 - Biconnected graph : 이중결합 그래프 - BCC에서 A-po..

[Algorithm:알고리즘] 03 Divide and Conquer

목차 0. Introduction: 분할정복 소개 - 에피소드 - DnC를 이용한 토너먼트 알고리즘 - DnC의 키 아이디어 - DnC의 추상 알고리즘 - DnC의 성능 분석 1. Recurrence Relation: 점화식 - 연습 문제 1) Characteristic equation(특성 다항식) 2) Repeated substitution(반복 치환) 3) Master theorem 2. DnC Algorithm : 분할정복 알고리즘 - 토너먼트 - 이진탐색 3. Multiplication : 곱셈 - DnC를 이용한 곱셈 알고리즘 4. Sorting : 정렬 - 병합정렬 - 퀵 정렬 5. Medians : 중앙값 - K번째로 작은 값 찾기 6. Matrix Multiplication : 행렬 곱셈

[Algorithm: 알고리즘] 02 Prologue

목차 1. Introduction: 알고리즘 소개 - 알고리즘 - 블록체인 2. Performance Analysis: 성능 분석 - Computational complexity(계산 복잡도) - Common running times - Recurrence relation(점화식) 1) Characteristic equation(특성 다항식) 2) Repeated substitution(반복 치환) 3) Master theorem 3. Fibonacci :피보나치 수열 소개