본문 바로가기
반응형

코딩테스트131

[코딩 테스트] 20일차: 동적 프로그래밍 동적 프로그래밍 (Dynamic Programming)동적 프로그래밍은 복잡한 문제를 더 작은 부분 문제로 나누어 해결하는 방법입니다. 부분 문제의 해결 결과를 저장하여 동일한 부분 문제를 다시 계산하지 않도록 합니다. 동적 프로그래밍은 주로 최적화 문제에 사용되며, 메모이제이션(Memoization)과 타뷸레이션(Tabulatioon) 두 가지 방법으로 구현할 수 있습니다.동적 프로그래밍의 주요 개념부분 문제(Subproblem): 원래 문제를 구성하는 더 작은 문제최적 부분 구조(Optimal Substructure): 부분 문제의 최적 해를 이용하여 원래 문제의 최적 해를 구할 수 있는 구조중복되는 부분 문제(Overlapping Subproblems): 동일한 부분 문제가 여러 번 반복되는 문제 .. 2024. 9. 20.
[코딩 테스트] 19일차: 탐욕 알고리즘 탐욕 알고리즘 (Greedy Algorithm)탐욕 알고리즘은 매 순간 가장 최적이라고 생각되는 해를 선택하여 문제를 해결하는 방법입니다. 이 방법은 부분적인 최적 해가 전체적인 최적 해가 될 수 있는 문제에 적합합니다. 탐욕 알고리즘은 주로 최적화 문제에 사용됩니다.탐욕 알고리즘의 주요 개념현재 시점에서 가장 좋은 선택: 각 단계에서 가장 좋은 선택을 하여 문제를 해결부분 최적 해: 각 부분 문제에서의 최적 해가 전체 문제에서도 최적 해가 되는 경우활동 선택 문제 (Activity Selection Problem)활동 선택 문제는 시작 시간과 종료 시간이 주어진 여러 활동 중에서 서로 겹치지 않게 최대한 많은 활동을 선택하는 문제입니다. 탐욕 알고리즘을 이용하여 해결할 수 있습니다. 예제: 활동 선택 .. 2024. 9. 19.
[코딩 테스트] 17일차: 그래프의 심화 알고리즘 그래프의 심화 알고리즘이번 글에서는 그래프의 심화 알고리즘에 대해 알아보겠습니다. 위상 정렬, 강결합 컴포넌트, 최소 컷 최대 유량 등의 알고리즘을 살펴보겠습니다.위상 정렬 (Topological Sort)위상 정렬은 방향 그래프의 모든 노드를 순서대로 나열하는 알고리즘입니다. 주로 작업의 순서를 결정할 때 사용됩니다. 위상 정렬은 사이클이 없는 방향 그래프(DAG)에서만 적용 가능합니다. 예제: 위상 정렬 구현 (Kahn's Algorithm)JavaScriptfunction topologicalSort(vertices, edges) { const adjList = new Map(); const inDegree = new Map(); const queue = []; const result = [.. 2024. 9. 17.
[코딩 테스트] 16일차: 트리 알고리즘 트리 알고리즘트리는 노드와 간선으로 이루어진 자료구조로, 사이클이 없는 연결 그래프입니다. 이진 트리, 이진 탐색 트리(BST), AVL 트리, 힙(Heap) 등 다양한 트리 구조가 있으며, 각기 다른 특성과 용도를 가지고 있습니다.이진 트리와 이진 탐색 트리 (BST)이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리입니다. 이진 탐색 트리(BST)는 이진 트리의 일종으로, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가지는 트리입니다. 예제: 이진 탐색 트리 구현JavaScriptclass TreeNode { constructor(value) { this.value = value; this.left = null; this.right = null; }}class.. 2024. 9. 16.
[코딩 테스트] 15일차: 그리디 알고리즘 그리디 알고리즘 (Greedy Algorithm)그리디 알고리즘은 매 순간 가장 최적이라고 생각되는 해를 선택하여 문제를 해결하는 방법입니다. 이 방법은 부분적인 최적 해가 전체적인 최적 해가 될 수 있는 문제에 적합합니다.그리디 알고리즘의 주요 개념현재 시점에서 가장 좋은 선택: 각 단계에서 가장 좋은 선택을 하여 문제를 해결부분 최적 해: 각 부분 문제에서의 최적 해가 전체 문제에서도 최적 해가 되는 경우최소 신장 트리 (MST)최소 신장 트리는 그래프의 모든 정점을 포함하면서, 사이클이 없고, 간선의 가중치 합이 최소인 트리입니다. 대표적인 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리즘(Prim's Algorithm)이 있습니다.크루스칼 알고리즘 (Kruska.. 2024. 9. 15.
[코딩 테스트] 14일차: 분할 정복 분할 정복 (Divide and Conquer)분할 정복은 문제를 더 작은 하위 문제로 나누어 해결하고, 그 결과를 합쳐서 원래 문제를 해결하는 알고리즘 기법입니다. 분할 정복의 핵심은 문제를 나누고(Divide), 정복하며(Conquer), 합치는(Combine) 단계로 이루어집니다.분할 정복의 주요 개념분할(Divide): 문제를 더 작은 하위 문제로 나눕니다.정복(Conquer): 하위 문제를 재귀적으로 해결합니다.합치기(Combine): 하위 문제의 결과를 합쳐 원래 문제의 해를 구합니다.합병 정렬 (Merge Sort)합병 정렬은 분할 정복 알고리즘의 대표적인 예제로, 배열을 반으로 나누어 각각을 정렬한 후 병합하여 정렬된 배열을 만듭니다. 시간 복잡도는 O(n log n)입니다. 예제: 합병 .. 2024. 9. 14.
[코딩 테스트] 13일차: 동적 프로그래밍 동적 프로그래밍 (Dynamic Programming)동적 프로그래밍은 복잡한 문제를 더 작은 부분 문제로 나누어 해결하는 방법입니다. 부분 문제의 해결 결과를 저장하여 동일한 부분 문제를 다시 계산하지 않도록 합니다. 동적 프로그래밍은 주로 최적화 문제에 사용되며, 메모이제이션(Memoization)과 타뷸레이션(Tabulatioon) 두 가지 방법으로 구현할 수 있습니다.동적 프로그래밍의 주요 개념부분 문제(Subproblem): 원래 문제를 구성하는 더 작은 문제최적 부분 구조(Optimal Substructure): 부분 문제의 최적 해를 이용하여 원래 문제의 최적 해를 구할 수 있는 구조중복되는 부분 문제(Overlapping Subproblems): 동일한 부분 문제가 여러 번 반복되는 문제 .. 2024. 9. 13.
[코딩 테스트] 12일차: 그래프 알고리즘 그래프 알고리즘그래프 알고리즘은 노드(정점)와 노드를 연결하는 에지(간선)로 구성된 자료구조인 그래프를 탐색하거나 분석하는 알고리즘입니다. 이번 글에서는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 그리고 최단 경로 알고리즘(Dijkstra, Floyd-Warshall)에 대해 알아보겠습니다.깊이 우선 탐색(DFS)깊이 우선 탐색(DFS)은 그래프의 모든 정점을 깊게 탐색하는 알고리즘입니다. 스택(또는 재귀)을 사용하여 구현할 수 있습니다.예제: DFS 구현JavaScriptclass Graph { constructor() { this.adjList = new Map(); } addVertex(v) { if (!this.adjList.has(v)) { this.adjLi.. 2024. 9. 12.
[코딩 테스트] 11일차: 재귀와 백트래킹 재귀 (Recursion)재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 재귀 함수는 하나 이상의 종료 조건(Base Case)과 자기 자신을 호출하는 재귀 단계(Recursive Case)를 포함합니다.재귀 함수의 주요 개념기저 조건(Base Case): 재귀 호출을 멈추는 조건재귀 단계(Recursive Case): 함수를 반복적으로 호출하는 단계예제: 재귀를 이용한 팩토리얼 계산JavaScriptfunction factorial(n) { if (n === 0) { return 1; // 기저 조건 } return n * factorial(n - 1); // 재귀 단계}console.log(factorial(5)); // 120Pythondef factorial(n): if.. 2024. 9. 11.
[코딩 테스트] 10일차: 탐색 알고리즘 탐색 알고리즘탐색 알고리즘은 주어진 데이터 집합에서 특정 값을 찾는 방법입니다. 이번 글에서는 가장 기본적인 탐색 알고리즘인 선형 탐색과 효율적인 탐색 알고리즘인 이진 탐색에 대해 알아보겠습니다.선형 탐색 (Linear Search)선형 탐색은 배열의 처음부터 끝까지 순차적으로 탐색하여 원하는 값을 찾는 방법입니다. 시간 복잡도는 O(n)입니다.JavaScript에서의 선형 탐색 구현function linearSearch(arr, target) { for (let i = 0; i Python에서의 선형 탐색 구현def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i.. 2024. 9. 10.
반응형

티스토리툴바