(23.03.13) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 3.1 why graphs? 3.2 Depth-fist search in undirected graphs 3.3 Depth-first search in directed graphs Depth-first search in undirected graphs예시 풀이 과정 Depth-first search in directed graphs 예시 풀이 과정

(23.03.10) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 2.4 medians (+ quick sort) Medians quick sort quick sort python code def quick_sort(input, start, end): if start >= end: return input pivot = start left = start+1 right = end while left right: input[right], input[pivot] = inpu..

(23.03.07) algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf 정리한 내용 2.1 multiplication 2.2 recurrence relations 2.3 merge sort Divide-and-Conquer algorithms divide: 문제를 sub-problem 으로 쪼갠다. conquer: cub-problem을 recuresively 하게 해결한다. combine: sub-problems의 solutions를 combine 한다. (+ 예전에 수업들으면서 정..

(2021.12.14) 알고리즘 수업 들으면서 정리하기 26탄 w15-2 녹강 + 보충강의 정리 저번 시간에 배우던 solvable problem 나머지 부분에 대해서 배웠따 개념이 너무 뒤죽박죽함 ▷ solvable problems > provably intractable problems (infeasible) : 해결하기 어려움이 입증된 문제 > probably intractable problems : 아마도 해결하기 어려울 것 같은 문제 ---> NP > tractable problems (feasible) : 다루기 쉬운 문제 --> P ▷ deterministic turing machine(DTM) : 주어진 state, 주어진 input 에 대해서 하나의 possible action만 존재하는..

(2021.12.08) 알고리즘 수업 들으면서 정리하기 25탄 w15-1 실강 정리 halting problem 을 배웠다. NP 정의도 배웠다. 교수님이 이 부분을 굉장히 자세하게 천천히 많이 설명해주셔서 오늘도 진도를 많이 안나갔다 교수님 추천 영상 https://www.youtube.com/watch?v=92WHN-pAFCs&feature=youtu.be Halting Problem (unsolvable problem) 프로그램 P와 input i 가 있고, 프로그램 P에 input i 를 넣는다. 그러면 두가지의 상황이 발생한다. > P halts on i > P runs forever on i 프로그램 P와 input i 가 있을 때, P가 i에 halt인지 아닌지를 알아낼 수 있는 프로그램 H..

(2021.12.07) 알고리즘 수업 들으면서 정리하기 24탄 w14-2, w14-3 녹강 정리 TM transition function, crashing, halting 에 대해 배웠다 저번 실강이랑 겹치는 내용이 많아서 정리할 내용이 거의 없다 TM transition function (여기서 Q의 정의부분이 틀렸다. halt 를 포함하지 않는다고 되어있는데 halt state도 포함한다) 이렇게 표현할 수 있다 example) Processing a string > string의 가장 왼쪽과 가장 오른쪽에는 blank symbol을 두고, blank가 아닌 string의 가장 첫번째 cell에 tape head를 두고 과정을 진행한다. > input string w에서 transition 과정이 진..

(2021.12.01) 알고리즘 수업 들으면서 정리하기 23탄 w14 실강 NP-completeness 내용 시작 계산 복잡도, 튜링 기계에 대해 배웠다 NP-completeness Computational Complexity > 알고리즘은 특정 알고리즘의 performance 특성 (성능 특성)에 대한 연구이다. > 계산 복잡도(계산 이론)은 알고리즘보다는 문제의 특성에 대한 연구이다. 우리는 문제를 solvable problem과 unsolvable problem으로 나눌 수 있다. > unsolvable problem은 다시 세가지로 나뉜다. 1. Unsolvable problems ---> halting problem 2. Solvable problems a. Provably intractable..

(2021.11.30) 알고리즘 수업 들으면서 정리하기 22탄 w13-2 녹강 N-Queens problem에 관한 내용이다 지금까지 배운 것 중에서 개념은 정말 쉬운 것 같은데 구현하는게 어려울 것 같다.. 시간나면 구현해봐야지.. N-Queens problem : backtracking 기본형 problem이다 n x n의 체스보드에서 n개의 서로다른 queen들이 서로 공격하지 않는 자리에 어떻게 둘 수 있는지를 물어본다. 예를 들어 n=4 라고 했을 때, 4개의 Queen들이 위치할 수 있는 전체 경우의 수는 16 x 15 x 14 x 13 = 43680 가지이다. 그러나 우리는 이를 더욱 간단하게 알아 볼 수 있다. --> search space를 줄여나가면서!! 기본적인 sketch idea는..

