nathan_H

최근 알고리즘 문제를 풀면서 벽에 부딪히는 느낌이 많이 들었는데, 그 중 Dynamic Programming이라는 유형의 문제는 쉽게 감이 잘 잡히지 않는 유형 중 하나였다. 그럼에도 불구하고 Dynamic Programming은 중요한 알고리즘 디자인 패러다임이기에 한 번 제대로 이해하고 문제도 풀어볼 가치가 있다. Dynamic Programming 사실 Dynamic Programming 이름만 가지고는 다른 "이분 탐색", "분할 정복", "너비 우선 탐색"과 같이 무엇을 의미하는 잘 다가오지 않는데, Dynamic Programming이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔으며 전산학 전반에서 일반적으로 사용하는 Dynamic, 혹은 Programming이란 단어와는 아무런 관련이 ..

시작하기 알고리즘을 풀다보면 그래프 자료구조를 사용하는 경우가 많고, 그래프 자료구조를 사용하는 문제의 상당수는 DFS, BFS을 구현해 문제를 해결하는 경우가 많다. 그리고 문제의 난이도가 올라갈수록 단순한 DFS, BFS가 아닌 다양한 형태로 변형한 DFS, BFS을 요구한다. 그래서 DFS, BFS 개념과 몇가지 유형을 통해 한번 DFS, BFS을 뿌시고자 한다. Graph 자료형 그래프 자료형의 경우 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多의 관계 를 가지는 원소들을 표현하기 위한 자료구조로 객체의 정점과 객체를 연결하는 간선의 집합이다. 그래프 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합 𝐺 = (𝑉,𝐸) − 𝑉는 그래프에 있는 정점들의 집합 − 𝐸..

큐는 스택 자료구조와 달리 FIFO (First-In First-Out)- 선입 선출 특징으로 넣을 때에는 한 쪽 끝에서 밀어 넣어야 한다. -> enqueue 연산 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야하는 제약 -> dequeue 연산 즉 enqueue로 삽입된 원소가 가장 나중에 dequeue로 빠져나온다는 것이다. 추상적 자료구조 구현 method size() - 현재 큐에 들어 있는 데이터 원소의 수 O(1) isEmpty() - 현재 큐가 비어 있는지 판단 O(1) enqueue(x) - 데이터 원소 큐에 추가 O(1) dequeue - 큐에 맨 앞에 저장된 데이터 원소 제기 or 반환 O(n) peek() - 큐의 맨앞에 저장된 데이터 원소 반환(제거 x) O(1) dequeue 시간 복잡도 ..