넘치게 채우기

https://leetcode.com/problems/n-th-tribonacci-number/description/?envType=study-plan-v2&id=dynamic-programming N-th Tribonacci Number - LeetCode Can you solve this real interview question? N-th Tribonacci Number - The Tribonacci sequence Tn is defined as follows: T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. Given n, return the value of Tn. Example 1: Input: n = 4 Output: 4 E l..

https://leetcode.com/problems/fibonacci-number/description/?envType=study-plan-v2&id=dynamic-programming Fibonacci Number - LeetCode Can you solve this real interview question? Fibonacci Number - The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F(0) = 0 leetcode..

https://leetcode.com/problems/reverse-integer/description/ Reverse Integer - LeetCode Can you solve this real interview question? Reverse Integer - Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0. Assume the envir leetcode.com 문제 유형 : 수학 난이도 : Medium 문제 Given a signed ..

https://leetcode.com/problems/gas-station/description/ Gas Station - LeetCode Can you solve this real interview question? Gas Station - There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith st leetcode.com 문제 유형 : 그리디 / 브루트 포스 난이도 : Medium 문제 There are n g..

"당장 최선의 수를 고려하기" 탐욕 알고리즘은 매 선택마다 당장의 최선의 선택을 하여 답에 도달하는 방법이다. 항상 최선의 결과를 보여주지는 않지만 특정 상황들 속에서는 굉장히 효과적이고, 직관적이다. 대표적인 예시로는, 거스름돈이 있다. #include #include using namespace std; int input; int wons[4] = {500, 100, 50, 10}; vector calc_coin(int money) { vector coins = vector(4); coins[0] = money / 500; coins[1] = (money % 500) / 100; coins[2] = (money % 100) / 50; coins[3] = (money % 50) / 10; return ..

"이미 알고있는 답은 또 구하지 않는다" 사실 전혀 다이나믹하지 않고, 프로그래밍이라고 하기에도 애매하다. 벨만이라는 수학자가 펀딩을 잘 받기 위해서, 눈에 띄는 이름을 지은 것이다. 이광근 교수님의 저서 "컴퓨터과학이 여는 세계"에서는 '기억하며 풀기'라는 이름이 쓰였다. 하나의 큰 문제를 작은 문제로 나누어서, 그 결과를 얻고, 큰 문제의 답을 구하는 방식이다. "분할 정복법"과도 유사하다. 다이나믹 프로그래밍에는 두 가지 방법이 있다: 종류 메모이제이션 타뷸레이션 과정 하향식(Top down) 상향식(Bottom up) 구현 재귀 함수 반복문 장점 직관적이다 시간을 더 아낄 수도 있다 단점 재귀함수의 호출이 잦아 느려질 수 있다. DP테이블을 잘 채워야 한다. 기타 Lazy - Evaluation ..

https://leetcode.com/problems/add-digits/description/ Add Digits - LeetCode Can you solve this real interview question? Add Digits - Given an integer num, repeatedly add all its digits until the result has only one digit, and return it. Example 1: Input: num = 38 Output: 2 Explanation: The process is 38 --> 3 + 8 --> 11 11 --> leetcode.com 난이도 : Easy 문제 Given an integer num, repeatedly add all i..

https://leetcode.com/problems/roman-to-integer/ Roman to Integer - LeetCode Can you solve this real interview question? Roman to Integer - Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just tw leetcode.com 난이도 : Easy 문제 Roman numerals are represented by seven d..

https://www.acmicpc.net/problem/2638 2638번: 치즈첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로www.acmicpc.net문제 유형 : BFS solved.ac 난이도 : GOLD III 문제(자세한 내용은 위 링크(문제 본문) 참조) N * M의 모눈종이 위에 아주 얇은 치즈가 표시되어있다. N은 세로 격자의 수이고, M은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자의 4변 중에서 최소 ..

정렬은 데이터들을 주어진 조건에 맞게 순차적으로 나열하는 것이다. 1. 버블 정렬(Bubble Sort) 한 번 순회할 때마다 마지막 하나가 정렬 된다. 거품이 올라오는 것 처럼 보여서 버블 정렬이라고 한다. 두 수를 비교하여, 조건에 맞으면 자리를 바꾼다. O(N^2)의 시간복잡도를 가진다. def bubble_sort(arr): for i in range(len(arr)): for j in range(len(arr)): if arr[i] < arr[j]: arr[i], arr[j] = arr[j], arr[i] 2. 선택 정렬(Selection Sort) 테이블에서 가장 작은 노드를 찾아서 맨 앞으로 위치를 바꾼다. 맨 앞에 놓인 노드 뒤부터 다시 똑같은 과정을 반복한다.(가장 작은 노드를 0번째 인..