hyunkookim 님의 블로그

탐욕 알고리즘 (Greedy Algorithm)탐욕 알고리즘은 문제를 해결할 때 현재 단계에서 가장 최적의 선택을 반복적으로 수행하여 전체 문제의 해를 구하는 알고리즘 설계 기법입니다. 이 알고리즘은 항상 **국소적 최적해(Local Optimal Solution)**를 선택하며, 이를 통해 최종적으로 **전역적 최적해(Global Optimal Solution)**를 구하려고 시도합니다.탐욕 알고리즘의 특징단계별 최적 선택:매 단계에서 그 순간 가장 최적인 선택을 합니다.이전 단계의 선택에 대해 다시 돌아가서 바꾸지 않습니다. (비가역적)문제의 구조적 특성 필요:탐욕 알고리즘이 최적해를 보장하려면 문제에 특정한 성질이 있어야 합니다:Greedy Choice Property (탐욕 선택 속성):현재 단계..

단조 스택(Monotonic Stack) **Monotonic Stack(단조 스택)**은 스택 자료구조를 활용하여 특정 조건을 만족하는 값을 효율적으로 찾는 알고리즘 기법입니다. 주로 배열이나 리스트에서 다음 큰 값(Next Greater Element), 다음 작은 값(Next Smaller Element) 등을 찾는 문제에서 사용됩니다.Monotonic의 의미"Monotonic"은 단조라는 뜻으로, 값이 항상 증가하거나 감소하는 특성을 가집니다.Monotonic Stack에서는 스택 안에 들어 있는 값들이 다음 두 가지 조건 중 하나를 만족하도록 유지합니다:단조 증가 스택 (Monotonic Increasing Stack):스택에 값이 쌓일수록 값이 커지거나 같음.즉, 스택의 위쪽에 있는 값이 아래..

https://youtu.be/ZNa9-86uVEA?si=gW5g_NFuih1V9T4I

https://youtu.be/0bqfTzpWySY?si=w9gBnCw8EkfZNwe7 DP 사용 이유 !!메모리를 사용해서 중복 연산을 줄이고메모리를 사용한다: 추가의 배열 혹은 자료구조를 만든다.중복 연산을 줄인다: 한번 연산한 결과는 배열에 담는다.중복 연산을 줄여서 수행 속도를 개선한다.따라서, DP를 `기억하기 알고리즘`, `기억하며 풀기` 라고도 함

문제790. Domino and Tromino Tiling You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 109 + 7.In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent ce..

참고 강의https://youtu.be/Ar40zcPoKEI?si=ANrQRht6S-ERkYOl https://youtu.be/atTzqxbt4DM?si=OTMYb-8eRMltSgTO  https://www.geeksforgeeks.org/find-paths-given-source-destination/ Print all paths from a given source to a destination - GeeksforGeeksA Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/..

문제198. House Robber You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.Given an integer array nums representing ..