728x90 프로그래밍/알고리즘8 [알고리즘 시리즈] 탐욕 알고리즘 : Greedy Algorithm 탐욕 알고리즘 : Greedy Algorithm목차1. 그리디 알고리즘의 목적2. 그리디 알고리즘의 적용 조건3. 그리디 알고리즘 적용 예시1. 그리디 알고리즘의 목적현재의 선택이 다음 단계에 끼치는 영향을 고려하지 않고 전체 문제의 최적의 해를 구한다. 2. 그리디 알고리즘의 적용 조건1) Greedy-choice property현재 최선의 선택이 미래에도 최선의 선택인가이 속성을 만족하지 않는 그리디 알고리즘은 huristic한 해결책을 제시한다. 2) Optimal Substructure부분 문제의 해결 방법으로 전체 문제도 해결할 수 있는가 3. 그리디를 적용한 대표적인 문제들1) Activity Selection Problem시작 시간과 끝 시간이 있는 활동이 여러개가 있을 때, 주어진 구간에서.. 2024. 10. 1. [알고리즘 시리즈] 투 포인터 : Two Pointer 투 포인터 : Two Pointer목차1. 투 포인터의 목적2. 투 포인터의 적용 조건 및 적용 상황3. 투 포인터의 사용법4. Meet in the middle1. 투 포인터의 목적특정 조건에 따라 두 포인터를 조작하여 O(n) 만에 특정한 값을 찾는다. 2. 투 포인터의 적용 조건 및 적용 상황1) 검색을 위해 사용한다.특정한 조건을 만족하는 순서쌍을 찾는 문제에서 사용되는 투 포인터가 이 경우이다. 리스트가 오름차순 또는 내림차순으로 정렬되어 있어야 한다. 2) 한 배열을 정렬하기 위해 사용한다.quick sort 정렬 연산 시 사용되는 투 포인터가 이 경우이다.특별한 조건이 필요하지 않다. 3) 두 배열을 비교할 때 사용한다.merge sort의 병합 단계가 이 경우이다.두 배열이 오름차순 또는.. 2024. 9. 21. [알고리즘 시리즈] 분할 정복 : Divide and Conquer 분할 정복 : Divide and Conquer목차1. 분할 정복의 목적2. 분할 정복의 적용 절차3. 분할 정복이 적용된 형태4. 재귀적으로 분할된 알고리즘의 시간복잡도를 분석하는 방법1. 분할 정복의 목적복잡한 전체 문제를 쉬운 부분 문제로 나누어 푼다. 2. 분할 정복의 적용 절차전체 문제를 부분 문제로 나눈다. -> divide부분 문제를 해결한다. -> conquer해결된 부분 문제들을 합친다. -> combine 3. 분할 정복이 적용된 형태아래는 분할 정복을 이용하여 병합 정렬을 수행하는 코드다.배열을 절반으로 분리한다. 투 포인터를 이용해 두 배열을 하나의 배열에 오름차순으로 정렬한다. def merge_sort(arr): if len(arr) > 1: mid = len(.. 2024. 9. 14. [알고리즘 시리즈] 알고리즘 분석 방법 : 시간복잡도와 공간복잡도 알고리즘 분석 방법목차1. 알고리즘이란 무엇인가2. 알고리즘을 분석하는 방법3. 시간복잡도란 무엇인가4. 시간복잡도를 계산하는 방법5. Growth of functions6. 공간복잡도란 무엇인가7. 좋은 알고리즘이란 무엇인가1. 알고리즘이란 무엇인가문제를 해결하는 일반적인 방법이다. 2. 알고리즘을 분석하는 방법알고리즘의 효율성은 아래 두 가지 기준으로 판단한다.시간 복잡도 (Time Complexity)공간 복잡도 (Space Complexity)또한, 입력값이 주어지는 상황을 3가지로 나누어 알고리즘을 분석한다.worst-case : 최악의 시간 복잡도를 가지는 입력값이 주어진 경우average-case : 평균의 시간 복잡도를 가지는 입력값이 주어진 경우best-case : 최상의 시간 복잡도를 .. 2024. 9. 13. [알고리즘 시리즈] 동적 계획법 : Dynamic Programming 동적 계획법 : Dynamic Programming목차1. 다이내믹 프로그래밍의 목적2. 다이나믹 프로그래밍의 적용 절차3. 다이나믹 프로그래밍의 적용 조건4. 다이나믹 프로그래밍이 적용된 형태5. 다이나믹 프로그래밍과 분할 정복의 차이점6. 다이나믹 프로그래밍을 적용한 대표적인 문제들1. 다이나믹 프로그래밍의 목적재계산을 피한다. 2. 다이나믹 프로그래밍의 적용 조건1) Optimal Substurcture부분 문제의 최적의 값으로 전체 문제의 최적의 값을 구할 수 있는가 2) Overlapping Subproblems동일한 부분문제가 반복해서 나타나는가 3. 다이나믹 프로그래밍의 적용 절차전체 문제를 부분 문제로 나눈다.부분 문제를 해결하고 결괏값을 저장한다.부분 문제의 답과 해결 방식을 이용하여 전.. 2024. 7. 31. [알고리즘] 누적 합, 구간 합 - 백준 단계별로 풀어보기 시리즈 들어가며이번 포스팅에서 다룰 알고리즘은 누적 합 입니다. 누적 합 배열을 이용해 구간 합을 구하는 알고리즘입니다.개인적으로는 구간 합이라고 불리는 것이 더 적절하다고 생각합니다. 아이디어 자체는 간단하지만 한번씩 예상치 못한 곳에서 사용되는 것 같습니다.구간 합누적 합 배열을 이용하여 상수 시간만에 구간의 합을 구하는 알고리즘입니다. 구간 합을 구하는 과정은 일반적으로 다음과 같습니다.1. 누적 합 배열을 만든다. 2. 두 지점의 차를 통해 구간 합을 구한다. 1차원 구간 합$ y $를 누적합 배열, $ x $를 원소라고 하자. 누적 합 배열을 만드는 방법$ y[i] = y[i-1] + x[i] $ 구간 합을 구하는 방법$ [a, b] $ 구간에 대해서, $ y[b] - y[a-1] $ 2차원 구간 합 .. 2024. 7. 26. [알고리즘] 백트래킹 - 백준 단계별로 풀어보기 들어가며이번 챕터는 백트래킹입니다. 특별한 개념은 아니고, 재귀 함수의 콜스택을 이용하여 모든 경우의 수를 탐색하는 알고리즘 입니다.백트래킹재귀 함수를 이용하여 제약 조건 내 모든 경우의 수를 시뮬레이션하는 알고리즘입니다.제약 조건을 잘 설정하는 것이 관건입니다.당연한 얘기지만 재귀 함수를 이용합니다.알고리즘의 구조def backtracking(매개 변수): if 탈출조건: # 탈출 실행 if 제약범위안: # 실행 # 다음 단계로 # 실행 취소 return Any # return의 이용 여부는 사용자에게 달려있음 예시백트래킹 알고리즘은 미로 찾기와 같이 시뮬레이션이 필요한 문제를 푸는데 많이 사용됩니다.보통 다음의 형태로 많이 사용됩.. 2024. 7. 25. [알고리즘] 그래프와 탐색 - 백준 단계별로 풀어보기 시리즈 들어가며설명할게 따로 없어 바로 본론 들어가겠습니다. DFS깊이 우선 탐색이라고 불리며, 방향별로 탐색하는 방법입니다.보통 재귀 함수, 스택으로 구현됩니다.재귀 구현연결되어 있지 않은 노드를 고려하였습니다.grp = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': [], 'D': [], 'E': []}visited = set()def dfs(now): if now not in visited: print(now, end=' ') visited.add(now) for next in grp[now]: if next not in visited: dfs(next)for node in grp: dfs(node.. 2024. 7. 24. 이전 1 다음 728x90
