재귀함수란? 자기 자신을 호출하는 함수로 팩토리얼 하노이 탑 등 동일한 작업을 반복해서 수행하는 문제엣 많이 사용됨. 재귀함수의 장점 직관적인 모습으로 간단히 구현가능 DFS, 백트래킹, 그리디 등 많은 알고리즘에서 사용되어 꼭 알아두어야 할 개념 재귀함수의 단점 종료 조건을 명시해주지 않으면 무한루프에 빠질 수 있음. 깊이가 너무 깊어지면 ( 너무 많은 반복호출 ) 많은 메모리를 차지한다. 불필요한 연산을 할 가능성이 있음. Python 에서의 재귀 파이썬에서 재귀의 깊이는 1000회라는 제한이 있다. def hello(): print('Hello, world!') hello() hello() 그래서 위 코드를 실행시키면 Hello world! 라는 문자열이 계속 출력되다 에러가 발생한다. 위에서 말한..
Greedy Algorithm(탐욕 알고리즘)이란? greedy의 사전적 의미는 욕심 많은, 탐욕적인 이라는 형용사다. 그럼 욕심 많은, 탐욕적인 알고리즘이 도대체 뭐야?? 간단하다 진짜 말 그대로 매 순간마다 욕심적으로 최적의 상황만을 고르는 알고리즘이다. 특징 탐욕 알고리즘은 크게 두 가지 특징이 있다. 1. 탐욕 알고리즘은 데이터 사이의 관계(단계별 관계)를 고려하지 않고 수행을 한다. => 이는 탐욕스러운 선택의 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다고 볼 수 있다. 2. 일단 선택한 것에 대해 절대로 번복하지 않는다. => 이미 선택된 데이터를 버리고 다른 것을 선택하지 않는다. (그래프 탐색은 아니라는 이야기) 이러한 특징들 때문에 대부분의 탐욕 알고리즘들은 매우 단순하며, 반면..
백트래킹? 트리방식으로 동작된다고 이해하면 쉽다. 재귀함수를 통해 for문을 돌려 깊이를 마음대로 설정할 수 있음. DFS랑 백트래킹 뭐가 달라? 재귀함수를 통한 dfs랑 백트래킹이 유사하지 않나?라는 생각이 들었다. 둘 다 탐색이지만 원하는 값을 찾기 위한 방법에서 차이가 발생한다. 백트래킹은 불필요한 탐색을 하지 않는다. 경로를 찾아가는 도중에 해가 되지 않을 것 같은 경로에 왔다면 더 가지 않고 되돌아온다. 아래 사진을 보면 느낌이 팍 올 것이다. 되돌아올 때 밑에 노드는 애초 방문하지 않은 것처럼. dfs의 방문처리는 보통 배열을 사용하여 인덱스를 활용한 방문처리를 한다. 하지만 백트래킹은 다시 부모노드로 올라갈 때 이전의 노드들을 방문했다고 생각하지도 않고 진행한다. 그래서 보통 append()..
평소에는 DFS, BFS 둘 중 뭘 써도 풀리는 문제들만 풀었어서 차이점(효율적인 측면)을 명확하게 잘 몰랐다. 그렇게 오늘도 알고리즘 문제를 풀다 갑자기 이 DFS BFS 적용 기준 정리에 필요성을 느껴 바로 실행에 옮기려 한다. BFS, DFS가 뭐야? 내가 알고있는 bfs, dfs는 그래프를 탐색하는 방법으로 알 고 있다. 각 dfs bfs에 대해 간단히 적어보겠다. BFS(너비 우선 탐색) 큐를 사용함 정점에서 가까운 노드들부터 탐색 찾는 노드가 인접할 때 유리 노드가 많을 수록 메모리를 많이 소비 DFS(깊이 우선 탐색) 스택 혹은 재위함수를 사용함 정점에서 가장 깊은 노드까지 들어가며 탐색 그래프의 깊이(depth)가 깊을 수록 빠름 메모리가 적음 언제 뭐 써야해? 공통 단순히 모든 정점을 방..
