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

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번째 요소까지의 가장 긴 증가하는 부분 수열의..

개념 최소 신장 트리(MST,  Minimum Spanning Tree)연결된 무방향 가중치 그래프에서 모든 정점을 포함하면서, 가중치의 합이 최소가 되는 트리  위 내용은 gpt가 설명하는 MST의 정의입니다. 두 정점 사이의 간선이 서로 다른 가중치를 가지는 그래프에 대하여 최소 신장 트리는 다음과 같은 특징을 만족합니다. 모든 정점을 포함사이클이 없음 간선의 가중치 합이 최소 아래 그래프를 예시로 들어보겠습니다.  위 그래프에서 최소 신장트리는 다음과 같습니다. 최소 신장 트리를 구하는 대표적인 알고리즘은 크루스칼과 프림 알고리즘이 있습니다. 이번 게시물에서는 그 중 크루스칼에 대해 알아보고자 합니다.  크루스칼 알고리즘(kruskal's Algorithm)간선을 가중치 순(오름차순)으로 정렬한 후..

설명  그래프 내에 존재하는 두 정점 사이의 최단 경로를 찾는 알고리즘. 모든 정점 쌍에 대한 최단 경로를 계산할 수 있다. 만약 정점의 개수가 n일 경우 n * n크기의 2차원 배열을 생성한 뒤, 각 정점 사이의 거리를 초기화해준다. 이후 그래프 내 모든 정점을 중간 정점으로 사용하여 가능한 경로를 탐색해 나간다. 만약 a에서 b로 가는 경로를 구할 때, 중간 정점을 c라 한다면 a -> c에서 c->b로 가는 경로의 거리와 비교해 최단 거리를 갱신한다. 이 과정을 반복하여 모든 정점 사이의 최단거리를 구한다.  시간 복잡도: O(n3) 알고리즘 문제에서는 보통 정점의 개수가 약 100 ~ 1000개 정도로 나온다. 예시  아래와 같은 그래프의 최단 경로를 구할 경우 먼저 거리의 배열을 초기화 한다. ..