zyeon's 작심삼일 코딩 공부

보호되어 있는 글입니다.

투 포인터 알고리즘은 두 개의 포인터를 사용해 주어진 데이터를 탐색하거나특정 조건을 만족하는 부분집합이나 부분수열을 찾는 알고리즘이다. 주로 정렬된 배열이나 연속적인 구간을 다룰 때 사용한다.부분합 1806더보기문제10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.입력첫째 줄에 N (10 ≤ N 출력첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.문제풀이부분합의 시작점을 가리키는 start 포인터, 끝점을 가리키는 end 포인터를 시작 위치(0)로 설정해준다.합이 s이상이 될 때까지 end 포인터를 ..

다익스트라 알고리즘은 최단 경로 탐색 알고리즘으로,가중치가 양수인 그래프에서 사용 가능하다.우선순위 큐를 사용해 데이터를 우선순위가 높은 노드부터 탐색을 확장한다.최소비용 구하기 1916더보기문제N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.입력첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출..

백트래킹은 모든 경우의 수를 따져야 할 때 유용한 기법이다.해를 찾는 과정에서 가능하지 않는 경로는 미리 포기해 불필요한 연산을 줄여주어경우의 수가 많아도 가능한 해만을 탐색해 효율적으로 문제를 풀 수 있다. 백트래킹이 자주 쓰이는 대표적인 상황은순서 조합 및 순열 문제, 특정 조건을 만족하는 부분 집합을 구할 때, 그래프 탐색, 최적 해 구하기, 퍼즐 문제 등이 있다.가르침 1062더보기문제남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K..