Python Algorithm class

1주차 : 개론, 시간복잡도

log n 과 √n 비교

배울 내용 : 간단한 정렬 알고리즘(선택, 버블, 삽입)

문제의 해를 부분문제(subproblem, 작은 크기의 입력에 대한 동일한 문제)의 해를 이용하여 해결하는 방법

세 개의 막대기 1, 2, 3이 있고, 서로 다른 크기의 n개의 원반들이 막대기 1에 크기순서(위에서부터 아래로 크기가 증가)대로 놓여있다. 다음 규칙을 지키면서 막대기 1에 있는 모든 원반들을 막대기 3으로 옮겨라.

다룰 내용 : 분할과 정복 방법

문제 : 어떤 회사의 주식 가격이 날짜 별로 n개 주어져 있다. 한 번 주식을 사서 한 번 팔 수 있다고 하자. 얻을 수 있는 최대 이득을 구하는 프로그램을 작성하시오.

병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)

(2) 정렬 알고리즘의 하한계(lower bound)

두 원소의 키 비교에 의한 정렬 방법이 아닌 정렬 알고리즘으로 기수정렬과 계수정렬이 있다.

동적 계획법에 대하여 알아보자

Dynamic Programming (동적 계획법 - 2) >4. 양의 정수 n의 합 표현 방법 >5. 거스름 돈 나누어 주는 방법 >6. Weighted Interval Scheduling

Weighted Interval SchedulingWe are given a set of intervals(구간) : "I" = {(si, fi) | i = 1, ..., n} (si = 시작시간, fi = 끝나는 시간)Our goal is to find a subse

Dynamic Programming (동적 계획법 - 4) > 8. 연속하는 수들의 최대 합 구하기 > 9. 그리드(Grid)에서 경로 찾기 > 10. LCS(Longest common subsequence) 문제 8. 연속하는 수들의 최대 합 구하기

Assembly line scheduling

개요, 동전 교환 문제, 평균적인 대기 시간을 최소로 하는 작업 스케쥴링, 회의실 배정, 문제배낭 문제

그래프의 정의, 용어 설명, 그래프 표현

3\. Graph 표현

깊이 우선 탐색 (Depth First Search)과 너비 우선 탐색 (Breadth First Search)

(2) 너비 우선 탐색(Breadth First Search)

(1) 위상정렬(2) 에지에 가중치가 있는(weighted) DAG에서 최장경로(longest path) 문제

오늘 배울 내용(1) 최단경로(shortest path) 문제, (2) 최소 스패닝트리(minimum spanning tree)

오늘 배울 내용 : Prim 알고리즘(욕심쟁이 알고리즘, )Kruskal 알고리즘(욕심쟁이 알고리즘), 상호 배타적 집합의 처리

백트래킹 알고리즘

NP-Complete

중복된 데이터가 없을 때는 기본적인 이진 탐색을 통해 쉽게 구할 수 있으나, 중복된 데이터들이 있는 경우엔 구할 수 없다.

2021년 11월 20일 토요일에 HUFS CODE FESTIVAL이 열린다는 소식을 듣고 함께 알고리즘 스터디를 하는 친구들에게 알려 함께 함가하자고 말했다.그러나 한 명은 카카오 브레인 2차 테스트를 그 날 봐야했고, 다른 한 명은 까먹고 신청을 못한 모양이었다.