-
목표
- 순열에 대해 알아보자
- 순열을 이용한 문제 풀이
순열 배경
- 다양한 조합 문제를 해결하기 위해 등장
- 요소들의 배열과 선택에 대한 방법의 필요성
순열이란?
- 수학적 관점 - 순서대로 나열 한 것, 나열한 경우의 수
- 알고리즘 관점 - 서로 다른 요소들을 모든 가능한 방법으로 배열
- 예를 들면 "ABC"의 경우 가능한 순열은 "ABC, ACB, BAC, BCA, CAB, CBA" 이다.
- 즉 ABC의 모든 조합, 경우의 수를 알 수 잇음
순열 활용하기
- 다양한 모든 순서를 고려해보고 싶다면. 순열을 활용해보자.
- 다양한 모든 순서가 몇번인지가 궁금하면 수학적으로 접근해보자.
n P c = n! / (n - c)!
n은 총 개수
c는 선택할 요소의 수
!는 팩토리얼
"ABC"의 순열의 수는 3P2 즉 3! / ( 3 - 2)! 이므로 경우의 수는 3!
- 알고리즘 문제 풀어보기
백준 - https://www.acmicpc.net/problem/10974
정리 및 느낀 점
- 수학적인 관점과 알고리즘 적인 관점을 잘 이해해야한다
- 모든 경우의 수를 파악할 때 좋은 알고리즘이다.