그리디(Greedy) 알고리즘매 순간 가장 좋아보이는 선택을 하는 알고리즘.구성 방식Optimal Substructure (최적 부분 구조) 확인전체 문제의 최적해가 부분 문제의 최적해로부터 만들어질 수 있어야 함.예: 활동 선택 문제에서 S_ij 같은 식으로 서브문제 설정.Recursive 구조 파악문제를 재귀적으로 쪼갤 수 있어야 함.예: OPT(i, j) = max(OPT(i, k) + OPT(k, j)) 같은 형식.Greedy Choice 후, 하나의 하위 문제만 남음중요한 포인트. 동적 계획법은 보통 하위 문제가 여러 개지만,그리디는 하나만 남기게 설계되어야 효율적임.Greedy Choice의 안전성 증명“언제나 지금 고르는 게 전체적으로도 최선”이라는 걸 보여야 함.귀류법으로 자주 증명함 (예..

부분 문제들의 해를 결합해서 문제를 해결하는 방법. 분할 정복과 유사해보이나, 재귀적으로 부분문제를 해결할 때, 반복되어 사용될 문제의 해는 저장해서 다른 계산에 꺼내쓴다.특징중복되는 하위 문제 (Overlapping Subproblems)동일한 하위 문제가 여러번 반복 계산ex) Fibo : $F(n) = F(n-1) + F(n-2)$ 에서 $F(n-1)$과 $F(n-2)$가 반복 계산최적 부분 구조 (Optimal Substructure)문제의 최적해가 그 부분 문제의 최적해를 포함하고 있을 때 그 문제는 최적 부분 구조를 가짐구현 방식상향식 (Bottom-up, Tabulation) :문제의 가장 작은 하위 문제부터 차례로 계산, 그 결과를 테이블에 저장 후 점차 큰 문제로 확장반복문(loop)을 ..

너비 우선 탐색 (BFS; Breadth First Search)정의가까운 노드부터 탐색 즉, 시작한 노드와 연결된 인접 노드들을 모드 방문한 후, 방문한 노드들의 인접노드를 차례로 방문특징레벨 단위 탐색 : 루트 노드로부터 거리에 따라 레벨을 구분최단 경로 탐색 : 가중치가 동일한 경우 시작 노드로부터 각 노드까지 최단경로 구할 때 유용다음 방문할 노드를 저장하기 위해 큐 자료구조를 사용활용최단 경로 탐색시작점 ~ 모든 노드까지 최단경로(간선 수)를 탐색ex) 미로찾기, 네트워크 최단경로레벨 순서 탐색트리의 각 레벨별 노드를 순서대로 방문하여, 레벨 별 데이터를 처리하거나 출력ex) 조직도연결 요소 탐색연결된 노드들의 집합(연결요소)를 식별할 때 사용ex) SNS 친구 그룹 찾기흐름 및 구현 예제시작 ..

정의위상정렬은 무순환 방향 그래프 DAG(Directed Acyclie Graph)에서 정돈되지 않은 그래프를, 각 노드의 선후관계를 정립해 일관된 방향으로 향하도록 정렬하는 방식이다. (작업의 우선순위, 부품의 조립 순서)Kahn 알고리즘(BFS 기반)각 노드의 진입차수(indegree) 계산 후, 진입 차수가 0인 노드를 큐에 넣고, 연결된 노드의 진입 차수를 감소최종적으로 현재 진입 차수가 0인 노드를 선택from collections import dequedef topological_sort_kahn(graph, indegree): result = [] # 위상 정렬 결과 저장 queue = deque([i for i in range(1, len(indegree)..

다익스트라(Dijkstra) 알고리즘정점 - 다른 정점까지의 최단 경로를 구하는 알고리즘그 과정에 모든 다른 정점까지 최단 경로를 획득https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98전제 : 모든 간선에 음수인 가중치(weight)가 있어서는 안된다알고리즘대략적인 흐름출발 노드 설정각 노드로 가는 최소 비용 저장방문하지 않은 노드 중 비용이 적은 노드 선택해당 노드를 거쳐 다른 노드로 가는 경우를 계산, 기존 비용보다 낮을 경우 비용 갱신3~4 반복구현초기화:시작 정점의 거리 0으..

