알고리즘/Java50

• 

  백준 알고리즘 11052번: 카드 구매하기 문제 정보 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 핵심 DP를 얼마나 잘 활용할 수 있을 것인가! 오랜만에 풀어본 문제라 조금 시간이 소요된 것 같다 하지만 이러한 문제는 케이스를 나눠서 생각하다 보면 주변과의 관계가 보이는 것 같다 먼저 문제를 이해해 보면, P(1) P(2) 처럼 괄호 안에 들어있는 작은 숫자는 카드의 개수를 뜻한다. (1) 은 카드 1개가 들어있는 카드팩을 뜻하며, (2)는 카드 2개가 들어있는 카드팩을 뜻한다 P(1)은 카드 1개가 들어있는 카드팩의 가격을 뜻한다. P(1) = 3 이면.. 알고리즘/Java 2024. 3. 19.

• 

  백준 알고리즘 2156번: 포도주 시식 문제 정보 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 핵심 백준 알고리즘: 2579번 계단 오르기 문제 정보 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 blog.dduneon.me 동적 계획법(DP) 알고리즘을 사용하여 문제를 풀이한다 위 링크한 문제인 계단 오르기 문제와 언뜻 보면 비슷해 보이지만, 계단 오르기에 경우에는 한번에 한 계단 혹은 두 계단을 반드시 올라야 .. 알고리즘/Java 2023. 12. 26.

• 

  백준 알고리즘 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.