분류 전체보기

[백준][Gold1]11401-이항계수3-JAVA

[문제] www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 1. 정수론에서의 합동 우리는 보통 합동이라는 단어를 도형의 합동을 얘기할 때 사용한다. 그런데 정수끼리의 관계를 얘기할 때도 합동이라는 개념이 존재한다. 정수론에서 합동은 어떤 개념일까? A: 비행기가 13시에 출발한다고? B: 응, 1시에 출발해 13과 1은 다른 숫자임에도 시각에서는 동일시된다. 우리가 쓰는 시계를 12시 단위이기 때문에 12로 나눈 나머지만 말해도 소통이 가능하다. 정수론에서도 마찬가지다. 정..

[백준][Gold1] 구간 합 구하기 - JAVA

[문제] www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리 자료구조를 이용해야 한다. 세그먼트 트리는 구간들을 보존하고 있는 트리로 구간합, 구간 곱 등을 구할 때 사용할 수 있다. [code] package com.algorithm.baekjoon.gold; import java.io.*; import java.util.StringTokenizer; public class Test03 ..

[백준][Gold1] 책 페이지 - JAVA

[문제] www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net [풀이] ✅구하려는 것: 1 ~ N까지의 숫자에 0~9가 각각 몇번 등장하는가 ✅규칙 * A=1, B=N으로 둔다. (ex. A=1, B=678) 1. ☝🏼정해진 약속: A의 일의자리는 항상 0, B의 일의자리는 항상 9여야 한다. 만약 아니라면 B--, A++ 하여 숫자를 변형해준다. A ~ B까지 일의자리에 0~9가 몇번들어가는가 2.예시의 A=1, B=678를 위 규칙대로 변형하면 A = 10, B=669가 된다. 이때, B = 678 -> 669로 변형되면서 숫..

[Java] 에라토스테네스의 체 - 소수 판별

[에라토스테네스의 체] - 가장 대표적인 소수 판별 알고리즘. 소수(Prime)이란 양의 약수를 1과 자기자신만 가지고 있는 자연수. - 대량의 소수를 빠르게 구하는 방법 * 일반적인 소수 판별 코드 (시간 복잡도: O(N)) boolean isPrime(int x) { for (int i=2; i < x; i++) { if (x % i == 0) { return false; } } return true; } [에레토스테네스의 체 동작 방식] ex) 1~25에서 소수 판별 1. 소수를 판별하고자하는 범위 크기의 배열을 정의하고 숫자들을 배열에 넣어준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2. 2부터 시작해서 특정 숫자의 ..

[백준][Gold1] 제곱ㄴㄴ수 - JAVA

[문제 설명] www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net 문제는 간단하지만 풀다보니 시간효율성을 통과하는 것이 까다로워 가히 Gold 레벨에 있는것이 납득이 가는 문제다. 문제를 읽고 일반 코드로 풀어보니 시간 초과가 나면서 통과하지 못했다. 에라토스테네스의 체 원리를 이용하여 된다. [JAVA code] package com.algorithm.baekjoon.silver5; import java.io.BufferedReader; imp..

[백준][silver5][JAVA] 1010-다리 놓기

[문제 설명] www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net [풀이 과정] M개 중에 N개 선택하여 조합하는 경우의 수를 구하는 문제다. 조합 경우의 수를 구하는 방법은 여러가진데 메모이제이션을 이용하면 가장 효율적으로 풀 수 있다. * 메모이제이션을 이용한 조합 경우의 수 구하기 - 메모이제이션(memoization) 기법은 동적 프로그래밍의(dynamic programming)의 일종이다. 메모를 할 배열을 만들어 놓고 처음 계산한 값은 배열에 저장한다..