이번 포스팅에서는 코딩테스트에 자주 출제되는 그래프, 트리를 탐색하는 방법인 DFS(Depth-First Search)와 BFS(Breadth-First Search)에 대해서 소개하려고 한다. DFS (Depth-First Search) DFS는 하나의 노드에서 갈 수 있는 노드가 여러개 있다고 했을 때, 하나의 노드에 대해서 완벽하게 탐색하고난 후 다음 노드에 대해서 탐색하는 방법을 말한다. 좀 더 교과서적으로 정리해보자면 다음 분기(Branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 DFS라고 한다. 하나의 길로 쭈우우욱 가보고 막히면 돌아와서 다음 길로 가는 형태를 말한다. 보통 모든 노드를 방문해야 할 경우 DFS를 선택한다. DFS 알고리즘을 프로그래밍할 때는 일반적으로 재귀함..
1. 무한루프를 통해 테스트 케이스를 실행하는 경우 특정 조건이 일치하는 것을 찾는 문제에서, 테스트 케이스의 수가 정해지는 것이 아니라 무한루프를 통해서 확인한다면 Boolean 배열에 저장해 활용함으로써 시간 단축이 가능하다. 2. 소수 빠르게 구하기 소수인지 확인은 2 ~ (i ** 0.5) + 1 의 범위만 확인해도 된다. 3. 파이썬에서의 전역변수 처리 함수 외부에 있는 전역변수(입력 값)을 함수에서 사용하려면 global 키워드를 사용하면 된다. 4. 빠른 입출력함수 input(), print() 대신 sys.stdin.readline(), sys.stdout.write() 함수를 사용하는 것이 빠르다. 5. 다양한 기본 라이브러리 사용 collections(deque, Counter, .....
동적 계획법(Dynamic Programming) 이란? 동적 계획법이란 어떠한 문제에 대한 최적해를 얻고자할때 해당 문제에 대해 부분적으로 분할하여 작은 문제를 먼저 해결한 뒤, 각 부분에 대해 최적의 해답을 차례로 구해가는 알고리즘이다. 솔직히 이런 이론적인 어려운 말보다 내가 이해한 것을 말하자면 "분할 정복을 통해서 문제를 해결하는데 동일한 문제는 한번만 풀자" 이다. 단순 분할 정복은 동일한 문제를 반복적으로 계산해 시간을 낭비한다는 단점이 있다. 동적 계획법은 이러한 비효율적인 부분을 해결할 수 있다는 장점이 있다. 따라서 동적 계획법을 통해 문제를 해결하게 된다면 단일항 시간복잡도를 통해 문제를 해결할 수 있다. 위 사진은 피보나치 수열의 값을 재귀함수를 통해 구할 때 거치게되는 노드 트리이..
백트래킹(Back Tracking) 백트래킹이란 해를 찾는 도중에 올바른 해가 아니면 전 상태로 되돌아가서 다시 해를 찾아가는 기법이다. 즉, DFS 와 같이 모든 경우의 수를 탐색하지만 중간에 올바르지 않은 해가 나올 경우 해당 가지를 가지치기해 하위 트리는 더 이상 확인하지 않는 것을 말한다. 이러한 가지치기는 불필요한 부분을 쳐내고 경우의 수를 최대한 줄여 최적화하가 가능합니다. 그렇기 때문에 가지치기를 얼마나 잘하느냐에 따라서 효율성이 결정된다. 즉, 시간이 단축된다는 말이다. 언제 사용하면 좋을까? 백트래킹은 결국 모든 상황을 확인하는 전수 검사를 기반으로 하고 있기 때문에, 모든 상황에 대해서 직접 Brute Force 해야하는 경우 고려해볼 수 있다. 특히, 시간제한이 있거나 N이 작아 직접..