재귀

[백준] 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은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드..

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

[백준] 1991번 : 트리 순회 Silver1(실버1) - JAVA[자바]

[Silver I] 트리 순회 - 1991 문제 링크 성능 요약 메모리: 11584 KB, 시간: 76 ms 분류 재귀, 트리 제출 일자 2024년 1월 14일 02:07:09 문제 설명 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다. 입력 첫째 줄에는 이진..

[백준] 1987번 : 알파벳 Gold4(골드4) - JAVA[자바]

[Gold IV] 알파벳 - 1987 문제 링크 성능 요약 메모리: 296464 KB, 시간: 1988 ms 분류 백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 제출 일자 2024년 1월 14일 01:08:01 문제 설명 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 ..

[백준] 17829번 : 222-풀링 Silver2(실버2) - JAVA[자바]

[Silver II] 222-풀링 - 17829 문제 링크 성능 요약 메모리: 114204 KB, 시간: 552 ms 분류 분할 정복, 구현, 재귀 제출 일자 2024년 1월 12일 14:49:42 문제 설명 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다. 다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다 종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지 궁금해한다. 랩실 활동에 치여 삶이 사라진 종욱이..