문제 A,B,C 로 구성할 수 있는 부분집합을 모두 구하시오. 해결 방법 부분집합의 모든 경우의 수가 2^(원소의 개수) 인 것은 학교에서 배우는 내용이다. 코딩 문제에서도 부분집합과 순열, 조합의 경우 해당 개념을 사용하는데, 그 이유는 다음 사진과 같다. A,B,C를 각각 on off 개념으로 1,0 으로 나타낼 수 있다. 즉, 파이썬에서는 for i in range(2**3) 으로 모든 부분집합을 구할 수 있는 것이다. 예시 코드 비트를 사용하여 부분집합을 구하는 예시입니다. # 비트를 활용한 부분집합 구하기 letters = ['a', 'b', 'c'] for i in range(1 0 0 0 => 공집합 # ['a'] | => (i = 1) => 0 0 1 => (j = 0)에서 걸려 'a'가 ..
공부할 때 참고한 블로그 : https://sepang2.tistory.com/ 학습기록 sepang2.tistory.com Ch:9: Theory of NP 다항시간 알고리즘이란 worst case 시간복잡도가 n에 대한 다항 함수로 구성되는 알고리즘이다. o(n^k) (K≥0) 다만 n^3을 넘어가는 다항시간 알고리즘 또한 실제 사용하기에는 복잡도가 커다는 평가가 있다. solvable problem 컴퓨터가 해결할 수 있는 해결할 수 있는 알고리즘이 입증되어 있는 경우를 말한다. polynomial of expoenential시간 복잡도를 가진다. unsolvable problem 미래에도 해당 문제에 대한 해결 알고리즘을 개발하는게 불가능하다는 것이 증명된 문제들을 말한다. intractable ..
Ch:8: Theory of computational complexity: Searching problem and selection problem as a case study 탐색문제의 lower bound도 확인해보자 binary search 알고리즘 사용 = worst case = logn인 효율적인 알고리즘 searching 문제는 여러개의 key field에서 원하는 key를 검색하는 과정이다. 즉, sorting 알고리즘과 유사하게 comparison이 base가 되는 알고리즘이다. = tree구조로 모델링이 가능하다. d = depth = comparison 횟수 search problem의 lower bound 도 logn이므로 binary search보다 더 빠른 알고리즘은 존재하지 않는다..
Ch:7: Theory of computational complexity: Sorting problem as a case study computational complexity theory = 계산 복잡도 이론 특정 문제를 해결하기 위해 필요한 시간복잡도를 계산하는 것이 아니라 동일한 문제를 해결하는데 사용될 수 있는 모든 알고리즘에 대해 시간 효율성에 대한 하한을 결정하는 이론 그렇기 위해서 주어진 제한된 자원으로 해결할 수 있거나 해결할 수 없는 문제를 분류함. 최대 T(n)으로 문제의 시간복잡도를 보이는 상한(upper bound)의 증명은 쉽지만(T(n)인 특정 알고리즘이 있다는 것만 보여주면 되기 때문) 하한을 증명하는 것은 어렵다(lower bound) 왜냐하면 lower bound는 주어진 ..
chap6 Branch and bound algorithm design approach 0-1 knapsack 문제에 대해서 항상 앞서있지는 않지만 많은 경우의 input 에 대해 유리한 결과를 보여준다. tree를 탐색하는 순서를 정해두고 하지않는다. 오직 optimization 문제를 위해 설계된 알고리즘이다. breadth first search = queue data structure로 구성된 level order traversal로 kanpsack 문제 해결하기. BFS = 너비 우선 탐색 시작노드에서 시작하여 가까운 노드부터 우선적으로 탐색하는 알고리즘 recursive function을 사용x BFS 동작 과정 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼낸 뒤에 해당..
chap5 Backtracking Algorithm design approach 해가 될 가능성이 있는지 promising을 확인한 수 필요없으면 가지치기 prune을 한다. DFS = 깊이 우선 탐색 DFS는 스택 자료구조 또는 재귀 함수를 이용한다. DFS backtracking 푸는법 Tree 형태로 visualize한다 branch를 제거하는 메커니즘을 설계한다. 조건에 따라 단일 leaf node에 도달하거나 여러개의 leaf node에 도달할 것이다. 이후 조건에 따라 이중에서 하나를 선택한다. DFS 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 ..
chap4 Greedy algorithm design pattern =과거 미래에 상관없이 현재 순간에 최선을 고르는 방식. = local optimal 해결책임 , global optimal solution이 아닐 수 있음. greedy 알고리즘의 반복순서 selection step = solution set에 들어갈 현재의 최선을 선택함 feasibility check = 타당한지 확인함(가능한지) solution checking step = 새로운 solution set이 문제를 만족하는 해답인지 확인. global optimal solution을 얻기 위해 local optimal을 선택하는 과정 Minimum spanning Tree 문제 = 최소 비용 신장트리 Select an edge Cyc..
chap3. Dynamic programming(planning) 작은 문제가 반복되는 경우에 작은 문제를 계산하여 한번 계산한 값을 저장하고 검색 후 재사용하는 방식. = recomputing 대신 look up table 만들기. fibonacci number DP의 핵심 스텝 DP는 schedule을 사용하여 문제를 효율적으로 풀지만 메모리를 추가로 사용하고 divide and conquer는 문제를 blindly(무턱대고) 풀며, 스케줄링과 planning이 없다. - 겹치는 계산이 없을 때 쓰면 좋음. Compute binomial coefficient=이항계수 문제 계속 이전 항끼리의 합을 구하는 방식이라 겹치는(over lapping)부분과 반복되는 계산이 많다. basic operation..
chap2. Divide and conquer problem을 subproblem으로 나누어 따로 풀고 합치는 방식. = top→ down approach 3-basic step Divide conquer(solve subP) if necessary combine binary search = sorted input = T(n) = T(n/2) -> time complexity = logn every time complexity recurrence relation Master Theorem 재귀방식에 적용 가능한 time complexity 구하는 법 재귀함수가 몇번 불렸는지(a) 몇 개로 나누어 푸는지(b)를 구하고, 함수 T(n)의 재귀 외의 나머지 함수에 대해서 n^d 형태로 만들어 d를 구한다. 그..
알고리즘 중간범위 알고리즘의 정의, 수학적 귀납법, 알고리즘 효율성의 점근적 분석법 등을 배운다. 그 후 분할정복 divide and conquer, 동적 계획법 dynamic programming, 그리디 방법 greedy approach, 퇴각검색 backtracking, 분지한정 branch and bound 등의 알고리즘 설계 기법을 공부한다. 강의 후반에는 효율적인 알고리즘이 존재하지 않는 문제가 있다는 사실을 배우고 이를 다뤄본다. chap1. algorithm efficiency algorithm = step by step procedure for solving problem 알고리즘은 input을 받아 output을 내보낸다. - 문제에 따라 형태는 다르다. 왜 알고리즘을 공부하냐? pra..
