Back to the Basics

Rock Paper Scissors 1. 문제 이 문제는 가위바위보를 n 판 했을 때 한 사람이 낼 수 있는 모든 경우의 수를 구하는 문제이다. R=Rock , P=Paper, S=Scissors라고 할 때 4판을 했을 때 트리 구조로 구성을 해보면 아래와 같다. 중학생 때 배웠던 수학을 떠올려보자, 한 판을 할 때마다 R, P, S 3개 중 중복을 허용하여 뽑는 경우의 수 3Π\PiΠ1과 같다. 바로 중복순열이다. 중복순열은 자료구조 DFS를 이용하여 전체를 순환하는 방식을 사용한다. DFS에 대한 개념적인 내용은 Section2의 첫 부분인 자료구조에서 이미 정리한 바가 있으니 참고하자 자료구조/알고리즘] Graph - BFS , DFS 입력 : depth 또는 없음 출력 : 2차원 배열 조건 : 여..

그래프를 순회하는 방법 중 가장 일반적인 너비 우선 검색과 깊이 우선 검색에 대해 공부한다 1. 너비 우선 방법 (BFS , Breadth-First Search) 그림출처 위의 그림과 같이 그래프에서 연결된 노드와 해당 노드들 간의 간선을 순서대로 검색하는 알고리즘을 말한다. 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회한다. 이진트리검색의 차수 우선 순회와 비슷한 개념이다. 구현을 위해서는 Queue를 필요로 한다. 시간 복잡도 O(V+E) : V는 정점의 개수이고 E는 간선의 개수이다. 전체 그래프를 순회하기 위해 모든 정점과 간선을 방문해야 하기 때문 아래의 무지향성 그래프의 예와 함께 코드를 분석해보자 탐색 순서는 a → b → d→ c →e 이다. 아래 코드에서 ver..