codeollie

그리디 ● 그리디 알고리즘은 탐욕법이라고도 하며 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. ● 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. ● 그리디 해법은 그 정당성 분석이 중요하다. ● 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 한다. 위와 같은 모양의 트리가 있다고 가정하고 루트 노드부터 시작하여 거쳐가는 노드 값의 합이 최대인 경우를 구하려고 했을때 최적의 해는 5 -> 7 -> 9 이지만 그리디 알고리즘을 사용해서 당장 가장 큰 수를 선택했을 때 최적의 해보다 더 작은 값이 나올 수도 있다. ● 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. ● 하지만..

백트래킹 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 백트래킹은 상당한 구현력을 필요로하고 재귀로 구현한다면 재귀의 특성상 실수한 부분을 찾기가 어렵다. 백트래킹의 원리 어떤 노드의 유망성을 점검한 후 유망하지 않으면 배제시킨다. 해당 노드의 부모 노드로 되돌아간 후 다른 자식 노드를 점검한다. 탐색을 해보고 정답을 찾기 위한 후보해가 될 수 없으면 다음 단계로 진행하지 않고 되돌아 간다는 의미이다. DFS와의 차이점은 DFS는 모든 노드를 방문하는 것을 목표로 하지만 백트래킹은 불필요한 탐색을 하지 않기 위해 유망하지 않은 경우 탐색을 하지 않고 시간을 단축시킨다. AIR라는 단어를 완성시키기 위해서 백트래킹을 진행한다고 했을때 왼쪽 노드 N을 방문하였을때 그 노드의 자식 ..

DFS(Depth First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조 혹은 재귀 함수를 이용하며, 동작과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더이상 2번의 과정을 수행할 수 없을때까지 반복한다. 위와 같은 그래프에서 시작노드 1부터 깊이 우선 탐색을 진행한다면 과정은 다음과 같다. def DFS(graph, x, visited): stk = [] stk.append(x) visited[x] = True while ..