DFS(Depth First Search) 알고리즘 DFS(깊이 우선 탐색) 역시 앞서 포스팅했던 BFS 알고리즘과 마찬가지로 길찾기 알고리즘을 구현할 때 유용한 그래프 탐색 알고리즘입니다. Brute Force(완전탐색) 형태로 모든 경우의 수를 다 시도하여 답을 찾는 방법으로, 이름과 같이 깊이(Depth)를 끊임없이 추적하며 전체 정점을 탐색합니다. 앞서 인접행렬과 BFS탐색 알고리즘에서 보였던 아래와 같은 그래프와 인접행렬을 예로 들어보겠습니다. 1부터 탐색을 시작한다고 가정할 때, BFS가 2와 3을 큐에 담는 것과 달리, DFS는 오직 가장 근접한 값인 2만 스택에 담습니다. 그리고 두번째 뎁스인 2에서 다음 탐색을 이어갈 정점을 찾습니다. 1,4,5가 2와 연결되어있지만, 1은 이미 탐색을 ..
이번 포스팅에서는 탐색 알고리즘에서 가장 중요하게 활용되는 BFS 알고리즘과 인접 행렬에 대해 다루도록 하겠습니다. 인접행렬 인접행렬에 대한 설명은 다른 사이트에서 워낙 많이 다뤄 온 주제이기 때문에 본 포스팅에서 구체적으로 설명하지 않겠습니다. 그럼에도 불구하고 본 포스팅에서 인접행렬을 다루는 가장 큰 이유는 BFS 알고리즘과 관련이 많기 때문입니다. 보통 경로 탐색 알고리즘을 사용하는 경우, 예를 들어 A->Z로 가는 방향에 대해 최적의 경로를 찾고자 하는 경우, 다양한 방식으로 경로를 계산하고 이를 표현할 수 있습니다. 어떠한 알고리즘을 사용하느냐에 따라 경로가 달라지는데, 이러한 경로에 대한 정보를 행렬로 표현할 수 있습니다. 흔히 사용되는 행렬이 인접행렬입니다. 인접 행렬에는 다음과 같이 몇 가..
문자열 파싱 알고리즘 String 처리와 관련된 알고리즘 문제를 해결하는 과정에서 종종 Sub String을 파싱해서 처리해야 하는 상황에 직면하곤 합니다. 사실 파싱하는 방법은 머릿속으로 방법을 그리는 것은 쉽다고 생각할 수 있지만 직접 만들어보지 않으면 생각보다 어려울 수도 있습니다. 그래서 이번 포스팅에서는 알고리즘 문제를 해결하기 위해 반드시 필요한 문자열 파싱 알고리즘에 대해 다루고자 합니다. 문자열을 파싱하는 방법은 정말 다양합니다. 언어에 따라서는 기본적으로 파싱 기능을 제공하기도 합니다. Java가 대표적으로 파싱을 위한 tokenizer기능을 제공하고 있습니다. C++의 경우에는 공식적으로 STL을 통한 파싱 알고리즘은 아직 제공하지 않고 있습니다. (다만 시간 포맷으로 구성된 strin..
blog post 순열과 조합 개발 과정에서 어떤 집합의 경우의 수를 찾아야 하는 경우가 종종 있습니다. 이때 경우에 따라 조합 혹은 순열을 활용해야 하는데, 둘의 차이는 다음과 같습니다. - 조합(Combination): 순서 바뀜 허용 안함. 중복 허용 안함. 표현: nCr = n! / r! * (n - r)! . - 순열(Permutation): 순서 바뀜 허용. 중복 허용 안함. 표현: nPr = nCr x r! . 예를 들어 {1,2,3} 세개의 요소를 가지고 있는 벡터 v={1,2,3} 를 활용하여 각각 순열과 조합을 구성하고자 하는 경우 아래와 같은 경우의 수를 도출할 수 있습니다. 순열: - 3개의 원소로 조합 가능한 모든 구성: 3P3 (nPn = n!). 가능한 구성: {1,2,3}, ..
클라우드와 개발, 네트워크, 리눅스 시스템 등을 연구하고 정리하기 위한 개인 공간입니다.
