BOJ

[백준] 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..

[백준] 14716번 : 현수막 Silver1(실버1) - JAVA[자바]

[Silver I] 현수막 - 14716 문제 링크 성능 요약 메모리: 24692 KB, 시간: 196 ms 분류 너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2024년 1월 29일 12:17:02 문제 설명 ANT가 처음 알고리즘 대회를 개최하게 되면서 현수막을 내걸었다. 저번 학기 영상처리 수업을 듣고 배웠던 지식을 최대한 응용 해보고 싶은 혁진이는 이 현수막에서 글자가 몇 개인지 알아보는 프로그램을 만들려 한다. 혁진이는 우선 현수막에서 글자인 부분은 1, 글자가 아닌 부분은 0으로 바꾸는 필터를 적용하여 값을 만드는데 성공했다. 그런데 혁진이는 이 값을 바탕으로 글자인 부분 1이 상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자라고 생각만 하..

[백준] 1309번 : 동물원 Silver1(실버1) - JAVA[자바]

[Silver I] 동물원 - 1309 문제 링크 성능 요약 메모리: 15048 KB, 시간: 88 ms 분류 다이나믹 프로그래밍 제출 일자 2024년 1월 28일 16:10:15 문제 설명 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. 입력 첫째 줄에 우리의 크기 N(1≤N≤100,000)..

[백준] 1326번 : 폴짝폴짝 Silver2(실버2) - JAVA[자바]

[Silver II] 폴짝폴짝 - 1326 문제 링크 성능 요약 메모리: 13804 KB, 시간: 128 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2024년 1월 24일 20:54:46 문제 설명 개구리가 일렬로 놓여 있는 징검다리 사이를 폴짝폴짝 뛰어다니고 있다. 징검다리에는 숫자가 각각 쓰여 있는데, 이 개구리는 매우 특이한 개구리여서 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다. 이 개구리는 a번째 징검다리에서 b번째 징검다리까지 가려고 한다. 이 개구리가 a번째 징검다리에서 시작하여 최소 몇 번 점프를 하여 b번째 징검다리까지 갈 수 있는지를 알아보는 프로그램을 작성하시오. 입력 첫째 줄에 징검다리의 개수 N(..

[백준] 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: 첫 번째 숫자와 두..