반응형 Python24 [코딩 테스트] 19일차: 탐욕 알고리즘 탐욕 알고리즘 (Greedy Algorithm)탐욕 알고리즘은 매 순간 가장 최적이라고 생각되는 해를 선택하여 문제를 해결하는 방법입니다. 이 방법은 부분적인 최적 해가 전체적인 최적 해가 될 수 있는 문제에 적합합니다. 탐욕 알고리즘은 주로 최적화 문제에 사용됩니다.탐욕 알고리즘의 주요 개념현재 시점에서 가장 좋은 선택: 각 단계에서 가장 좋은 선택을 하여 문제를 해결부분 최적 해: 각 부분 문제에서의 최적 해가 전체 문제에서도 최적 해가 되는 경우활동 선택 문제 (Activity Selection Problem)활동 선택 문제는 시작 시간과 종료 시간이 주어진 여러 활동 중에서 서로 겹치지 않게 최대한 많은 활동을 선택하는 문제입니다. 탐욕 알고리즘을 이용하여 해결할 수 있습니다. 예제: 활동 선택 .. 2024. 9. 19. [코딩 테스트] 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. [코딩 테스트] 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. [코딩 테스트] 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. [코딩 테스트] 5일차: 스택과 큐 스택스택은 LIFO(Last In, First Out) 자료구조로, 가장 나중에 삽입된 데이터가 가장 먼저 삭제됩니다. 스택은 보통 함수 호출, 수식 계산, 문자열 역순 처리 등에서 사용됩니다.스택의 기본 연산push: 스택의 맨 위에 요소를 추가pop: 스택의 맨 위 요소를 제거하고 반환peek: 스택의 맨 위 요소를 반환 (제거하지 않음)isEmpty: 스택이 비어 있는지 확인JavaScript에서의 스택 구현class Stack { constructor() { this.items = []; } push(element) { this.items.push(element); } pop() { if (this.isEmpty()) { return "Underflow"; .. 2024. 9. 5. [코딩 테스트] 3일차: 함수와 객체 함수함수는 재사용 가능한 코드 블록으로, 특정 작업을 수행하기 위해 작성됩니다. 함수를 사용하면 코드의 가독성과 재사용성을 높일 수 있습니다.함수 선언과 호출JavaScript에서의 함수 선언과 호출// 함수 선언function greet(name) { return "Hello, " + name + "!";}// 함수 호출let greeting = greet("Alice");console.log(greeting); // "Hello, Alice!"Python에서의 함수 선언과 호출# 함수 선언def greet(name): return "Hello, " + name + "!"# 함수 호출greeting = greet("Alice")print(greeting) # "Hello, Alice!"매개변수와.. 2024. 8. 3. [코딩 테스트] 2일차: 조건문과 반복문 조건문조건문은 주어진 조건에 따라 코드의 실행 흐름을 제어하는 문법입니다. 조건문을 사용하여 특정 조건이 참일 때만 특정 코드 블록을 실행할 수 있습니다.if, else if, else 문if 문은 조건이 참일 때 특정 코드를 실행합니다. else if와 else 문은 추가 조건과 기본 조건을 처리하는 데 사용됩니다. JavaScript에서의 if, else if, else 문let num = 10;if (num > 10) { console.log("num은 10보다 큽니다.");} else if (num === 10) { console.log("num은 10입니다.");} else { console.log("num은 10보다 작습니다.");}Python에서의 if, else if, else 문nu.. 2024. 8. 2. 이전 1 2 3 다음 반응형