알고리즘 - Baekjoon
[백준] 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부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치..
[백준] 18111번 : 마인크래프트 Silver2(실버2) - JAVA[자바]
[Silver II] 마인크래프트 - 18111 문제 링크 성능 요약 메모리: 34724 KB, 시간: 564 ms 분류 브루트포스 알고리즘, 구현 제출 일자 2023년 12월 15일 10:10:15 문제 설명 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다. 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다. lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0,..
[백준] 1676번 : 팩토리얼 0의 개수 Silver5(실버5) - JAVA[자바]
[Silver V] 팩토리얼 0의 개수 - 1676 문제 링크 성능 요약 메모리: 11488 KB, 시간: 76 ms 분류 수학 제출 일자 2023년 12월 13일 15:56:31 문제 설명 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 풀이 방법(1) 1. 일단 n의 최대값은 500임으로 그냥 숫자로는 풀 수 없고 BigInteger로 풀 수 있음 2. BigInteger을 통해서 주어진 n값까지 팩토리얼을 구해준다. 3. 뒤에서부터 확인하여 0의 개수를 센 후 출력해주면 된다. package com.pratice; import java.io.*; i..
[백준] 9935번 : 문자열 폭발 Gold4(골드4) - JAVA[자바]
[Gold IV] 문자열 폭발 - 9935 문제 링크 성능 요약 메모리: 39504 KB, 시간: 372 ms 분류 자료 구조, 스택, 문자열 제출 일자 2023년 12월 13일 15:34:52 문제 설명 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는..
[백준] 2659번 : 십자카드 문제 Silver3(실버3) - JAVA[자바]
[Silver III] 십자카드 문제 - 2659 문제 링크 성능 요약 메모리: 11584 KB, 시간: 80 ms 분류 브루트포스 알고리즘, 구현, 정렬 제출 일자 2023년 12월 13일 15:02:37 문제 설명 위와 같은 십자모양의 한 장의 카드에서, 네 모서리에 1 이상 9 이하의 숫자가 하나씩 씌여 있다. 이 네 개의 숫자 중에는 같은 숫자도 있을 수 있다. 모든 가능한 십자 카드가 주어질 때, 각각의 카드는 다음과 같은 '시계수'라는 번호를 가진다. 시계수는 카드의 숫자들을 시계 방향으로 읽어서 만들어지는 네 자리 수들 중에서 가장 작은 수이다. 위 그림의 카드는 시계방향으로 3227, 2273, 2732, 7322로 읽을 수 있으므로, 이 카드의 시계수는 가장 작은 수인 2273이다. 입력..
[백준] 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. 각..
[백준] 2630번 : 색종이 만들기 Silver2(실버2) - JAVA[자바]
[Silver II] 색종이 만들기 - 2630 문제 링크 성능 요약 메모리: 13152 KB, 시간: 108 ms 분류 분할 정복, 재귀 제출 일자 2023년 12월 12일 10:44:08 문제 설명 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑..