Computer Science/알고리즘 (Algorithm)10 알고리즘 | 최적화 문제 | 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘 그리디 알고리즘의 기본 아이디어는 각 단계에서 현재의 상황에서 최적의 선택을 하는 것이다. 이러한 선택은 문제 해결에 있어서 전역적으로 최적이며, 각 단계에서의 선택은 이후 단계에 대한 선택을 제한하지 않는다. DP와 마찬가지로, 그리디 알고리즘은 일반적으로 최적화 문제를 해결하기 위해 사용된다. 또한, 그리디 알고리즘은 해를 찾기 위해 반복적인 선택을 해야 하는 문제에도 적용된다. 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. (...) 이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우.. 2023. 10. 27. 알고리즘 | 최적화 문제 | 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 다이나믹 프로그래밍(동적 계획법, 이하 DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 이를 조합하여 원래의 문제를 해결하는 알고리즘 설계 기법이다. 핵심 아이디어 자체는 분할정복과 동일하다. 1950년대에 리처드 벨먼이라는 응용수학자가 개발했으며, Dynamic 이라는 단어는 그저 멋있어서😂 붙인거고, Programming은 컴퓨터 코드가 아니라 테이블을 이용한 방법을 일컫는 거라고 한다. 개인적으로 DP는 적용 상황을 판단하는 것도 쉽지 않고, 문제 풀이 단계에서 정확한 점화식을 도출하는 게 쉽지않은 것 같다. . 모두 연습만이 살길 !! 어떤 문제에 DP를 적용하는가? 목적을 따지자면, 일반적으로 최적화 문제(optimmization problem)에 DP를 적용한다... 2023. 10. 27. 알고리즘 | 그래프 탐색 | 위상 정렬(Topological Sort) 위상 정렬은 방향 그래프(Directed Graph)에서 노드를 정렬하는 방법이다. u -> v 방향을 갖는 각 간선 (u, v)에 대해서, u가 v보다 앞에 오도록 정렬한다. 여러가지 작업이 주어지고, 특정 작업이 특정 작업보다 선행되어야 한다는 순서 조건이 달렸을 때, 전체 순서를 어떻게 전개해야할 것인가와 관련하여 탁월한 답을 내려준다. 이러한 특성 덕에, 위상 정렬은 프로젝트를 스케줄링할 때, 작업 우선순위 지정 등 다양한 분야에서 활용된다. 기본 개념 의존성(Dependency): A 작업이 B 작업에 의존한다는 것은, A 작업이 시작하기 전에 B 작업이 완료되어야 함을 의미한다. 진입차수(in-degree): 한 노드로 들어오는 간선의 수 진출차수(out-degree): 한 노드에서 나가는 간.. 2023. 10. 23. 알고리즘 | 그래프 탐색 | 크루스칼 알고리즘(Kruskal's Algorithm) 위와 같은 MST를 어떻게 자동적으로 찾을 수 있을까? 크루스칼 알고리즘과 프림 알고리즘은 MST를 찾는 대표적인 기법이다. 두 알고리즘의 시간복잡도와 공간복잡도는 다음과 같다. (V = 정점의 수, E = 간선의 수) Kruskal 알고리즘 Prim 알고리즘 시간복잡도 (간선 기반) O(E*log E) O(E*log V) 시간복잡도 (우선순위 큐 사용) - O(E + V*log V) 공간복잡도 O(E + V) O(E + V) Kruskal 알고리즘의 경우, 간선을 정렬하는 데 가장 많은 시간이 소요되므로 O(E*log E)의 시간복잡도를 갖는다. Prim 알고리즘은 각 정점마다 인접한 간선 중 가장 작은 가중치를 가진 간선을 선택하므로, 우선순위 큐를 사용할 경우 O(E + V*log V)의 시간복잡도.. 2023. 10. 23. 알고리즘 | 그래프 탐색 | BFS, DFS 앞서 실제 세계를 데이터 구조로 모델링하기 위해 그래프를 사용한다고 했는데, 실제 문제 해결까지 가기 위해서는 표현에 그칠 것이 아니라 다양한 방식의 활용법을 모색할 필요가 있다. 그 중 대표적으로 그래프 내의 정보를 효율적으로 탐색하는 탐색 기법이 빠질 수 없다. 그 중에서도 BFS(Breadth-First Search, 너비우선탐색)와 DFS(Depth-First Search, 깊이우선탐색)는 가장 기본적이면서도 널리 사용되는 탐색 알고리즘이다. BFS와 DFS는 그래프의 모든 노드를 방문하는 방법이지만, 방문 순서와 방식에는 큰 차이가 있다. 이 두 알고리즘은 다양한 심화 알고리즘의 핵심 아이디어 기반이 되기도 한다. 기업 코딩테스트에서도 단골로 출제되는 주제이니만큼 제대로 이해하는 것이 좋다. B.. 2023. 10. 22. 알고리즘 | 정렬 기법 | 병합 정렬(Merge Sort) Merge Sort는 이전 포스팅에서 공부했던 Quick Sort와 함께 분할 정복을 활용한 대표적인 정렬 기법이다. 1945년에 폰 노이만이 개발했다고 한다. 안정적인 정렬로 알려져 있으며, 데이터의 크기와 상관없이 일정한 성능을 보여준다는 장점이 있다. 따라서 대용량의 데이터를 정렬할 때 효과적이라고 한다. 앞서 Quick Sort가 Java에서 기본형 타입의 배열의 Array.sort() 메서드에 활용된다고 했는데, 객체 타입 배열의 Array.sort()에는 Tim Sort가 쓰인다. 파이썬의 list.sort()와 sorted(list)도 Tim Sort 기반으로 동작한다. 여기서 Tim Sort가 삽입 정렬(Insertion Sort)과 Merge Sort를 결합한 기법이다. 1. 핵심 아이디.. 2023. 10. 18. 알고리즘 | 분할정복(Divide and Conquer) 분할 정복 알고리즘은 다양한 알고리즘 설계에서 핵심 원칙으로 사용되고 있다. 자주 접하는 개념 중에선 Quick Sort, Merge Sort가 분할 정복 알고리즘을 응용한 대표적인 예시이다. 고속 푸리에 변환(FFT)도 분할 정복 알고리즘 기반이라고 한다. 분할 정복 알고리즘 개념 분할 정복(Divide and Conquer)은 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 전략이다. Divide and Conquer라는 이름의 어원은 원래 정치와 군사 전략에서 사용되던 용어로, 큰 적 또는 문제를 작은 부분으로 나누어 각각을 해결함으로써 전체를 제어하는 전략을 의미한다고 한다. (나무위키에 따르면 제국주의 시절 유럽 식민제국이 식민지인들의 단결을 막기 위해 주로 사용한 방법으로 유명한 분.. 2023. 10. 18. 알고리즘 | 정렬 기법 | 퀵 정렬 (Quick Sort) Quick sort는 1961년 Tony Hoare(토니 호어)가 발표한 정렬 기법이다. 정렬 기법 중에서 매우 흔히 사용되는 기법으로, 현대에는 Quick Sort에 여러 가지 최적화 기법을 추가한 변형을 자주 사용한다. 예를 들어, Java의 Array.sort() 메서드는 기본형 타입의 배열(int, long 등)에 대해서는 Dual-Pivot Quick Sort를 사용한다고 한다. (객체 배열에 대해서는 Tim Sort를 사용한다.) - Dual-Privot Quick Sort: Insertion Sort와 Quick Sort를 결합한 정렬 기법 - Tim Sort: Insertion Sort와 Merge Sort를 결합한 정렬 기법 1. 핵심 아이디어 분할 정복 전략을 사용하여 리스트를 정렬한다.. 2023. 10. 17. 알고리즘 | 계산 복잡도, Big-O 표기법 프로그램의 효율성 프로그램의 효율성은 해당 프로그램이 얼마나 빠르게 원하는 결과를 도출하고, 그 과정에서 얼마나 적은 자원을 사용하는지를 기준으로 평가된다. 특히 알고리즘 코드를 작성하는 입장에서는, 내 코드 혹은 동료의 코드의 효율성을 빠르게 판단할 수 있는 인지적 도구가 필요하다. 따라서 프로그램 효율성울 평가하는 두 가지 핵심 요소, 즉 1) 얼마나 빠른 시간 내에, 2) 얼마나 적은 자원을 사용하여 구현되었는지를 쉽게 파악할 수 있도록 1) '시간 복잡도(Time Complexity)'와 2) '공간 복잡도(Space Complexity)', 그리고 이들을 나타내는 표기법인 'Big-O' 개념을 배울 필요가 있다. 백준 문제를 풀 때, 항상 문제에 시간 제한과 메모리 제한이 걸려 있다. 여기서 '.. 2023. 10. 15. 알고리즘 | 재귀(Recursion) 재귀함수 문제를 아직 몇 개 못 풀어보긴 했지만, 지금까지 느낌으로는 재귀함수를 활용한 풀이는 마법같이 느껴지기도 한다. 하위 문제가 올바르게 해결된다는 가정만 정확히 한다면, 하위 문제의 구체적인 해결 방법을 코드로 직접 짜지 않아도 컴퓨터의 빠른 연산이 자동으로 해결해준다. 처음에는 '이게 말이 돼?'라는 생각이 든다. 때문에 직관적이지 않지만, 제대로 습득한 사람들에게는 매우 유용한 도구가 될 것이라 생각된다. 하위 문제에 대한 해결책이 이미 정의되어 있다고 "가정"하는 것은 재귀의 핵심 철학 중 하나입니다. 재귀의 아름다움은 그것이 문제를 단순화하는 방식에 있습니다. 복잡한 문제를 여러 작은 조각으로 나누면, 각 조각을 해결하는 것은 종종 훨씬 더 쉽습니다. 재귀는 이러한 단순화를 반복적으로 적용.. 2023. 10. 15. 이전 1 다음
