알고리즘 - Baekjoon/Gold

[백준] 1963번 : 소수 경로 Gold4(골드4) - JAVA[자바]

[Gold IV] 소수 경로 - 1963 문제 링크 성능 요약 메모리: 17916 KB, 시간: 200 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색, 수학, 정수론, 소수 판정, 에라토스테네스의 체 제출 일자 2023년 11월 28일 10:41:32 문제 설명 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야" “그럼 8179로 해” “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가..

[백준] 2447번 : 별 찍기 Gold5(골드5) - JAVA[자바]

[Gold V] 별 찍기 - 10 - 2447 문제 링크 성능 요약 메모리: 68452 KB, 시간: 280 ms 분류 분할 정복, 재귀 제출 일자 2023년 11월 27일 09:25:23 문제 설명 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. 입력 첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉..

[백준] 11729번 : 하노이 탑 이동 순서 Gold5(골드5) - JAVA[자바]

[Gold V] 하노이 탑 이동 순서 - 11729 문제 링크 성능 요약 메모리: 100692 KB, 시간: 416 ms 분류 재귀 제출 일자 2023년 11월 26일 12:12:23 문제 설명 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 입력 첫째 줄에 첫 번째 장대에 쌓인..

[백준] 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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 ..

[백준] 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. 천천히 확장해나가면서 ..

[백준] 12886번 : 돌 그룹 Gold5(골드 5) - JAVA[자바]

[Gold IV] 돌 그룹 - 12886 문제 링크 성능 요약 메모리: 50696 KB, 시간: 196 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2023년 11월 21일 10:59:00 문제 설명 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다. 강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다. 크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다. A, B, C가 주어..

[백준] 16928번 : 뱀과 사다리 게임 Gold5(골드 5) - JAVA[자바]

[Gold V] 뱀과 사다리 게임 - 16928 문제 링크 성능 요약 메모리: 12972 KB, 시간: 112 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2023년 11월 17일 10:37:28 문제 설명 뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다. 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까? 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다. 플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어..