본문 바로가기

Algorithm/Algorithm patterns

중복 순열 구하기
Algorithm/Algorithm patterns 2023. 12. 28. 중복 순열 구하기 더보기 참고 문서 이 블로그의 문서: DFS를 사용한 순열 구하기 GitHub: 이 프로젝트의 리포지토리(algorithm) 이 문서의 내용 더보기 순열이란 n개의 값 중에서 r개의 값을 뽑는 모든 경우의 수를 의미합니다. 예를 들어 1, 2, 3 값 중에서 2개의 값을 뽑는 모든 경우의 수는 다음과 같습니다. 순열은 값의 중복을 배제하지 않기 때문에 1, 2 그리고 2, 1이 동시에 나타납니다. [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] 중복 순열은 순열에서 중복을 허용합니다. 위의 예시를 중복 순열에 대해서 계산하면 다음과 같이 나타납니다. [1, 1] [1, 2] [1, 3] [2, 1] [2, 2] [2, 3] [3, 1] [3, 2] [3, 3] 재귀호출을 사용한..
DFS를 사용한 순열 구하기
Algorithm/Algorithm patterns 2023. 12. 6. DFS를 사용한 순열 구하기 더보기 참고 문서 이 블로그의 문서: Swap을 사용한 순열 구하기 GitHub: 이 프로젝트의 리포지토리(algorithm) 이 문서의 내용 더보기 순열이란 n개의 값 중에서 r개의 값을 뽑는 모든 경우의 수를 의미합니다. 예를 들어 1, 2, 3 값 중에서 2개의 값을 뽑는 모든 경우의 수는 다음과 같습니다. 순열은 값의 중복을 배제하지 않기 때문에 1, 2 그리고 2, 1이 동시에 나타납니다. [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] DFS란? 깊이 우선 탐색(DFS, Depth-First Search)은 그래프의 시작 노드를 기준으로 탐색 할 수 있는 가장 깊은 노드까지 진행합니다. 탐색은 마지막 노드에 도달했을 때 종료되고 이전 노드로 돌아온다음 분기된 다른 노..
Swap을 사용한 순열 구하기
Algorithm/Algorithm patterns 2023. 12. 6. Swap을 사용한 순열 구하기 더보기 참고 문서 이 블로그의 문서: DFS를 사용한 순열 구하기 GitHub: 이 프로젝트의 리포지토리(algorithm) 이 문서의 내용 더보기 순열이란 n개의 값 중에서 r개의 값을 뽑는 모든 경우의 수를 의미합니다. 예를 들어 1, 2, 3 값 중에서 2개의 값을 뽑는 모든 경우의 수는 다음과 같습니다. 순열은 값의 중복을 배제하지 않기 때문에 1, 2 그리고 2, 1이 동시에 나타납니다. [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] Swap이란? Swap은 배열에서 두 개 요소의 위치를 서로 바꾸는 것을 의미합니다. static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[..
너비 우선 탐색(BFS, Breadth-First Search)
Algorithm/Algorithm patterns 2023. 12. 5. 너비 우선 탐색(BFS, Breadth-First Search) 이 문서의 내용 더보기 BFS는 하나의 정점에서 시작해 차례대로 모든 정점을 정확히 한 번씩 방문하는 알고리즘입니다. 이 알고리즘의 핵심은 어떤 노드를 방문했었는지 여부를 마킹하는 것입니다. 모든 정점을 정확히 한 번씩 방문해야하는 경우 사용합니다. 일반적으로 루트 노드를 정하고 인접한 노드를 순차적으로 탐색합니다. BFS는 두 노드 사이의 최단 경로를 찾을 때 사용합니다. 또는 좌표계에서 어떤 영역의 크기를 계산하기 위해서 사용합니다(아래 사진 참고, Programmers: PCCP 기출 문제 2번에서 발췌). BFS를 구현하는 방법은 크게 두 가지입니다. 재귀 함수를 사용한 구현 큐(Queue) 자료 구조를 사용한 구현 일반적으로 큐를 사용하는 것이 성능면에서 유리하기 때문에 선호됩니다. BFS 흐름..

티스토리툴바