분류 전체보기

[백준] 1850번 : 최대공약수 Silver1(실버1) - JAVA[자바]

[Silver I] 최대공약수 - 1850 문제 링크 성능 요약 메모리: 20048 KB, 시간: 240 ms 분류 유클리드 호제법, 수학, 정수론 제출 일자 2023년 11월 26일 10:38:16 문제 설명 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. 입력 첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 263보다 작은 자연수이다. 출력 첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다. 1. 자리수끼리의 최대..

[백준] 12851번 : 숨바꼭질2 Gold4(골드4) - JAVA[자바]

[Gold IV] 숨바꼭질 2 - 12851 문제 링크 성능 요약 메모리: 22092 KB, 시간: 128 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2023년 11월 25일 12:51:12 문제 설명 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 ..

[백준] 11054번 : 가장 긴 바이토닉 부분 수열 Gold4(골드4) - JAVA[자바]

[Gold IV] 가장 긴 바이토닉 부분 수열 - 11054 문제 링크 성능 요약 메모리: 12540 KB, 시간: 120 ms 분류 다이나믹 프로그래밍 제출 일자 2023년 11월 25일 11:16:22 문제 설명 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 ..

[백준] 1699번 : 제곱수의 합 Silver2(실버2) - JAVA[자바]

[Silver II] 제곱수의 합 - 1699 문제 링크 성능 요약 메모리: 12308 KB, 시간: 124 ms 분류 다이나믹 프로그래밍, 수학 제출 일자 2023년 11월 25일 10:33:09 문제 설명 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게 제곱수들의..

[백준] 9251번 : LCS Gold5(티어) - JAVA[자바]

[Gold V] LCS - 9251 문제 링크 성능 요약 메모리: 15940 KB, 시간: 108 ms 분류 다이나믹 프로그래밍, 문자열 제출 일자 2023년 11월 24일 10:54:51 문제 설명 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 1. DP로 풀 수 있는 대표적인 예제 2. 천천히 확장해나가면서 ..

[백준] 11004번 : K번째 수 Silver5(실버 5) - JAVA[자바]

[Silver V] K번째 수 - 11004 문제 링크 성능 요약 메모리: 663552 KB, 시간: 4136 ms 분류 정렬 제출 일자 2023년 11월 24일 10:09:12 문제 설명 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다. 둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109) 출력 A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt..

[백준] 11652번 : 카드 Silver4(실버4) - JAVA[자바]

[Silver IV] 카드 - 11652 문제 링크 성능 요약 메모리: 38388 KB, 시간: 316 ms 분류 자료 구조, 해시를 사용한 집합과 맵, 정렬 제출 일자 2023년 11월 24일 10:01:04 문제 설명 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다. 입력 첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 출..

[백준] 11722번 : 가장 긴 감소하는 부분 수열 Silver2(실버2) - JAVA[자바]

[Silver II] 가장 긴 감소하는 부분 수열 - 11722 문제 링크 성능 요약 메모리: 12280 KB, 시간: 104 ms 분류 다이나믹 프로그래밍 제출 일자 2023년 11월 24일 09:38:05 문제 설명 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길..