백준71 백준 알고리즘 2293번: 동전1 문제 정보 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 핵심 이전 글과 동일한 Dynamic Programming을 활용하여 풀이하는 문제이다 기존 문제 대비 점화식 세우는것이 개인적으로 조금 어렵다고 느꼈기 때문에 최대한 처음 문제를 접하는 입장에서 문제를 풀이해보도록 하겠다 문제 유형 잡기 일단 해당 문제는 서두에 설명했듯 DP 알고리즘을 사용하는 문제이다 이를 생각하게 된 몇가지 근거는, 먼저 일반적으로 많이 풀어봤을 법한 잔돈 문제 등은 Greedy 알고리즘이지만 이는 최적의 해를 구해나가는 방식으로.. 알고리즘/Java 2023. 12. 22. 백준 알고리즘 1912번: 연속합 문제 정보 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 핵심 요즘 많이 풀고 있는 Dynamic Programming, DP 알고리즘으로 문제를 풀이한다 정수 n의 개수가 최대 100,000이기 때문에 연속되는 수들의 합의 최대값을 구할 때 모든 경우의 수를 확인하는 것은 매우 비효율적인 방법이고, 심지어 수가 한개일 수도 있으며 연속되기만 한다면 모든 경우를 고려해야 하기 때문에 더더욱 사용하지 말아야 할 것이다 여기서 사용한 방법은 DP(동적 프로그래밍) 방법인데, 각각의 상태에서의 최대 합을 기록하며 풀이를 진.. 알고리즘/Java 2023. 12. 21. 백준 알고리즘 2583번: 영역 구하기 문제 정보 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 핵심 그래프 탐색 알고리즘을 사용하여 문제를 풀이하자! 다만, 처음에 고민되었던 부분은 각 영역의 오른쪽 위 꼭짓점의 좌표값을 어떻게 처리하느냐.. 였는데 꼭짓점을 좌표라고 생각하지 말고, 해당 영역을 좌표라고 생각해 보는 것이 도움이 되었던 것 같다 예를 들어 (0, 0)은 왼쪽 아래 꼭짓점이라고 생각하기보다는 첫번째 (왼쪽 아래) 영역이라고 생각하면 map[0][0]은 해당 영역을 나타내는 값이 되는 것이다 간단하게 그림으로 나.. 알고리즘/Java 2023. 12. 14. 백준 알고리즘: 2636번 치즈 문제 정보 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 핵심 BFS(너비 우선 탐색)을 사용하여 문제를 풀이한다! 이를 사용하는 근거는, 치즈 조각은 한 시간이 지날때 마다 점차 녹아가며 우리가 구해야 하는 것은 모든 경로를 탐색하는 것이 아닌 각자의 위치(공기)에서 녹일 수 있는 치즈를 천천히 녹여가며 모든 치즈가 녹는 데에 걸린 시간과 한 시간 전에 남아있는 치즈 조각을 구하는 것이기 때문이다 사실상 이를 떠올리는 것은 어렵지는 않고, 좀 까다로웠던 것은 (0,0) 부터 맵을 탐색하기 시작하여 0(공기)이면 큐에 추가하고.. 알고리즘/Java 2023. 11. 22. 백준 알고리즘: 9466번 텀 프로젝트 문제 정보 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 핵심 DFS(깊이 우선 탐색)으로 순환을 이루는 학생들을 찾아야 한다 visited 배열을 사용하여 방문한 학생들을 재방문하지 않도록 처리해 주어야 하며 재귀적으로 노드들을 탐색할 때, 해당 부분집합에 순환되는 부분이 존재할 수 있으므로 이를 골라내어 카운팅해주는 방식이 요구되는 것 같다 처음에는, 재귀 호출로 구한 여러명의 학생들 중 일부만 순환 관계에 놓여있다고 했을 때 순환을 이루는 학생들에 대해서만 방문 표시를 해주고, 나머지 학생들에 대해서는 방문.. 알고리즘/Java 2023. 11. 15. 이전 1 ··· 3 4 5 6 7 8 9 ··· 15 다음
