Algorithm & SQL/Algorithm (3) 썸네일형 리스트형 [Algorithm] Dynamic Programming - 동적 계획법 Dynamic Programming - 동적 계획법 DP, 동적계획법이란? 큰 문제를 작은 문제로 나누어 접근하는 방식의 문제를 일컫는 용어입니다. 어떠한 문제를 나누어 접근한다는 시각에서는 분할정복(Divide and Conquer) 와 컨셉이 비슷합니다. 하지만 나누어 접근하는 작은 문제가 중복해서 일어나는가에 대한 여부에 차이가 존재합니다. 분할정복은 작은 문제에서 반복이 일어나지 않습니다. 반면 DP는 작은 부분의 문제들이 반복되는 컨셉을 이용해 문제를 풀어나가는 방법입니다. Memoization 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 다시 사용하는 방법으로 동적계획법에 핵심이 되는 기술입니다. Memoization은 동적 프로그래밍 방식이 작은 문.. [Algorithm] DFS&BFS - 깊이 우선 탐색, 너비 우선 탐색 (그래프 탐색) DFS & BFS - 그래프 탐색 인접 리스트와 인접 행렬의 차이 인접 행렬 방식은 노드 간 모든 관계를 저장하므로 노드가 많을수록 많은 메모리가 불필요하게 낭비됩니다. 반면, 인접 리스트 방식은 연결된 정보만 저장하기 때문에 메모리를 보다 효율적으로 사용하게 됩니다. 하지만 인접 리스트 방식에 비해 특정 두 노드가 연결되어 있는지 바로바로 확인이 불가하기 때문에 정보를 얻는 속도가 느려집니다. DFS DFS의 동작 방식에 대해 알아보겠습니다. DFS는 깊이 우선 탐색 이라는 이름대로 특정 경로를 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 노드를 방문한 이후, 다시 돌아가서 다른 경로를 탐색하는 알고리즘입니다. DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 아래와 같습니다. 탐색 시작 노드.. [Algorithm] Greedy - 탐욕법 Greedy - 탐욕법 그리디 알고리즘은 매우 단순하면서 강력한 방법이다. 알고리즘의 흐름을 보면 왜 "greedy" 라는 이름이 붙었는지 알 수 있다. 그리디 알고리즘은 현재 상황에서 가장 좋은 최적의 해만 고르는 방법이다. 즉, 매 순간 제일 최적의 해로 보이는 해를 선택하며 현재의 선택이 나중에 어떠한 영향을 미칠지는 고려하지 않는다. 따라서 특정 문제를 만났을 때 단순히 현재 상황에서 가장 좋아보이는 최적의 해만 선택해도 문제를 정상적으로 풀어낼 수 있는지 파악해야 한다. -> 그리디의 핵심! 예제 풀이 1. 백준 - 설탕 배달 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다.. 이전 1 다음