순열
-
[Graph] 그래프의 탐색 - 깊이 우선 탐색 (DFS, Depth-First Search)알고리즘, 코딩테스트/알고리즘 개념 2023. 12. 5. 02:12
알고리즘 문제에서 가장 큰 비중을 차지하는 유형 중 하나가 바로 그래프 탐색 문제다. 어떤 형태의 코딩 테스트, 알고리즘 시험에서든 가장 쉽게 만날 수 있는 문제 유형이기도 하고 여러 문제가 출제되는 형식이라면 반드시 한문제 이상 포함된다고 할 수 있을 정도다. 그래프 탐색 알고리즘은 필수 중 필수이기 때문에 반드시 익숙해져야 한다. 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 대표적인 그래프 탐색 알고리즘 중 하나다. 직관적인 이름 그대로 깊이를 따라서 탐색해나가는 방법으로 너비 우선 탐색(BFS)과 대조되는 특징을 가진다. BFS의 경우 동시에 여러 갈래의 길을 뻗어나가듯 탐색한다면 DFS는 일반적으로 미로찾기를 해나갈 때와 같이 분기점에서 하나의 길을 선택하고 그 길을 따..
-
[백준 BOJ/C++] 1759 암호 만들기알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 18. 00:52
1759번: 암호 만들기 아주 어렵지 않고 재밌게 풀 수 있는 순열/조합 문제다. Input으로 주어지는 알파벳 소문자를 중복 없이 조합하되 간단한 룰을 만족하는 조합을 찾아내면 된다. 1. 알파벳 사전 순서로 정렬 2. 1개 이상의 모음(a, e, i, o, u)과 2개 이상의 자음을 포함 위 규칙을 만족하면서 각 요소의 중복이 없는 조합을 만들어 모두 출력해야 한다. 이런 순열, 조합의 문제는 DFS로 구현하거나 간단히 각 언어마다 제공되는 API가 있다면 이를 이용해 어렵지 않게 풀어낼 수 있다. 문제의 포인트 순열 혹은 조합 구하기 순서가 의미를 가지고 중복을 허용하지 않는다는 점에서 순열이라고 할 수 있겠지만 사실 순서는 정해져 있는 것이기 때문에 일반적인 순열 문제와 같이 접근하지는 않았다. ..