Algorithm
-
[정글 WEEK04_알고리즘] LCS와 LISAlgorithm 2025. 4. 3. 21:54
LCS(Longest Common Subsequence) - 최장 공통 부분 수열"두 수열에서 순서를 유지하면서 공통으로 등장하는 가장 긴 부분 수열의 길이를 구하는 문제"단순히 요소들이 모두 존재하는지 보기만 하면 안 되고 위치까지 고려한 비교가 필요함 🪄 활용 사례버전 관리(diff), DNA 분석 🪄 풀이 방법DP → 시간 복잡도: O(N * M) • N, M: 두 수열의 길이 💡 점화식 1️⃣ 두 수열의 마지막 요소가 같다면, 그 문자를 포함한 LCS를 만들 수 있음 해당 문자를 포함한 LCS를 만들기 위해 마지막 원소를 지우고, 짧아진 수열에 대한 LCS를 찾은 후 삭제한 원소를 붙여줌 예) X = AB**C**, Y = DE**C** → C는 LCS에 포함됨..
-
[정글 WEEK04_알고리즘] 개발일지 - Knapsack Problem으로 알아보는 DP와 GreedyAlgorithm 2025. 4. 3. 21:23
🪄 DP(Dynamic Programming)"복잡한 문제를 작은 하위 문제들로 나누고, 그 결과를 저장해두었다가 중복 계산을 피하면서 최적해를 찾는 기법" 1️⃣ 중복되는 부분 문제를 피하기 위해 부분 문제의 결과 저장 2️⃣ 모든 경우의 수를 고려하며 최적의 해 탐색 3️⃣ 이전 상태를 기반으로 현재 상태를 계산할 수 있는 점화식 도출 필수 ✏️ 풀이 방식아래와 같은 일반적인 피보나치 수열 풀이와 두 가지 DP 풀이를 비교해서 DP의 개념을 확실히 이해해보자!# 일반적인 피보나치 수열 풀이def fibonacci(n): if n == 0: return n elif n == 1: return n else: return fibonacci(n - 1..
-
[정글 WEEK03_알고리즘] 개발 일지 - BFS/DFSAlgorithm 2025. 3. 29. 15:49
개요BFS와 DFS는 그래프를 탐색하는 방법이고, 그래프 중에서도 트리에 많이 사용된다.트리는 형제 노드의 순서 관계 여부에 따라 '순서 트리(Ordered Tree)', '무순서 트리(Unordered Tree)'로 구분할 수 있다.참고로, 대표적인 순서 트리에는 이진 트리가 있다. 순서 트리를 순회하는 방법에는 DFS 기반의 전위 순회, 중위 순회, 후위 순회가 있으며,무순서 트리의 탐색에는 DFS 방식, BFS 방식 모두 사용할 수 있다. 순서 트리 순회아래와 같은 트리를 전위 순회, 중위 순회, 후위 순회 해보자. A / \ B C / \ \ D E F - 전위 순회 Root → Left → Right 순으로 탐..
-
[정글 WEEK03_알고리즘] 개발 일지 - 최단 경로 알고리즘Algorithm 2025. 3. 29. 14:11
📍 한 정점 → 모든 정점 탐색 1. 다익스트라(Dijkstra) 한 지점에서 다른 모든 지점까지의 최단 경로를 계산하는데, 양의 가중치 간선만 허용하는 알고리즘 방향이 있는 그래프에서 '노드와 간선의 개수가 모두 많은' 경우 사용 💡핵심 아이디어: 단계마다 '방문하지 않은 노드' 중에서 '가장 비용이 적은' 노드를 선택한 뒤에, 그 노드를 거쳐 가는 경우를 확인해서 최단 거리 갱신 빠르게 최소 거리 노드를 선택하기 위해서 우선순위 큐를, 특정 노드의 인접 노드들을 확인하는 연산이 반복되므로 최단 거리 테이블은 인접리스트 사용 V번 각 노드의 최단 거리를 결정할 때, → 매번 heapq...
-
[정글 WEEK03_알고리즘] 개발 일지 - 트리Algorithm 2025. 3. 28. 11:45
정의n개의 노드(Node)와 n-1개의 간선(Edge)을 갖는 비순환 방향 연결 그래프 * 전통적인 수학에서는 무방향 그래프로, 컴퓨터공학 분야에서는 방향 그래프로 간주한다. ❗️아래 조건을 모두 만족해야 트리라고 할 수 있다.1) 모든 노드가 하나로 연결되어있어야 하며,2) 사이클이 없어야 하고,3) 항상 '간선의 수'가 '노드 수 - 1'개여야 한다. 헷갈리는 용어 - 레벨(level): 현재 노드가 루트에서 얼마나 멀리 떨어져 있는지 - 높이(height): 루트에서 가장 멀리 있는 리프까지의 거리 (= 리프 레벨의 최댓값) 분류1. Binary Tree - Perfect Binary Tree - Strict Binary Tree - Complete Binary Tree - Binary Searc..
-
[정글 WEEK03_알고리즘] 개발 일지 - 위상 정렬Algorithm 2025. 3. 28. 11:45
정의DAG(Directed Acyclic Graph, 방향 비순환 그래프)에서 노드 간 선후 관계를 방향성에 거스르지 않고 나열하는 정렬 기법 사용 예시 - 작업 순서 설정 - 선수 과목 고려한 학습 순서 - 빌드 시스템(컴파일 순서) - 스케줄링 문제 등 핵심 개념 - 진입 차수(In-degree) : 특정 노드로 들어오는 간선의 수 수행 절차모든 노드의 진입 차수 계산진입 차수가 0인 노드를 큐에 삽입큐가 빌 때까지 아래 과정 반복 3-1) 큐에서 노드를 꺼내 결과 리스트에 추가 3-2) 해당 노드에서 나가는 간선 제거(연결된 노드의 진입 차수 -1) 3-3) 새롭게 진입 차수가 0이 된 노드를 큐에 삽입 사이클 판별 - 모든 노드를 방문하기 전에 큐가 비..
-
[정글 WEEK03_알고리즘] 개발 일지 - 그래프 개요Algorithm 2025. 3. 28. 11:02
정의정점(Vertex)과 정점 사이에 연결된 간선(Edge) 정보를 가지고 있는 자료구조 구현 방식- 인접 행렬: 그래프의 정점을 행과 열로 나타내고, 각 칸에 간선의 존재 여부(또는 가중치)를 저장하는 2차원 배열 구현 방식- 인접 리스트: 각 정점(vertex)에 대해 해당 정점과 연결된 이웃 정점들의 목록을 리스트 안에 저장, 가중치가 있다면 (정점, 가중치) 튜플 형태로도 저장 가능 인접 행렬인접 리스트형태N x N 2차원 배열예: matrix[D][C] = 1 → D정점과 C정점이 연결(0: 비연결, 1: 연결)리스트 안에 연결된 정점 목록예: graph[C] = [B, D] → C정점이 B, D 정점과 연결간선 정보 저장 시 공간 복잡도나쁨 (O(V^2))간선과 무관하게 V x V크기의 2..
-
[프로그래머스] 멀리뛰기 # DPAlgorithm 2024. 9. 20. 21:51
문제 링크1. 문제 전체 칸 수 n이 주어질 때 1칸 또는 2칸을 이동해 n칸을 이동하는 경우의 수에 1234567을 나눈 나머지를 반환하는 함수를 완성하라. 2. 제한 사항1 3. 입출력 예 4. 첫 번째 풀이 - Python 결국 초기값만 다른 피보나치 수열이다. n이 2000 이하이므로 메모이제이션을 사용하지 않았다. 메모이제이션을 사용했을 때는 0.18ms, 사용하지 않았을 때는 최대 0.15ms가 소요되었다. def solution(n): MOD = 1234567 if n == 1: return 1 if n == 2: return 2 a, b = 1, 2 for i in range(3, n + 1): a, b ..