모든 글 보기
Dynamic Programming
🕵🏻♂️ 동적계획법이란? 복잡하고 큰 문제를 간단한 작은 문제들로 🦿나누어서 푸는 방법으로 작은 문제들의 답을 🧠기억해서 재활용한다. 동적계획법을 사용하려면 2가지 조건을 만족해야 한다. 최적 부분 구조 전체 문제를 부분 문제로 나눌 수 있고, 부분 문제의 최적해로 전체 문제의 최적해를 낼 수 있다. 중복되는 부분 문제 동일한 부분 문제가 반복적으로 계속 사용된다. 🕵🏻♂️ 사용하려면? 전체 문제와 부분 문제 사이의 규칙을 찾는다. 배열에 부분 문제들의 답을 저장하고 재활용하며 전체 문제를 해결한다. 동적계획법은 크게 2가지 형태로 구현할 수 있다. Bottom Up (Tabulation) 반복문 이용해서 dp[0]부터 위로 올라가며 배열을 채우는 방식 Top Down (Memoization) 재귀함..
[분할정복] 백준 1992번 (C++)
1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제가 뭐야 백준 1992번은 2차원 배열을 한 줄의 문자열로 표현하는 문제이다 어떻게 해결해 분할정복을 이용해서 큰 2차원 배열을 작은 2차원 배열들로 쪼갠 후 작은 배열들부터 문자열로 표현했다. 쪼갠 작은 배열들이 전부 값이 같은 경우와 다른 경우를 나누어서 처리해주어야 한다. 분할정복 (Divide & Conquer) Divide : 전체 문제를 더 이상 쪼갤 수 없는 작은 문제들로 쪼갠다 Conquer : 작은 문제들을 각각 해결한 후 조합해..
Breadth First Search
그래프의 정점들을 탐색하는 알고리즘에는 대표적으로 DFS와 BFS가 있다. 🕵️설명해본다 BFS는 넓이 우선 탐색으로 👭🏿가까운 정점부터 먼저 다 탐색하러 간다. 시작 정점의 인접한 정점을 다 탐색한 후, 다시 방문한 정점들의 인접한 정점들을 탐색하러 가는 방식이다. DFS보다 짧은 시간안에 최단거리 찾는 것을 보장한다. 🕵️구현해본다 넓게 넓게 탐색해야 하므로 큐, 반복문으로 구현한다. 시작 정점 혹은 어떤 정점에서 갈 수 있는 자식 정점 경우를 생각한다. 반복문을 돌며 큐에서 정점을 빼고, 그 정점의 자식들을 다시 넣고 빼고를 반복한다. 큐에 자식들을 넣을 때 범위, 목표 도착 등을 체크한다. (체크했을 때 갈 수 없는 자식 정점은 큐에 넣지 않는다) 큐에 넣을 정점 형태는 '정점 식별(Value) ..
DFS
DFS (Depth First Search) 그래프의 정점들을 탐색하는 알고리즘에는 대표적으로 DFS와 BFS가 있다. DFS는 깊이 우선 탐색으로 정점의 자식을 먼저 탐색하러 간다. 깊게 깊게 들어갔다가 더 이상 갈 곳이 없으면 다시 돌아와서 다른 방향으로 또 깊게 깊게 탐색하러 간다. 깊게 깊게 들어갔다 나오는 것이기에 재귀함수 또는 스택으로 구현한다. 재귀함수로 구현할 때 나만의 ✨체크 포인트✨ 어떤 정점에서 갈 수 있는 자식 정점 경우를 생각해서 함수 안에 자기 함수들을 (재귀함수) 구현한다. 재귀함수를 들어왔을 때 or 재귀함수 들어가기 전에 범위, 목표 도착 여부 등 조건을 체크한다. 현재위치, 목표 도착 여부, 들어간 깊이 등 재귀함수의 매개변수, 반환 값를 확인한다. # 프로그래머스 - 타..