백준

[백준] 14719 빗물 (JAVA)

✉️문제 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 📝 접근 왼쪽에 있는 기둥의 최대값(LM)과 오른쪽에 있는 기둥의 최대값(RM)을 구한다. LM과 RM의 최소값을 구한다. 최소값 - 현재 인덱스의 높이 🗝 문제풀이 public class Q14719_B { static int[] heights; public static void main(String[] args) { Scanner sc = new Scanner(Sys..

[백준] 2504 괄호의 값

✉️문제 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 📝 접근 분배법칙을 이용하면 쉽게 풀 수 있다. 일단 stack과 Tmp 변수를 준비하자. 여기에 분배법칙을 한 값들을 더 해줄 예정이다. 1. ‘(’이면 tmp변수에 2를 곱해준다. 2. ‘[’이면 tmp변수에 3을 곱해준다. 3. ‘)’일 때 a. 만약 stack이 비어있거나, ‘(’가 아니면 잘못된 입력이므로 종료한다. b. 이전 문자가 ‘(’ 이면 answer에 tmp를 더 해준..

[백준] 4375 1로만 이루어진 n의 배수(Java)

✉️문제 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 📝 접근 1로만 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력하면 된다. 이 때 1로만 이루어진 배수가 자료형의 범위를 넘어갈 수 있으므로, 혹은 더 효율적인 계싼을 위해서 나머지 연산을 이용한다. num = (num * 10) + 1; num = num % n; 🗝 문제풀이 import java.util.Scanner; public class B4375RRR { public static void main(String[] args) { Sc..

[백준] 10430 나머지 (Java)

✉️문제 https://www.acmicpc.net/problem/10430 10430번: 나머지 첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000) www.acmicpc.net 📝 접근 컴퓨터의 정수는 저장할 수 있는 범위가 지정되어 있기 때문에, 답을 M으로 나눈 나머지를 출력하는 문제가 등장한다. 이 때 다음과 같은 성질을 이용해서 int또는 long과 같은 자료형의 범위로 제한해주어야 한다. (A + B) mod M = (( A mod M ) + ( B mod M )) mod M (A x B) mod M = (( A mod M) x ( B mod M )) mod M (A - B ) mod M = (( A mod M) - (B mod M) mod M 🗝 문제풀이 위..

[알고리즘] 소수 알고리즘

소수를 구하는 알고리즘을 알아보자. 소수의 정의를 이용한 방법 N이 소수이면 2 ~ (N-1)로 나누어 떨어지지 않는다. 이 경우 2부터 N-1까지 연산이 필요하기 때문에 O(N)의 시간복잡도가 걸린다. 약수의 특징을 이용한 방법 N이 소수가 되려면, 2이상이고, N/2 이하의 자연수로 나누어 떨어지면 안된다. (N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같다) 여전히 O(N)의 시간 복잡도를 갖는다. 약수의 특징을 이용한 방법2 모든 수의 약수는 루트 N을 기준으로 대칭을 이룬다. 루트 N의 값 왼쪽에 있는 값을 기준으로 값 들을 조합해 대칭 오른쪽에 있는 수의 값을 구할 수 있다. O(루트 N)의 시간 복잡도를 가진다. 컴퓨터에서 실수는 근사값을 나타내기 때문에, 루트 N과 같은 경우는 다음 ..