본문 바로가기

Algorithm54

[백준 Gold 1] 2357 최솟값과 최댓값 - Java 문제링크 : https://www.acmicpc.net/problem/2357 접근 과정 : https://rays-space.tistory.com/84 [백준 Gold 1] 10868 최솟값 - Java 문제링크 : https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만.. rays-space.tistory.com 위 문제와 같은 같은 문제이다. 위 문제에서 사용했던 세그먼트 트리를 활용하기 위해 해당 문제를 풀게 되었다. 최솟값과 최댓값을 의미하는 세그먼트 트리를 각각 만들어서 문제를 해결했다. 소스 코드 및 결과 .. 2022. 1. 10.
[백준 Gold 1] 10868 최솟값 - Java 문제링크 : https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 접근 과정 : 특정 범위가 주어졌을 때, 해당 범위 내의 최솟값을 찾는 문제다. 숫자와 질의 입력이 최대 100,000까지 주어지기 때문에, 일반적인 탐색으로는 힘들것이라고 생각했다. 세그먼트 트리를 사용해 보았다. 내가 이해한 세그먼트 트리는, 특정 범위 내에서의 값(최대값 혹은 최솟값 등)을 노드에 표시하는 것이다. 노드 1은 1~N까지의 값 중.. 2022. 1. 10.
[백준 Silver 1] 11048 이동하기 - Java 문제링크 : https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 접근 과정 : 해당 문제는 DP를 이용해서 풀수 있다. DP[r][c] = maze[r][c] + Math.max(dp[r-1][c], Math.max(dp[r][c-1], dp[r-1][c-1])) 이다. Top-down 과 Bottom-up으로 풀어보았다. 소스 코드 및 결과 : package BOJ; /* 이동하기 Top-down */ import java.io.*.. 2022. 1. 7.
[백준 Silver 3] 3085 사탕 게임 - Java 문제링크 : https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 접근 과정 : 초기 상태에서 가장 많이 사탕을 먹을 수 있는 경우를 계산 사탕을 바꿀 수 있는 경우들을 탐색하며, 바꿨을 때 먹을 수 있는 사탕의 개수를 계산 사탕의 개수를 계산할 때마다, 최대값을 갱신하여 리턴. + 사탕의 실제 값은 바꾸지 않고 좌표로만 확인한다. 소스 코드 및 결과 : package BOJ; /* 사탕 게임 */ import java.io.*; public class BOJ3085 { public static void main(String[] args) throws NumberFo.. 2022. 1. 7.

티스토리툴바