공부상자

1. 순열순열이란 서로 다른 n개의 원소를 가지는 어떤 집합에서 중복 없이 "순서에 상관있게" r개의 원소를 선택하거나 혹은 나열하는 것이다.영어로 permutation이고 nPr로 표현한다.nPr = n! / (n - r)! 순열을 코드로 구현할 때는 DFS를 사용할 수 있다.방문여부를 체크하는 배열을 두고 뽑았는지 안 뽑았는지를 구별할 수 있고 파라미터로 r과 현재 뽑은 개수 c를 보내주면 된다.(전역변수로 집합이 있는 케이스가 아니라면 n도 같이 보내줘야한다.)그리고 순서에 상관있기 때문에 무조건 0번째 인덱스부터 반복하면 된다.방문여부 체크 배열의 값을 true로 했다가 false로 하는 이유는 해당 숫자가 다른 경우의 수에서 사용될 수 있기 때문이다.val list = intArrayOf(1, ..

DFS와 BFS는 그래프 탐색 알고리즘 1. DFS(Depth First Search) : 깊이 우선 탐색 그래프를 탐색 할때 특정한 경로로 쭉 타고 끝까지 내려간 후 특정한 경로의 시작으로 다시 돌아와 다른 경로를 방문 - 스택 또는 재귀함수를 사용하여 구현 가능 - 탐색 순서(스택) 1. 시작노드를 스택에 삽입하고 방문표시 2. 스택의 최상단 노드의 인접 노드 중에 방문하지 않은 노드가 하나라도 있으면 그 노드를 스택에 삽입하고 방문표시 3. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼내고 최상단 노드의 인접 노드를 계속 확인 4. 2~3번 과정을 수행할 수 없을 때까지 반복 5. 모든 노드를 방문하면 탐색 종료 - 탐색 순서(재귀함수) 1. 재귀함수에 시작노드를 넣어 호출 2. (시작..