조앤의 기술블로그

순열 (Permutaion) Permutaion의 앞글자를 따서 P로 나타냄. nPr의 의미는 n개의 숫자에서 r개를 뽑아 정렬하는 가짓수이다. 예를 들어 {1, 2, 3}이란 수열이 있고, 여기서 두개를 뽑아 정렬하고자 할 때, n = 3, r = 2라고 하면, 가짓수는 3P2가 된다. 가짓수를 출력해보면 {1, 2}, {2, 1} {1, 3}, {3, 1} {2, 3}, {3, 2} 순서도 고려하므로 {1, 2}와 {2, 1}은 다르게 취급한다. 조합 (Combination) Combination의 앞글자를 따서 C로 나타낸다. nCr의 의미는 n개의 숫자에서 r개를 뽑는 경우의 수이다. 순서가 달라도 내용물이 같으면 같은 수열이다. 예를 들어 {1, 2, 3}이란 수열이 있고, 여기서 2개를 뽑는..

BFS(Breadth First Search, 너비 우선 탐색) 또한 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘입니다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점들을 발견하면, 그 간선을 통해 방문하지 않은 정점들을 자료구조 큐에 넣습니다. 그리고 큐의 front 정점을 방문하고 pop합니다. 또 해당 정점에서 인접한 간선을 검사해 방문하지 않은 정점들을 큐에 넣고 방문하는 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없으면 종료합니다. 즉, 과정을 반복하다가 큐에 더 이상 정점이 존재하지 않을 때까지 실행하여 그래프의 모든 정점을 방문하는 알고리즘입니다. 결과적으로 이어진 것을 보면 최소 간선으로 이동할 수 있는 경로가 됩니다. (출처: 삼성 코드 그라운드) [시..

DFS(Depth First Search, 깊이 우선 탐색)는 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 입니다.현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 않은 정점으로 이동합니다. 이 과정을 반복하다가 더 이상 반복할 수 있는 정점이 없으면 마지막으로 통과한 간선을 통해 뒤로 돌아가서 해당 정점에서 방문할 수 있는 정점을 탐색합니다. 이 과정을 반복하여 그래프의 모든 정점을 방문하는 알고리즘 입니다. (출처: 삼성 코드 그라운드) 즉,1) 특정한 순서대로 정점을 계속 방문하다가,2) 정점이 없으면 마지막으로 통과한 간선을 통해 뒤로 돌아가서3) 해당 정점에서 방문할 수 있는 정점을 탐색하는 방법입니다. [자료구조]필요한 자료구조로는,..