알고리즘3 [DFS,BFS] 백준 2583 영역구하기 C++ https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 : 풀이 : bfs 문제 중에 그림(백준 1926) 문제와 유사해서 그걸 풀었던 방식과 비슷하게 풀었다. 좌표의 최대값(100)크기의 이차원 배열을 만들어서 색칠된 부분을 1 색칠이 안된 부분을 0으로 두고 bfs 탐색을 통해 0인 부분의 넓이를 구하는 방법이다. 이런 식으로 구해진 넓이는 우선순위 큐에 넣어서 오름차순으로 정렬하여 출력가능 단, 조금 주의해야 할 점이 있.. 2021. 8. 16. [그리디] 백준 13305 주유소 C++ https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 : 그리디 알고리즘을 이용하는 문제이므로 최소가격으로 이동하려면 가장 싼 기름 값으로 많이 주유하면 된다! 접근 방법 자체는 쉬운문제지만 메모리 범위 라던지 구현에서 생각보다 삽질을 많이 함.. 처음에는 city 구조체를 정의해서 vector에 넣어서 풀었는데 굳이 그렇게 할필요가 없었다. 거리와 가격이 최대 1,000,000,000 까지 입력되므로 int로 계산하면 오버플로우.. 2021. 8. 13. [DP] 백준 12865 평범한 배낭 C++ https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 처음 읽고 쉬워 보여서 2시간넘게 고민 했는데 풀지못했다.. 결국 풀이를 찾아 봤는데 knapsack알고리즘 이라고 꽤나 유명한 알고리즘이다. 나중에 알고리즘 관한 부분은 따로 정리해서 업로드 할 예정. 내가 생각하지 못한 솔루션은 무게 남을 때 어떻게 최댓값을 찾을 것인가(코드상으로 dp[i-1][j-weight])부분이었다. 천.. 2021. 8. 12. 이전 1 다음
