개발새발

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

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

여러 사이트와 블로그, 카페, 백준 추천 문제를 참고하여 코테에 최적화된 문제 리스트를 정리해봤다기본 문제는 문제를 보자마자 풀수 있어야 하고, 그 외 문제들은 고민 시간이 1시간을 넘어간다면 해설을 보길 추천한다너무 축약된 코드는 제외하고 설명이 있는 코드를 보면서 문제 풀이 로직을 익혀야한다. ex) 이 문제에서는 왜 이런 공식(알고리즘)을 써서 풀었는지 등등 풀었던 문제도 여러 가지 풀이가 있을 수 있기 때문에 다른 풀이를 확인해보는 것도 좋다@.@ 1. 기본문제2501, 3460, 10818, 2460, 10870, 2309, 2693, 1978, 1292, 2581입출력 - 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 1..