알고리즘 - Baekjoon/Gold
[백준] 15711번 : 환상의 짝궁 Gold3(골드3) - JAVA[자바]
[Gold III] 환상의 짝꿍 - 15711 문제 링크 성능 요약 메모리: 18396 KB, 시간: 928 ms 분류 수학, 정수론, 소수 판정, 에라토스테네스의 체 제출 일자 2023년 12월 18일 16:00:43 문제 설명 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이어붙이고 그 끈을 다시 길이가 소수인 끈 두개로 정확히 나눌 수 있다면 두 사람은 환상의 짝꿍이라고 한다. 하지만 그들은 길이가 소수인 두개의 끈으로 나눌 수 있는지 판단하는 것이 어려워서 대부분 서로가 인연임을 모르고 그냥 지나간다고 한다. 애석하게도... 그런 그들을 위해서 어떤 두 사람이 환..
[백준] 1644번 : 소수의 연속합 Gold3(골드3) - JAVA[자바]
[Gold III] 소수의 연속합 - 1644 문제 링크 성능 요약 메모리: 24836 KB, 시간: 184 ms 분류 수학, 정수론, 소수 판정, 에라토스테네스의 체, 두 포인터 제출 일자 2023년 12월 17일 16:43:06 문제 설명 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한..
[백준] 2580번 : 스도쿠 Gold4(골드4) - JAVA[자바]
[Gold IV] 스도쿠 - 2580 문제 링크 성능 요약 메모리: 16048 KB, 시간: 368 ms 분류 백트래킹 제출 일자 2023년 12월 17일 16:20:12 문제 설명 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 위..
[백준] 2661번 : 좋은수열 Gold4(골드4) - JAVA[자바]
[Gold IV] 좋은수열 - 2661 문제 링크 성능 요약 메모리: 13048 KB, 시간: 96 ms 분류 백트래킹 제출 일자 2023년 12월 17일 15:44:25 문제 설명 숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다. 다음은 나쁜 수열의 예이다. 33 32121323 123123213 다음은 좋은 수열의 예이다. 2 32 32123 1232123 길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수..
[백준] 15686번 : 치킨 배달 Gold5(골드5) - JAVA[자바]
[Gold V] 치킨 배달 - 15686 문제 링크 성능 요약 메모리: 14448 KB, 시간: 184 ms 분류 백트래킹, 브루트포스 알고리즘, 구현 제출 일자 2023년 12월 16일 15:30:01 문제 설명 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치..
[백준] 9935번 : 문자열 폭발 Gold4(골드4) - JAVA[자바]
[Gold IV] 문자열 폭발 - 9935 문제 링크 성능 요약 메모리: 39504 KB, 시간: 372 ms 분류 자료 구조, 스택, 문자열 제출 일자 2023년 12월 13일 15:34:52 문제 설명 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는..
[백준] 124-번 : 노드사이의 거리 Gold5(골드5) - JAVA[자바]
[Gold V] 노드사이의 거리 - 1240 문제 링크 성능 요약 메모리: 51564 KB, 시간: 292 ms 분류 너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리 제출 일자 2023년 12월 12일 11:34:45 문제 설명 N$N$개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 입력 첫째 줄에 노드의 개수 N$N$과 거리를 알고 싶은 노드 쌍의 개수 M$M$이 입력되고 다음 N−1$N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M$M$개의 노드 쌍이 한 줄에 한 쌍씩 입력된다. 출력 M$M$개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다. 풀이 방법 1. 각..
[백준] 2668번 : 숫자고르기 Gold5(골드5) - JAVA[자바]
[Gold V] 숫자고르기 - 2668 문제 링크 성능 요약 메모리: 11584 KB, 시간: 80 ms 분류 깊이 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2023년 12월 12일 09:34:56 문제 설명 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자. 이 ..