그리디 알고리즘(탐욕법, Greedy Algorithm)각 단계에서 가장 좋아 보이는 선택을 하는 방식이다. 현재 상황에서 최선을 선택을 한다. 한 번 선택한 것은 되돌리지 않는다. 빠르고 간단하지만, 항상 최적의 해를 보장하지는 않는다.  예제 (거스름돈 문제) def 거스름돈(금액): 동전 = [500, 100, 50, 10] # 사용 가능한 동전의 종류 결과 = {} for 단위 in 동전: 개수 = 금액 // 단위 if 개수 > 0: 결과[단위] = 개수 금액 %= 단위 return 결과print(거스름돈(1260))가장 큰 단위의 동전부터 시작한다. 현재 금액에서 해당 동전을 최대한 많이 사용한다. 남은 금액..

핵심 개념복잡한 문제를 더 작고 간단한 하위 문제들로 나누어 해결하는 것 (=기억하며 풀기) 문제를 더 작은 하위 문제로 나눈다. 각 하위 문제의 해답을 계산하고 저장한다. 저장된 결과를 이용해 더 큰 문제의 해답을 구한다. 특정한 알고리즘이 아니다. 그저 하나의 문제 해결 패러다임이다.  주요 특징같은 하위 문제의 결과를 여러 번 계산하지 않고 저장된 결과를 재사용한다. 큰 문제의 최적해가 작은 문제들의 최적해로 구성된다.  접근 방식 하향식(Top-down) : 메모이제이션 큰 문제에서 시작하여 작은 문제로 나누어 해결한다.재귀를 사용하지만, 계산된 결과를 저장(메모이제이션)하여 중복 계산을 방지한다.상향식(Bottom-up) : 타뷸레이션 가장 작은 부분 문제부터 시작하여 큰 문제를 해결한다. 반복..

스패닝 트리(Spanning Tree)원래 그래프의 모든 정점을 포함하면서 사이클 없이 연결된 부분 그래프를 의미한다.  스패닝 트리 조건모든 정점을 포함한다. 스패닝 트리는 원래 그래프의 모든 정점을 반드시 포함한다. 스패닝 트리는 그래프의 모든 요소를 '포괄(span)'한다는 의미에서 그 이름이 유래했다. 정확히 (n-1)개의 간선을 가집니다. (여기서 n은 그래프의 정점 수) n개의 정점을 가진 그래프의 스패닝 트리는 정확히 (n-1)개의 간선을 가진다. 이는 모든 정점을 연결하는 데 필요한 최소한의 간선 수 이다. 사이클(순환)을 포함하지 않는다. 스패닝 트리에는 사이클이 존재하지 않는다. 즉, 어떤 정점에서 출발하여 다시 그 정점으로 돌아오는 경로가 없다.연결되어 있다. (모든 정점 간에 경로가..

0. 개요1956년 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)에 의해 고안된 이 알고리즘은, 그래프에서 한 정점(노드)에서 다른 모든 정점까지의 최단 경로를 효율적으로 찾는 방법을 제시한다.  핵심 아이디어다익스트라 알고리즘의 핵심 아이디어는 단순하면서도 강력하다. 출발점에서 시작하여, 현재까지 알려진 최단 경로를 가진 정점을 선택하고, 그 정점을 통해 갈 수 있는 다른 정점들의 최단 경로를 갱신해나가는 과정을 반복한다. 이 과정을 통해 알고리즘은 그래프의 모든 정점을 방문하게 되며, 각 정점까지의 최단 경로를 모두 찾아낸다. 특징다익스트라는 '탐욕적'(greedy) 접근 방식을 취한다. 이 말이 무슨 말이나면, 매 단계에서 가장 좋아 보이는 선택(여기서는 최단 거리..

문제이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.예를 들어 위와 같은 이진 트리가 입력되면,전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 입력첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨..

위상 정렬(Topological Sorting)위상 정렬은 복잡한 작업들 사이의 순서를 정리하는 강력한 도구다. 이 알고리즘은 방향성 비순환 그래프(DAG, Directed Acyclic Graph)에서 작동한다. 여기서 '방향성'이란 작업들 사이에 명확한 선후관계가 있다는 뜻이고, '비순환'이란 어떤 작업도 자기 자신으로 돌아오는 순환고리에 갇히지 않는다는 의미이다. 위상 정렬의 목표는 이러한 그래프의 모든 노드(작업들)를 일렬로 늘어세우는 것이다. 이때 중요한 점은 그래프의 방향, 즉 작업들 간의 선후관계를 어기지 않아야 한다는 것이다.  마치 도미노를 세우듯이, 각 작업은 자신에게 필요한 모든 선행 작업들이 완료된 후에야 수행될 수 있다. 이 알고리즘의 핵심은 '선행 관계'를 철저히 지키는 데 있다..

DFS(깊이 우선 탐색)DFS(Depth-First Search)는 그래프나 트리 구조를 탐색하는 알고리즘 중 하나이다. 이 알고리즘은 가능한 한 깊이 들어가면서 탐색을 진행하고, 더 이상 탐색할 수 없을 때 백트래킹(backtracking)하여 다른 경로를 탐색한다. DFS는 주로 스택이나 재귀 함수를 사용하여 구현한다. 스택을 사용하면 명시적으로 방문할 노드를 관리할 수 있고, 재귀를 사용하면 함수 호출 스택을 이용하여 자동으로 백트래킹을 처리할 수 있다. 이 알고리즘의 특징은 한 경로를 끝까지 탐색한 후 다른 경로를 탐색한다는 점이다. 이는 미로 찾기나 경로 탐색 문제 등에서 유용하게 사용된다.  DFS 핵심 메커니즘DFS는 가능한 한 깊이 들어가면서 탐색을 진행한다. 한 경로를 끝까지 탐색한 후 ..

0. 문제 의식의 출발  # 예제 코드 Aresult = 0def add(num): global result result += numadd(3)print(result)# return 사용하지 않음 # 결과값은 '3' 출력# 예제 코드 Bresult = 0def add(num): global result result += num return resultprint(add(3))# return 사용함# 결과값은 '3' 출력예제 A 코드와 B 코드는 동일한 기능이 구현되어 있다. 결과값도 같다. 차이는 리턴(return)의 사용 여부다. 나는 이 차이가 궁금해졌다. 과연 내가 진정으로 return 문의 의미를 알고 코드를 작성하는 것이 맞는지 의구심이 들었다. 이러한 의문은 많은 입문..