성장하고 개발하는 계란의 이야기

LIS(Longest Increasing Subsequence )개념  주어진 배열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 코드. DP 방식이나 이분 탐색을 이용하여 풀 수 있다.  예를 들어, 배열 [10, 20, 10, 30, 20, 50]가 주어졌을 때, 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]로 길이는 4가 된다. 문제 풀이 방식동적 프로그래밍(DP) 방식 - 시간 복잡도: O(n^2)이분 탐색을 이용한 최적화 방식 - 시간 복잡도: O(n log n) 풀이 방식(DP)배열을 순서대로 탐색하면서 dp 배열을 갱신해나가는 방식. 각 위치에서 해당 위치까지의 가장 긴 증가하는 부분 수열의 길이를 저장한다.점화식: dp[i]는 i번째 요소까지의 가장 긴 증가하는 부분 수열의..

개념 최소 신장 트리 아래 링크 참조  [알고리즘]크루스칼 알고리즘(kruskal's Algorithm) 정리개념 최소 신장 트리(MST,  Minimum Spanning Tree)연결된 무방향 가중치 그래프에서 모든 정점을 포함하면서, 가중치의 합이 최소가 되는 트리  위 내용은 gpt가 설명하는 MST의 정의입니다. 두 정점 사growingegg.tistory.com 프림 알고리즘   최소 신장 트리를 찾기 위해 사용되는 알고리즘. 트리에 포함된 정점을 제외한 나머지 정점과의 간선 중 가중치가 가장 작은 간선을 선택하는 방식  아래와 같은 그래프가 있다고 가정하겠습니다. 1 번 정점부터 시작으로 간선을 확인합니다. 트리에 포함된 정점은 주황색으로 표시하였습니다. 1번에 연결된 간선은 1 - 3과 1 ..