⌨️코딩테스트/백준17 [JAVA/백준/11660] 구간 합 구하기 5 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 방법 구간합은 특정한 구간의 합을 의미합니다. 왼쪽과 같은 입력이 주어졌을 때 해당 칸의 앞 칸까지의 모든 수의 합을 더한 값이 구간합이 됩니다. 만약 2열 2행부터 3행 3열까지의 구간합을 구하고 싶다면 다음과 같이 구할 수 있습니다. 1행 1열부터 3행 3열까지의 구간합에서 회색 구간을 빼주고 겹쳐지는 노란 색 한 칸을 더하면 최종적으로 구하고자하는 구간의 합을 구할 수 있습니다. 결과 코드 BufferedRea.. 2023. 7. 12. [JAVA/백준/2457] 공주님의 정원 / Greedy 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 이 문제는 그리디 알고리즘을 사용하여 풀 수 있다 풀이과정은 다음과 같다 꽃을 시작 날짜를 기준으로 정렬, 시작 날짜가 같다면 종료 날짜를 기준으로 정렬 꽃의 시작 날짜가 현재 날짜보다 크면 탐색을 종료 현재 날짜보다 작거나 같은 시작 날짜를 가진 꽃 중 끝나는 날짜가 가장 큰 꽃을 선택 선택한 꽃의 끝나는 날짜를 기준으로 다시 시작 위와 같은 과정을 반복하면 최대로 심을 수 있는 꽃의 수를 계산할 수 있으며 자세한 설명은 주석으로 달아놨다 .. 2023. 3. 27. [JAVA/백준/1520] 내리막길 / DP, DFS 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 이 문제는 출발점에서 도착점까지 가는 경로의 수를 구하는 것이다 DFS를 통해 도착하는 모든 경로를 얻을 수 있지만 시간초과가 발생하게 된다 같은 경로를 중복해서 탐색할 수가 있기 때문에 시간 복잡도를 효율적으로 개성해야 한다 따라서 DFS + DP를 이용해 풀이를 했다 우선, DFS를 이용해 출발점에서 도착점까지 모든 경로를 탐색하는데 현재 위치에서 갈 수 있는 높이가 낮은 지점으로 이동하면서 경로의 수를 누적한다. 이미 계산한 경로는 중복 계산하지 않도록 .. 2023. 3. 25. [JAVA/백준/1495] 기타리스트 / DP 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 풀이 과정 기타의 볼륨을 조절하여 연주할 수 있는 곡 중에서, 마지막 곡을 연주할 때 볼륨의 최댓값을 구하는 문제다 이 문제를 해결하기 위해서는 가능한 모든 볼륨을 조합해봐야 하며 시간과 메모리를 적게 소모하기 위해서는 동적 계획법(Dynamic Programming)을 사용할 수 있다 우선 입력값을 받아와서, 가능한 볼륨을 저장하는 배열인 dp를 초기화한다 그리고 첫번째 곡을 연주할 때, 현재 볼륨(S)을 인덱스로 가지는 .. 2023. 3. 20. [JAVA/백준/16400] 소수 화폐 / DP 16400번: 소수 화폐 구매하려고하는 물건의 값 N(2 ≤ N ≤ 40,000, N은 정수)이 주어진다. www.acmicpc.net 풀이 과정 처음엔 모든 경우의 수를 따져가며 규칙을 찾았다 2 = 2 3 = 3 4 = 2 + 2 5 = 2 + 3, 5 6 = 2 + 2 + 2, 3 + 3 7 = 2 + 2 + 3, 2 + 5, 7 8 = 2 + 2 + 2 + 2, 2 + 3 + 3, 3 + 5 현재 수에서 소수만큼을 뺀 경우의 수를 모두 더하면 될 것 처럼 생겼다 우선 에라토스테네스의 체를 만들어 소수를 뽑았다 그 후 dp 배열을 만들고 dp[0] = 1을 넣은 다음에 점화식을 다음과 같이 유도했다 case 2 dp[2] += dp[2 - 2] dp[3] += dp[3 - 2] dp[4] += dp.. 2023. 3. 15. [JAVA/백준/16236] 아기상어 / BFS 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 과정 이 문제는 BFS를 구현하면 되는 문제지만 조건이 매우 복잡하다 이동 조건은 다음과 같다 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 감 먹을 수 있는 물고기가 1마리보다 많다면, 다음 우선 순위로 먹으러 감 거리가 가까운 순서 위, 왼쪽으로 가까운 순서 더 이상 먹을 수 있는 물고기가 공간에 없다면 종료 상어의 이동은 1초가 걸림 상어는 자신의 크기만큼 물고기를 먹으면 크기가 1 커짐 위 조건들을 맞추면서 BFS 탐색을 해야한다 하나.. 2023. 1. 5. 이전 1 2 3 다음
