더보기 ❗️이 글은 구종만 - 알고리즘 문제해결 전략 책을 참고하여 작성되었습니다. 📍 Algorithm vs Source Code Algorithm: 주어진 문제를 해결하는 명료한 방법, 다른 언어로 쓰인 program도 같은 원리로 동작한다면 같은 알고리즘을 사용한다고 할 수 있다. Source Code: 알고리즘을 구현하는 한 방법 => Source Code가 Algorithm을 정의하는 것은 아니다. 📍 Algorithm을 평가하는 기준 시간 : 알고리즘이 빠르게 동작하는지 공간 : 알고리즘이 적은 용량의 메모리를 사용하는지 ✔️ 시간 공간 메모리 사용량을 희생해 속도를 높이거나 속도를 희생해 메모리 사용량을 줄이거나 1. 알고리즘 속도 분석 두 알고리즘의 속도를 비교하기 위한 방법으로 두 프로그..
보호되어 있는 글입니다.
보호되어 있는 글입니다.
[Algorithm] - Dynamic Programming 알고리즘
dp 알고리즘 더보기 참고: https://hongjw1938.tistory.com/47 DP, 즉 Dynamic Programming(동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것 일반적인 재귀 방식 또한 DP와 매우 유사하다. 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산될 수 있다는 것이다. 피보나치 수를 재귀로 함수를 구성하면 return f(n) = f(n-1)+ f(n-2) ⇒ f(n-1)에서 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 되기 때문 한번 구한 작은 문제의 결과 값을 저장해두고 재사용한다면? ⇒ dp O(n^2)→O(f..
[Algorithm] - BFS(Breadth-First Search)
알고리즘 문제에서 자주 다뤄지는 BFS에 대해 알아보자. BFS란? BFS는 말 그대로 너비 우선 탐색으로 깊게 탐색하는 dfs와는 달리 인접한 노드부터 넓게 탐색하는 방법이다. 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 말한다. BFS 사용하는 경우: 두 노드 사이의 최단경로 or 임의의 경로를 찾고 싶을 때 ex) 어떤 지점 a에서 b까지 이동하는 거리를 그래프로 표현한 후 a와 b사이에 존재하는 경로를 찾는 경우 > DFS - 일단 한 경로를 선택하여 끝까지 가보고 막혔다면 다시 이전 분기점으로 돌아와 탐색 > BFS - 시작점과 가까운 곳부터 '차례대로' 살펴보며 탐색 BFS 특징 1️⃣ 재귀적으로 동작 x 2️⃣ 노드 방문 여부를 반드시 검사해야한다. : 방문한 노드를 재방문할..