전체 글

✅ 개요동적계획법(Dynamic programming)은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법✅핵심이론큰 문제를 작은 문제로 나눌 수 있어야 함작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야함모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용 이를 메모이제이션(memoization)기법이라고 함동적계획법은 톱-다운 방식 과 바텀-업 방식으로 구현가능📌대표 문제 : 피보나치수열피보나치수열 공식 : D[N] = D[N-1] + D[N-2]1. 동적계획법으로 풀 수 있는지 확인6번째 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 4번째 피보..

🤔그리디 알고리즘이란현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘✅수행 과정 3단계해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해 선택적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결하지 못한다면 1단계로 돌가 같은 과정 반복✅전제 조건탐욕 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 미치지 않아야 함최적 부분 구조(Optimal Substructure) : 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성되어야 함✅유형 및 주의사항동전 교환 문제 : 거스름 돈을 ..

1. 시간/공간 복잡도 알아야 하는 이유주어진 조건에 따라 접근법 유추 가능2. 빅오표기법: 알고리즘의 효율성 표기해주는 표기법3. 특징상수항 무시         |   O(N+5) → O(N)계수 무시             |   O(3N)  → O(N)최고차항만 표기  |   O(3N^3 + 2N^2 + N + 5 ) →  O(N^3)시간복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수공간복잡도 : 알고리즘이 실행될 때 사용하는 메모리의 양4. 빠른 순서👍O(1) 빅오 표기법명칭설명O(1)상수시간 (Constant time)문제를 해결하는데 오직 한 단계 처리O(log n)로그시간 (Log time)문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦O(N)선형시간 문제를 해결하..

그래프 알고리즘그래프를 표현하고 이해하는 알고리즘→ 그래프 : 정점(Vertex) 과 간선(Edge)으로 구성된 자료구조 그래프 구조 예시graph = { 0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1], 5: [2]}[분류]탐색 알고리즘 : 각각의 정점들이 연결된 상태 (DFS, BFS)DFS( Depth First Search ) BFS( Breadth First Search ) 그래프의 형태 : 인접 행렬 or 이차원 배열 형태최단 경로 알고리즘 : 두 정점의 최단 경로 (다익스트라 알고리즘 , 벨만 포드 알고리즘, 플로이드 와샬 알고리즘)최소 신장 트리 : 모든 정점을 연결하는 최단 경로. 모든 경로를 지나는 최소값 ( 쿠..

📌스택 ( Stack )선입후출( FILO ; First In Last Out ) 방식 = 먼저 들어온 데이터가 나중에 나가는 방식Stack 이 '쌓다' 라는 의미라는 것을 상기하면 이해하기 편함🤚🏻파이썬으로 구현하기 파이썬에서는 별도의 라이브러리 없이 List 자료형을 사용하여 스택 구현 가능# Stack stack = [] # list()# 데이터 삽입stack.append(1) # [1]stack.append(2) # [1,2]stack.append(3) # [1,2,3]# 데이터 추출stack.pop() # [1,2]stack.pop() # [1] 📌큐 ( Queue )선입선출( FIFO ; First In First Out ) 방식 = 먼저 들어온 데이터가 먼저 나가는..