전체 글

[백준][gold5] 14502번: 연구소 - JAVA

[문제] www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [풀이 내용] * 알고리즘 분류 - 부르트포스 알고리즘 - 너비 우선 탐색 0으로 표시된 빈칸들 중에 3곳을 골라 벽을 세워야 한다. 어떻게 3곳을 골라야 가장 안전 영역을 많이 확보할 수 있는지 모르므로 경우의 수를 모두 해봐야 한다. 그 다음 각 경우마다 바이러스가 퍼질 수 없는 안전 영역의 크기를 구하고 그 중 최댓값을 출력한다. 1. 연구소 2차원 배열에서 0으로 표시된 칸들 중에 3가지를 선택하는 경우의 ..

[백준][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)의 일종이다. 메모를 할 배열을 만들어 놓고 처음 계산한 값은 배열에 저장한다..

[백준][silver4][JAVA]터렛

[문제 설명] www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net [풀이 과정] 조규현, 백승환 각 좌표와 떨어진 거리를 반지름으로 원을 그려보면 두 원이 만나는지 여부를 알 수 있다. 두 원이 만나는 접점의 개수가 류재명이 있을 수 있는 좌표의 개수이다. 총 6가지 경우가 있다. 1. 두 점에서 만남 한 점에서 만남 2. 외접 3. 내접 반지름의 차 r1 + r2) 5. 두 중점 거리 < 반지름의 차이 (d < r2 - r1) 6. 두 중점..

[프로그래머스][Level3][Java]징검다리 건너기

[문제 설명] programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr [풀이 과정] 파라매트릭 서치(Parametric search)를 이용하여 푸는 문제다. 단순 코딩으로도 문제를 풀수는 있지만 파라매트릭 서치를 활용하지 않으면 효율성 체크에서 실패가 난다. 파라매트릭 서치는 이분탐색과 유사한 알고리즘으로 최적화 문제를 결정 문제로 바꾸어 푸는 것이다. * 최적화 문제 - 최적의 해가 무엇인가를 묻는 문제 - 주로 문제 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제 * 결정 문제 - 어떤 조건이 예-아니요로 답이 있는 문제 예시)..