전체 글
-
[정글 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..
-
[정글 WEEK04_알고리즘] 개발일지 - C 포인터, * 연산자, & 연산자카테고리 없음 2025. 4. 3. 18:37
1. 포인터, 역참조 연산자 "*"*는 변수 선언 시에는 포인터 선언으로, 변수 사용 시에는 역참조에 쓰임 포인터는 특정 변수 또는 데이터의 주소를 저장하는 특별한 변수역참조는 주소에 있는 값에 접근 ❗️ 포인터도 변수이므로 메모리 어딘가에 저장됨int *i; // int형 데이터를 '가리키는' 포인터 i 선언char *c; // char형 데이터를 '가리키는' 포인터 c 선언double *d; // double형 데이터를 '가리키는' 포인터 d 선언 🗝️ 사용 맥락1) 함수에서 값 변경(Call by Reference)#include void set_to_zero(int *ptr) { // 포인터 선언 *ptr = 0; // 역참조 -> ptr이 가리키는 주소에 저장되는 값ㅇ르 0으로..
-
[정글 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..
-
[정글 WEEK02_알고리즘] 개발 일지 - 2주차 마무리Extracurricular Activites/정글 2025. 3. 28. 00:13
공부 키워드 - 이분 탐색 - 분할 정복 - 스택 - 큐 - 우선순위 큐 - Linked List - 해시 테이블 지식의 연결✏️ 파이썬 dict는 해시 충돌을 어떻게 해결하고, 해시 함수로 무엇을 쓸까? ◼︎ 해시 충돌은 perturbation probing 기반의 open addressing 방식으로 해결한다. 단순히 버킷들을 한 칸씩 선형으로 탐색하는 것이 아니라, 해시값에서 유도한 perturb 값을 활용해 비트 연산과 시프트를 반복하며 다음 후보 인덱스를 계산한다.perturb는 다음 탐색 위치를 다양하게 만들기 위한 보조 난수 값으로, 아래 코드에서 볼 수 있듯이 시작 인덱스를 계속 변화하게 만들어 충돌을 효과적으로 분산시킨다.hash = 123456789mask = 15 # ..