https://thinking-developer.tistory.com/74(참고)트리전위 순회(Preorder)(1) 정의 및 순서순회 순서: (현재 노드) → (왼쪽 서브트리) → (오른쪽 서브트리)즉, 노드를 방문하자마자 그 노드의 정보를 처리(예: 출력)한 후, 왼쪽→오른쪽 순으로 내려갑니다.(2) 특징루트(root)를 가장 먼저 방문하므로, 트리 구조를 (부모-자식) 순서대로 파악하기 쉽습니다.예를 들어, 트리를 복원하거나 계층적인 구조를 직관적으로 출력할 때 유용합니다.중위 순회(Inorder)(1) 정의 및 순서순회 순서: (왼쪽 서브트리) → (현재 노드) → (오른쪽 서브트리)왼쪽 서브트리를 모두 방문한 뒤, 현재 노드를 방문하고, 그 다음 오른쪽을 방문합니다.(2) 특징이진 탐색 트리(B..

주의제 능력 부족으로 딱히 도움이 안될 확률이 높습니다문제는 여기에서 https://imgur.com/you-can-actually-win-snake-who-knew-ord27qI문제 자체는 고오전 게임인 뱀 게임을 구현하는 내용이다.게임판을 생성하고, 그 위에 뱀이 먹으면 길어지는 사과를 놓고뱀이 사과를 먹으면 길어질 뿐인 단?순한 게임이다결론부터 말하면, 난 이 문제를 하루종일 붙들게되었다뭐 다른 문제들도 다 비슷한 상황이지만가장 많은 시간을 차지한건 구현 구상인데,도저히 어떻게 큐를 사용해서 게임을 구현하라는건데 라는 생각만 계속 맴돌았다그간 해온건 배열, 탐색뿐인데 아니 들어오고 나가는게 왜 뱀이되는건데..반나절을 그렇게 시간을 보내고, 결국 기계의 손을 빌렸다그렇다, 내 수 시간은 그에게 단 '..

Divide and Conquer큰 문제를 여러 개의 작은 부분 문제로 분할(Divide)하고,각 부분 문제를 독립적으로 해결(Conquer)한 후그 결과를 결합(Combine)하여 원래 문제의 해가 되도록 만듬 특성재귀적 접근 :문제를 계속해서 작은 단위로 분할하며, 각 단계마다 동일한 전략을 반복해서 적용문제 단순화 :복잡한 문제를 여러 개의 간단한 문제로 나누어, 각 부분 문제에 대해 쉽게 해결병렬 처리 가능성 :하위 문제들이 서로 독립적일 경우, 병렬 처리하여 전체 수행시간을 줄일 수 있음분할 및 합병 오버헤드 :재귀를 활용하기 때문에, 분할하고 결합하는 과정에서 추가적인 연산과 메모리 사용이 발생할 수 있음흐름분할(Divide)해결할 문제를 여러 개의 하위 문제로 나눔. 이 때 하위 문제는 동일..

정의일반적인 형태는 함수 자신을 사용하여 정수 또는 실수에 대해 함수를 표현하는 방정식 또는 부등식. 둘 이상의 케이스는재귀 케이스 - 더 작은 입력에 대한 함수의 재귀호출이 포함베이스 케이스 - 재귀 호출이 포함되지 않음예시한 수열 {$a_n$}가 있을 때 점화식은a_n = f(a_{n-1}, a_{n-2}, ... , a_{n-k})f는 함수(연산)이며, a_n을 구할 때, 이전 항들 (a_{n-1},a_{n-2},....)의 값을 사용1차 선형 점화식 : a_n = c • a_{n-1} 한 단계 전 항만 이용2차 선형 점화식 : a_n = p • a_{n-1} + q • a_{n-2} 두 단계 전 항까지 이용피보나치 수열 : F_n = F_{n-1} + F_{n-2}, (n ≥ 2)$ (초기값 F..

$O(n^2)$(평균)버블정렬 (단순 교환 정렬)이웃한 두 원소의 대소관계를 비교하여 필요에 따라 교환을 반복$T(n) = O(n^2)$최대 $n(n-1)/2$번 정렬가장 성능이 안좋은 정렬셰이커 정렬버블정렬을 개선한 정렬홀수 반복 : 가장 작은수를 앞으로, 짝수 반복 : 가장 큰 수를 뒤로전체 반복(while) 구간에서 for문이 두개가 들어있음(이중x)선택 정렬 (Selection sort)모든 수를 훑어서 가장 작은(또는 큰) 것을 1번째, 2번째… (n-1)번 반복한다최대 $n(n-1)/2$에 비례하는 시간 소요 $O(n^2)$삽입 정렬 (Insertion sort)k번째 원소를 1부터 k-1 까지와 비교해 적절한 위치에 넣고, 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식평균적으로 3 종류 중 빠..