sm 기술 블로그

그리디 알고리즘(Greedy Algorithm) 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법 예시) 다음 중 가장 큰수를 고르라고 한다면 그리디 알고리즘은 12 -> 6 을 선택한다. 결과를 봤을 때 최적의 수는 아니지만 모든 노드를 거치지 않아 계산속도가 빠르다는 점을 지녔다. 문제 해결 방법 선택절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택절차로 돌아가 위의 과정을 반복 사용하는 문제 활동 선택 문제 거스름돈 문제 최소 ..

동적프로그래밍(Dynamic Programming) 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것 다음과 같이 중복으로 계산하는 것을 줄여줌으로써 조금 더 문제를 빠르게 해결함. 동적프로그래밍 조건 작은 문제가 반복이 일어나는 경우 같은 문제가 반복으로 구해지는 경우 동적프로그래밍 방법 모든 작은 문제들은 한 번만 풀고 어딘가에 메모해 놓는다. 다시 큰 문제를 풀어나갈때 똑같은 작은 문제를 직면하는 경우 메모한 작은 문제의 결과값을 이용한다. (Memoization 메모이제이션) 구현 (파이썬) 1. Botton-Up (아래서 위로) -> 작은 문제부터 구해나감 def fibonacci(n): if n 큰 문제부터 작은 문제로 (재귀함수로 구..

백트래킹 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정 모든 경우의 수를 전부 고려하는 알고리즘이다. 트리 탐색 알고리즘이라고 봐도 무방하며 방식에 따라 깊이우선탐색 (Depth First Search - DFS) 와 최선 우선 탐색 (Best First Search - BFS) 가 있다. 모든 경우의 수를 고려해야 한다면 DFS가 좋으며 BFS로도 구현이 가능하나 큐의 크기, 속도가 똑같아 DFS가 좋다. 장점 무한히 깊은 곳을 찾아야할때 효과적이다. 단점 모든곳을 방문하기 때문에 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할 수 있다. https://smhope.tistory.com/308 너비 우선 탐색(BFS) 너비 우선 탐색(BFS) 루트 노드에서 시작해서 인접한..

너비 우선 탐색(BFS) => 큐 사용 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법. 가장 가까운 정점을 먼저 방문하고 이후 멀리 떨어져 있는 정점을 방문하는 방식이다. 특징 직관적이지 않다. 큐를 사용한다. (선입 선출이 원칙이다) Prim, Dijkstra 알고리즘과 유사하다. 과정 결국 이동 순서는 0 -> 1 0 -> 2 0 -> 4 1 -> 2 2 -> 3 3 -> 4 이 된다. 시간 복잡도 인접 리스트로 표현된 그래프: O(N+E) 인접 행렬로 표현된 그래프: O(N^2)