반응형 코딩테스트31 [코딩 테스트] 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. [코딩 테스트] 9일차: 정렬 알고리즘 정렬 알고리즘정렬 알고리즘은 데이터를 일정한 순서로 정렬하는 알고리즘입니다. 정렬된 데이터는 검색, 분석 등의 작업에서 효율성을 높여줍니다. 여기서는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬에 대해 알아보겠습니다.버블 정렬 (Bubble Sort)버블 정렬은 인접한 두 요소를 비교하여 정렬하는 가장 간단한 정렬 알고리즘 중 하나입니다. 시간 복잡도는 O(n^2)입니다.JavaScript에서의 버블 정렬 구현function bubbleSort(arr) { let n = arr.length; for (let i = 0; i arr[j + 1]) { // Swap let temp = arr[j]; arr[j] = arr[j + 1]; a.. 2024. 9. 9. [코딩 테스트] 8일차: 해시 테이블 해시 테이블해시 테이블은 키-값 쌍을 저장하는 자료구조로, 빠른 검색, 삽입, 삭제 작업을 지원합니다. 해시 함수(hash function)를 사용하여 키를 해시 값으로 변환하고, 이 해시 값을 인덱스로 사용하여 배열에 값을 저장합니다.해시 테이블의 주요 개념해시 함수: 키를 해시 값으로 변환하는 함수해시 값: 해시 함수에 의해 생성된 값버킷: 해시 값에 대응하는 저장 공간충돌 해결: 동일한 해시 값을 가진 여러 키를 처리하는 방법충돌 해결 방법체이닝(Chaining): 각 버킷에 연결 리스트를 사용하여 충돌을 해결오픈 어드레싱(Open Addressing): 충돌이 발생하면 다른 빈 버킷을 찾아 값을 저장해시 테이블 구현체이닝을 이용한 해시 테이블 구현JavaScript에서의 체이닝을 이용한 해시 테이.. 2024. 9. 8. [코딩 테스트] 7일차: 트리와 그래프 트리트리는 노드와 에지로 구성된 자료구조로, 계층적인 데이터를 표현하는 데 사용됩니다. 트리는 루트 노드를 가지고 있으며, 각 노드는 자식 노드를 가질 수 있습니다.트리의 주요 개념루트 노드: 트리의 시작 노드리프 노드: 자식 노드가 없는 노드간선(Edge): 노드를 연결하는 선깊이(Depth): 루트 노드에서 특정 노드까지의 경로 길이높이(Height): 루트 노드에서 리프 노드까지의 가장 긴 경로 길이트리 순회트리 순회 방법에는 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)가 있습니다.전위 순회 (Preorder)현재 노드를 방문왼쪽 서브트리를 전위 순회오른쪽 서브트리를 전위 순회중위 순회 (Inorder)왼쪽 서브트리를 중위 순회현재 노드를 방문오른쪽 서브.. 2024. 9. 7. [코딩 테스트] 6일차: 연결 리스트 연결 리스트연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지고 있는 자료구조입니다. 배열과 달리 연결 리스트는 메모리상에서 연속적으로 저장되지 않습니다.단일 연결 리스트단일 연결 리스트는 각 노드가 다음 노드에 대한 포인터만을 가지고 있는 리스트입니다.JavaScript에서의 단일 연결 리스트 구현class Node { constructor(data) { this.data = data; this.next = null; }}class LinkedList { constructor() { this.head = null; } // 노드 추가 append(data) { let newNode = new Node(data); if (this.head === n.. 2024. 9. 6. 이전 1 2 3 4 다음 반응형