(2021.11.23) 알고리즘 수업들으면서 정리하기 21탄 w12-2 녹강, w12-3 녹강, w13-1 실강 maximum flow, network flow 내용이다. Flow network Maximum-flow problem : flow network G가 주어지고, source s, target t, capacity c 가 주어질 때, value가 최대인 flow를 찾는 문제 Max-flow min-cut theorem : max-flow의 값과 min-cut의 값이 같다. The Ford-Fulkerson method The Ford-Fulkerson method가 the maximum-flow problem을 해결한다. input: a flow network G, source s, targe..

(2021.11.17) 알고리즘 수업들으면서 정리하기 20탄 w11-2 녹화강의, w12-1 실강 minimum spanning tree와 prim algorithm 내용이다. Minimum Spanninng Tree 최소 신장 트리 --> 줄여서 MST input: 방향성 없는 연결 그래프 connected, undirected graph G=(V,E) (각 edge 들에 weigth가 있음) output: acyclic subset T of the edges of G (G의 모서리들의 cycle 없는 subset) Model은 undirected graph G=(V,E) 임 각 edge (u,v) ∈ E 에는 weight w(u,v) 가 있음 (u,v ⊂ V) acyclic T⊆E 에 대해서 모든 노..

(2021.11.12) 알고리즘 수업들으면서 정리하기 19탄 w10-3 녹화강의, w11-1 실강 BFS,DFS 내용이다. Network flow graph 알고리즘 - Breadth-first search - Depth-first search - Minimum spanning tree (Prim's algorithms) - Maximum flow (The Ford-Fulkerson method) graph G=(V,E) 로 표현한다. - V는 vertices 의 집합 (G.V) - E는 edges 의 집합 (G.E) G는 방향성일 수도 있고, 무방향성일 수도 있다. (directed, undirected) 보통 graph는 인접리스트나 인접행렬로 표현한다. BFS(Breadth-first search)..

(2021.11.08) 알고리즘 수업들으면서 정리하기 18탄 w10-2 녹화강의 huffman code 개념, 만드는 방법, greedy 알고리즘 Huffman codes each character를 binary charcter code로 디자인하는 것 optimal prefix code 라고도 한다. huffman code는 빈도수에 따라서 설정해준다. huffman code는 variable-length code이며, fixed-length code보다 효율적이다. (fixed-length code는 3비트로 표현한다--> 많은 저장용량을 차지한다.) prefix-free code (prefix code) huffman code의 가장 큰 특징은 prefix-free code(prefix code)이..

(2021.11.04) 알고리즘 수업들으면서 정리하기 17탄 w10-1 실시간 강의 greedy algorithm에 관한 내용과 huffman code 설명 조금(huffman은 다음 동영상정리에) activity selection 내용 전에 greedy 알고리즘 설명해주신 부분의 연장선 같음 Greedy algorithm greedy algorithm은 언제나 optimal solution을 도출해내는 것은 아니다. greedy algorithm으로 해결했을 때, 그 결과가 optimal solution이 아닐 수도 있다는 것이다. 어떠한 상황에서 greedy로 풀면 optimal한 결과가 나온다 라는 general한 접근법이 없기 때문에 greedy algorithm은 해봐야 알 수 있다. greed..

(2021.11.03) 알고리즘 수업들으면서 정리하기 16탄 w9-2 강의 activity selection을 greedy algorithm으로 푸는 방법을 배웠당 Activity Selection : greedy algorithm d.p는 subproblem이 두개가 나오지만, greedy algorithm은 subproblem이 하나만 나온다. aj와 am이 다른 경우에 Ak'를 정의하게 되는데 Ak'은 Ak에서 aj를 빼고, am을 넣은 것이라고 생각하면 된다. Ak'의 activity들이 서로 오버랩되지 않는다는 것이 중요하다. am은 Sk에서 가장 빨리 끝나는 activity이고, aj는 Ak에서 가장 빨리 끝나는 activity이다. 그렇기 때문에 am이 aj보다 빨리 끝날 것이다.(am이 더..

(2021.10.27) 알고리즘 수업들으면서 정리하기 15탄 Activity selection :공통의 자원에 대한 독점적인 사용을 필요로 하는 활동 N개가 있는데 이를 어떻게 스케줄링 할 것인가 하는 문제를 말한다. ex) 교실의 대한 사용을 스케줄링 하는 문제 Problem: 여러 competing activities 사이의 스케줄을 조정하는 것 ( 각 activity에 대해서 시작과 종료시간은 주어짐) Goal: nonoverlapping activities 의 largest possible set을 선택함 이를 이제 dynammic programming 기법으로 접근해보겠다 greedy algorithms으로 접근하는 건 다음 시간..