본문 바로가기

재귀16

[백준 16505] 별 www.acmicpc.net/problem/16505 16505번: 별 출력 예제를 보고 별 찍는 규칙을 유추하여 별을 찍어 보자. www.acmicpc.net 재귀를 사용하는 문제이다. 규칙을 찾아보면 0에서 * 1에서 * * * 2에서 f(1) f(1) f(1) 임을 알 수 있다. 그냥 printf를 써버리면 저런 모양이 안나오고 배열을 사용해야 한다. 재귀함수를 호출할 때마다 별찍기를 시작할 (row, col)을 정해서 별을 찍도록 한다. row와 col은 제곱수만큼 늘어나므로 기저 조건 (0,0)에 2의 제곱수만큼 더한 시점이 n-1번째 별찍기를 시작하는 시점일 것이다. #include #include using namespace std; char board[1024][1024]; void Pri.. 2020. 12. 12.
[leetcode 110] Balanced Binary Tree Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of every node differ in height by no more than 1. Example 1: Input: root = [3,9,20,null,null,15,7] Output: true Example 2: Input: root = [1,2,2,3,3,null,null,4,4] Output: false Example 3: Input: root = [] Output: true Constrain.. 2020. 11. 21.
[leetcode 395] Longest Substring with At Least K Repeating Characters Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times. 문자열이 최소 k번 등장하는 가장 긴 부분 문자열 찾기 Example 1: Input: s = "aaabb", k = 3 Output: 3 The longest substring is "aaa", as 'a' is repeated 3 times. Example 2: Input: s = "ababbc", k = 2 Output: 5 The longest substring is "ababb", as 'a' is repeated .. 2020. 11. 14.
[leetcode 236] Lowest Common Ancestor of a Binary Tree Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: .. 2020. 10. 31.

티스토리툴바