개발새발

최소 스패닝 트리(Minimum Spanning Tree, MST)를 찾는 문제는 크루스칼(Kruskal) 알고리즘이나 프림(Prim) 알고리즘을 사용하여 해결할 수 있습니다. 크루스칼 알고리즘과 다익스트라 알고리즘 모두 그래프의 모든 정점들을 연결하는 최소 비용의 트리를 찾는 데 사용됩니다.크루스칼 알고리즘은 간선을 가중치에 따라 정렬하고, 가장 작은 간선부터 시작하여 사이클을 만들지 않는 한 트리에 추가하는 방식으로 동작합니다.모든 간선을 가중치 순으로 정렬합니다.각 간선을 순서대로 확인하면서, 해당 간선을 추가해도 사이클이 생기지 않으면 트리에 추가합니다.사이클이 생기지 않는다는 것을 확인하기 위해서 Union-Find 자료구조를 사용합니다.*Union-Find 자료구조는 서로소 집합(Disjoin..

다익스트라 알고리즘은 그래프 이론에서 주어진 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘으로, 가중치가 있는 그래프에서 최단 경로를 찾는 문제를 해결하는 데 사용됩니다. (그래프 이론 + dp)다익스트라 알고리즘 개요다익스트라 알고리즘은 다음과 같은 단계로 동작합니다:출발 노드 선택: 시작 노드를 선택하고, 시작 노드의 최단 경로를 0으로 초기화합니다.우선순위 큐 활용: 출발 노드부터 갈 수 있는 모든 경로를 우선순위 큐(힙)에 넣습니다. 시작 노드의 최단 경로가 0이므로 시작 노드를 우선순위 큐에 넣습니다.최단 경로 갱신: 우선순위 큐에서 최소 비용의 노드를 꺼내서 해당 노드에서 갈 수 있는 모든 노드들의 최단 경로를 갱신합니다. 이 때, 기존 경로보다 더 짧은 경로를 발견하면 해당 ..

코딩 테스트에서 자주 출제되는 주요 알고리즘 종류와 각 알고리즘의 특징, 그리고 어떤 문제 유형에 어떤 알고리즘이 적합한지에 대해 알아보겠습니다.1. 그리디 알고리즘 (Greedy Algorithm)특징: 각 단계에서 가장 좋아 보이는 선택을 하며 최종적인 해답에 도달하는 방법.적용 예시: 최적의 해를 구하는 것이 중요하고, 각 선택이 서로 간섭이 없을 때 (즉, 한 선택이 다른 선택에 영향을 미치지 않을 때).2. 분할 정복 (Divide and Conquer)특징: 문제를 더 작은 문제로 나누어 해결한 후, 결과를 합쳐서 전체 문제의 해를 구함.적용 예시: 큰 문제를 작은 문제로 분할하여 해결할 수 있는 경우, 주로 재귀적으로 구현됨.3. 동적 계획법 (Dynamic Programming)특징: 이전..

투 포인터(Two Pointers) 알고리즘은 배열이나 리스트에서 특정 조건을 만족하는 부분 배열이나 부분 집합을 찾기 위해 두 개의 포인터를 사용하는 기법입니다. 이 기법은 주로 배열을 효율적으로 탐색하면서 O(N^2) 이상의 시간 복잡도를 O(N)으로 줄일 때 사용됩니다.투 포인터 기법의 기본 원리포인터 초기화:배열의 시작 위치에 두 개의 포인터를 설정합니다. 일반적으로 하나는 start 포인터, 다른 하나는 end 포인터입니다.포인터 이동:조건을 만족할 때까지 두 포인터를 이동시킵니다.각 포인터의 이동은 문제의 조건에 따라 다릅니다. 예를 들어, 부분합이 일정 값을 넘는 경우 start 포인터를 이동시키고, 그렇지 않으면 end 포인터를 이동시킵니다.조건 만족 확인:두 포인터가 가리키는 구간이나 값..