반응형 theory 📓/자료구조 알고리즘4 [자료구조/알고리즘] python 다이나믹프로그래밍 개념 및 예제 들어가기 전에...최근 진행한 코딩테스트에서, 문제를 풀다 테스트 케이스 몇개에서 실패를 경험하였다.복기를 해보니, 문제의 느낌만 보고 그리디 알고리즘을 통해 구현을 진행한것이 원인이였다.해당 그리디 알고리즘을 통해 순간에서 최선의 선택을 통해 구현을 하다보니,최적의 해를 놓치는 케이스가 발생하였고,이를 해결하기 위한 적합한 방식은 모든 경우의 수에서 최적의 해를 구하는 것이였다.이를 효과적으로 하기 위한 알고리즘은 다이나믹 프로그래밍이였으며, 이번 기회에 정리하고자 한다.다이나믹 프로그래밍복잡한 문제를 작은 문제로 나누어 해결하는 방법이미 계산한 작은 문제의 답을 기억해 두었다가 재사용이렇게 하면, 같은 계산을 반복하지 않아도 되기 떄문에 효율적메모리 공간을 조금 더 사용하지만, 수행 시간을 획기적으로.. 2024. 9. 30. [자료구조/알고리즘] python 스택, 큐, 우선순위 큐 개념 및 예제 스택 (stack)선입 후출 형식으로, 나중에 들어오는 데이터를 제일 먼저 반환하는 방식파이썬에서는 리스트에 append 후 pop 함수를 통해 구현 가능append 를 통해 리스트에 순서대로 데이터를 적재pop 함수를 통해 가장 마지막에 들어온 데이터를 추출예제)# stackdef sol(s): check = [] for i in s: if i == '(': check.append(i) else: try: check.pop() except: return False else: if len(check) != 0: retur.. 2024. 9. 27. [알고리즘] 탐욕 알고리즘 (Greedy Algorithm) 탐욕 알고리즘이란? Greedy 단어의 뜻처럼 * 탐욕스러운, 욕심 많은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해당에 도달 하는 방법이다. 탐욕 알고리즘은 최적의 해를 구하는 데 있어 근사적인 방법이다. 여러 경우 중 하나를 결정해야 할 때마다, 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행한다. 순간마다 선택 함으로써, 그 순간에 대해 지역적으로는 최적이지만, 그 선택들이 계속 진행되어 최종적(전역적)인 해답을 도출하였다 하더라도, 그것이 최적이라는 보장은없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 탐욕 알고리즘 해결 방법 선택 절차(Selection Procedure): 현재 상태에서의 최적의.. 2023. 8. 21. [자료구조/알고리즘] 자료구조에 대해 개요 자료구조의 학습의 목적 - 데이터를 체계적으로 저장하고, 효율적으로 활용하기 위해 경험에 따르면 특정한 패턴이 있는 상황들이 빈번하게 발생하게 된다. 이러한 특정 패턴의 문제를 해결하는데 있어, 보다 빠르고 정확하게 해결하기 위해 학습을 한다. 또한 우리에게 주어진 자원(메모리, cpu) 등은 한정적이다. 이러한 제약적인 상황에서 메모리 공간을 효율적으로 사용하고, 실행 시간의 효율성을 고려하여 최대한의 아웃풋을 끌어내기 위해 필요하다. 모든 패턴에서 맞는 자료구조는 없다 따라서 각 자료구조가 갖는 장점과 한계를 알고 학습하는 것이 중요하다. 자료구조란? 간단하게 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의 즉 데이터 값의 모임 이다. 좀 더 상세 하게 들어가보면 먼저 데이터를 정의해보자.. 2023. 8. 21. 이전 1 다음 반응형
