완전탐색
완전탐색 알고리즘은 문제는 해결하는 전략 중 하나로,
가능한 모든 경우의 수를 다 찾고, 그 중에서 답을 고르는 전략이다.
하지만, 가능한 모든 경우의 수를 다 나열해 보는것은 생각보다 어려운 일이다.
우리가 수학에서 배우는 단순한 경우의 수를 예로 들어보자.
1~4 까지의 숫자가 적힌 공들 중 임의의 두 공을 고르는 모든 경우의 수는 총 6가지이다.
(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)수학적으로는 조합이라는 개념으로 이를 표현한다.
Combination(4, 2) = 6
이렇게 단순하게 모든 경우의수를 생각해낼 수 있는 문제도 물론 존재한다.
하지만 다음과 같은 문제는 어떨까?
Queen은 가로, 세로, 양쪽 대각선 모두 공격이 가능하다.
8 x 8 체스판 위에 8개의 Queen을 서로 공격할 수 없게 배치해야한다.
가능한 모든 경우의 수를 구하시오.
이와 같은 문제는 수학에서 단순하게 공식처럼 배운 개념만으로는 모든 경우의 수를 나열하기 어렵다.
단순한 순서쌍과 같은 형태라기보다는 어떤 상황 자체를 나열해야한다.
그러므로 모든 경우의 수를 표현해내기 위해서는 굉장히 다양한 방법들이 활용될 수 있고,
같은 완전탐색 문제라도 형태나 난이도가 상당히 달라질 수 있다. 이 점을 주의해야한다.
정규화
특정 형태의 답만 고려할 수 있다면?
순서의 강제
순서를 강제시킬 수 있다면?
무차별 대입법
무차별 대입법
무차별 대입법 (Brute Force) 무차별 대입법은 모든 가능한 값을 다 시도해보는 형태의 전략을 의미한다. 그 중에서도 알고리즘 분야에서는 중첩 루프를 이용하여 표현하는 전략을 의미한다. 무차
algorfati.tistory.com
순열, 조합
순열, 조합
조합 모든 경우의 수를 표현하기 위해 자주 사용되는 또다른 전략 중 하나는 조합이다. 조합으로는 어떤 상황이 놓였을 때 선택에 대한 경우의 수를 표현할 수 있다. 예를 들어 다음과 같은 회사
algorfati.tistory.com
비트마스크
비트마스크
비트마스크 현대의 모든 CPU는 이진수를 이용하여 자료를 표현한다. 이러한 구조 덕분에 컴퓨터는 이진법 관련한 연산들을 아주 빠르고 쉽게 수행할 수 있다. 그리고 이 특성을 프로그래밍에서
algorfati.tistory.com
상태 공간 탐색
https://algorfati.tistory.com/132
상태 공간 탐색
상태 공간 탐색 상태 공간 탐색은 인공지능을 포함한 컴퓨터공학에서 사용되는 전략으로, 문제에서 정의될 수 있는 모든 상황들을 상태로 정의하고, 각각의 상태에서 수행할 수 있는 모든 선택
algorfati.tistory.com
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| [Algorithm] 상태 공간 탐색 (0) | 2021.05.20 |
|---|---|
| [Algorithm] 시뮬레이션, 구현 (0) | 2021.05.15 |
| [Algorithm] 순열, 조합 (0) | 2021.05.13 |
| [Algorithm] 무차별 대입법 (0) | 2021.05.13 |
| [Algorithm] 비트마스크 (0) | 2021.05.11 |
