728x90 전체 글335 백준 11779번 최소비용 구하기 2 C++ 1. 문제 설명 n개의 도시가 있다.한 도시에서 출발하여 다른 도시에 도착하는 m개의 버스가있고A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소 비용과 경로를 구하는 문제. 다익스트라 문제 2025. 5. 28. 백준 10968번 나머지 합 C++ 1. 문제 설명 수 N개 A1, A2, .... An이 주어진다.이때 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성해라즉 A[i] ~ A[j] 의 합이 M으로 나누어 떨어지는 (i,j) 쌍의 개수를 구하는 문제이다. 처음 이분탐색을 이용한 문제로 파악을 하였고 시간초과가 나와 다른 방법을 찾아본 결과 누적합 + 조합에 대한 문제였다.nC2 공식을 사용하여 문제를 풀 수 있다. 2025. 5. 28. 백준 9465번 스티커 C++ 1. 문제 해결문방구에서 스티커 2n개를 구매했다.스티커는 2행 n열로 배치되어 나온다.해당 스티커로 책상을 꾸미려고 하는데스티커를 한장 떼면 해당 스티커의 상하좌우에 있는 스티커에도 영향을주어 사용할 수 없게 되어버린다.각 스티커에는 값어치가 매겨져있어 그 값어치를 최대로 하게 끔 스티커를 떼어 책상을 꾸미려고 한다. 처음 dfs + 백트래킹 문제라고 생각하여 문제를 풀어보려고 하였으나 점점 산으로 가는 코드에 다른 방법이 있는것을 알았다이 문제는 dp를 이용한 문제로 점화식을 찾아 푸는 문제이다. 2025. 5. 27. 백준 1753번 최단 경로 C++ 1. 문제 설명방향 그래프가 주어졌을 때, 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성단 모든 간선의 가중치는 10 이하의 자연수로 이루어져있다. V,E 정점의 개수와 간선의 개수가 첫째줄에 주어지고K 둘째 줄에 시작 정점 번호가 주어진다. K부터 다른 모든정점으로의 최단 경로를 구하면 된다.가중치를 고려한 최단거리 노드로 된 길찾기 문제로 Dijkstra 알고리즘을 이용하여 풀 수 있다. 최소 비용으로 갈수 있는 노드를 꺼내고그 노드에서 갈 수 있는 정점들을 전부 본다.더 싸게 갈 수 있는 곳이 있다면 갱신하고, 큐에 넣는다.큐가 빌 때까지 반복하면 가장 싼 값이 남게 된다. 2025. 5. 27. 이전 1 2 3 4 5 6 ··· 84 다음 728x90
