Brute Force

MS·2022년 7월 13일

알고리즘 개념

목록 보기

2/7

🌿 개념

가능한 모든 경우의 수를 다 해보는 것

🌿 풀이

문제의 가능한 경우의 수를 파악하여 시간복잡도를 계산해본다.
시간복잡도 : O(문제의 개수 * 한 문제를 푸는 데 걸리는 시간)
제한 시간 내에 충분히 구현 가능하다고 파악되면 구현한다.

🌿 유형

🌱 (1) 그냥 다 해보는 방법

하나부터 열까지 다 해보는 유형

🌱 (2) 건너 뛰며 해보기

반복문의 step을 조정하는 유형

🌱 (3) 순열 & 조합

순열 : 문제에서 순서가 중요한 경우
- 시간복잡도 : O(N!)
조합 : 문제에서 선택이 중요한 경우
- 시간복잡도 : O(2^N)

🌱 (4) 재귀

문제의 깊이 (level)에 맞게 재귀 함수를 구현하는 유형
- 백트래킹
  - 조건문으로 검사하여, 함수 호출 횟수를 줄이는 테크닉
  - 의미없는 함수 호출을 줄여 시간 측면에서 좋다!
- 유망성 검사 & 상태 복구
  - 유망성 검사 : 해당 위치에 해당 숫자가 괜찮은지 판단
    (일반적으로, good 함수로 구현)
  - 상태 복구 : 유망성 검사에서 잘못된 판단을 하지 않기 위해, 상태를 복구
    - BOJ2580 스도쿠
    - BOJ9663 N-QUEEN

🌱 (5) 비트마스크

개념
이진수를 이용하여 하나의 정수로 여러 부분집합을 표현하는 테크닉
장점
1. [공간] -> 적은 메모리로 많은 경우를 표현할 수 있다.
  N비트 정수 변수의 경우, N개의 원소를 갖는 집합의 부분집합을 모두 표현할 수 있게 된다.
2. [시간] -> bit 연산은 대개 O(1)으로 구현된다.

🌱 (6) 투 포인터

개념
리스트에 순차적으로 접근해야 할 때, 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
언제?
특정한 합을 가지는 부분 연속 수열을 찾을 때
시간복잡도 : O(N)
코드

// <코드>
int l = 0, r = 0, sum = 0, ans = 0;
	while (l <= r && r < n) {
		if (sum < m) {
			sum += a[r++];
		}
		else if (sum == m) {
			sum += a[r++];
			ans++;
		}
		else {
			sum -= a[l++];
		}
	}
	while (sum >= m) {
		if (sum == m) {
			ans++;
		}
		sum -= a[l++];
	}

// <타당성 증명>
수열 A의 원소는 모두 양수이고 A[a] + ... +A[b] < M, A[a] + ... +A[b+1] > M이라고 할 때,
A[a+1] + ... + A[j] (a+1 <= j <= b) == M인 경우는 존재하지 않는다.
왜?
만일 존재한다고 하면 A[a] + ... + A[b] < M을 만족할 수 없기 때문이다.
따라서 j를 줄이는 것은 의미가 없고, i를 올려야 한다