알고리즘 - Baekjoon/Gold

[백준] 1174번 : 줄어드는 수 Gold5(골드5) - JAVA[자바]

[Gold V] 줄어드는 수 - 1174 문제 링크 성능 요약 메모리: 12972 KB, 시간: 88 ms 분류 백트래킹, 브루트포스 알고리즘 제출 일자 2024년 2월 3일 19:22:01 문제 설명 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다. 입력 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 N번째 작은 줄어드는 수를 출력한다. 접근 방법 1. N이 줄어드는 수라면..

[백준] 17825번 : 주사위 윷놀이 골드2(Gold2) - JAVA[자바]

[Gold II] 주사위 윷놀이 - 17825 문제 링크 성능 요약 메모리: 15280 KB, 시간: 164 ms 분류 백트래킹, 브루트포스 알고리즘, 구현, 시뮬레이션 제출 일자 2024년 2월 2일 10:31:18 문제 설명 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다. 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고..

[백준] 15684번 : 사다리 조작 Gold3(골드3) - JAVA[자바]

[Gold III] 사다리 조작 - 15684 문제 링크 성능 요약 메모리: 14204 KB, 시간: 312 ms 분류 백트래킹, 브루트포스 알고리즘, 구현 제출 일자 2024년 1월 31일 15:41:53 문제 설명 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선..

[백준] 13023번 : ABCDE Gold5(골드5) - JAVA[자바]

[Gold V] ABCDE - 13023 문제 링크 성능 요약 메모리: 19592 KB, 시간: 212 ms 분류 백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2024년 1월 29일 17:16:40 문제 설명 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000..

[백준] 2263번 : 트리의 순회 Gold1(골드1) - JAVA[자바]

[Gold I] 트리의 순회 - 2263 문제 링크 성능 요약 메모리: 62368 KB, 시간: 1280 ms 분류 분할 정복, 재귀, 트리 제출 일자 2024년 1월 23일 00:39:00 문제 설명 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력 첫째 줄에 프리오더를 출력한다. 접근 방법 1. PostOrder(LRV)는 루트 노드가 가장 오른쪽에 위치한다. -> 트리의 루트를 알 수 있다..

[백준] 4256번 : 트리 Gold2(골드2) - JAVA[자바]

[Gold II] 트리 - 4256 문제 링크 성능 요약 메모리: 37252 KB, 시간: 304 ms 분류 분할 정복, 재귀, 트리 제출 일자 2024년 1월 22일 22:45:38 문제 설명 이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다. 아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드..

[백준] 3425번 : 고스택 Gold4(골드4) - JAVA[자바]

[Gold IV] 고스택 - 3425 문제 링크 성능 요약 메모리: 39856 KB, 시간: 388 ms 분류 자료 구조, 구현, 스택 제출 일자 2024년 1월 20일 00:22:38 문제 설명 고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다. 편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 하고, 그 다음은 차례대로 두 번째 수, 세 번째 수라고 한다. NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109) POP: 스택 가장 위의 숫자를 제거한다. INV: 첫 번째 수의 부호를 바꾼다. (42 -> -42) DUP: 첫 번째 숫자를 하나 더 스택의 가장 위에 저장한다. SWP: 첫 번째 숫자와 두..

[백준] 2448번 : 별 찍기 - 11 Gold4(골드4) - JAVA[자바]

[Gold IV] 별 찍기 - 11 - 2448 문제 링크 성능 요약 메모리: 234796 KB, 시간: 476 ms 분류 재귀 제출 일자 2024년 1월 19일 00:23:23 문제 설명 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 접근 방법 1. 주어진 예시를 본다면 N이 3일 때 3층짜리 삼각형이고 맨 아랫줄은 6개의 공간이 생기는 것을 알 수 있다. 2. 출발점에서 시작하여 밑변의 길이를 2로 나누면 아래층의 시작점을 나눌 수 있다. 3. 밑변의 길이를 2로 나눈 것을 한번 더 나눠준다면(높이는 N이고 너..