코딩 테스트

[백준][gold5] 9251번: LCS - JAVA

[문제] www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 대학교 알고리즘 수업때 들었지만 기억이 가물가물했다. 아래 유튜브를 보면서 다시 공부했다. www.youtube.com/watch?v=EAXDUxVYquY [코드] package com.algorithm.baekjoon.gold5; import java.io.*; /** * 9251 - LCS */ public class Test04 { public stat..

[백준][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로 변형되면서 숫..

[백준][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..