브루트포스

dragonappear·2021년 1월 10일
0

Algorithm

목록 보기
4/5

브루트포스

핵심: 모든 경우의 수를 계산하고, 다 해보는 것
방법의 수가 적은 경우에만 사용하는것이다.
모든 문제를 풀수있는 방법이 아니다.
보통 재귀,순열,비트마스크를 사용해서 문제를 푼다.

  1. 문제의 가능한 경우의 수를 계산해본다. -> 직접 계산을 통해서 구한다.(손으로 계산)
  2. 가능한 모든 방법을 다 만들어본다.-> 하나도 빠짐 없이 만들어야한다.(재귀,순열,비트마스크)
  3. 각각의 방법을 이용해 답을 구해본다. -> 문제에 나와있는대로 답을 구해본다.
  4. 시간복잡도: 방법의 수 X 방법 1개의 시간복잡도

1. 그냥 다해보기

  1. 일곱난쟁이(https://www.acmicpc.net/problem/2309)

경우의수 = 9C2

  1. 사탕게임(https://www.acmicpc.net/problem/3085)

경우의수 = 2N^2
시간복잡도 = N^4

  1. 날짜계산(https://www.acmicpc.net/problem/1476)

경우의수 = 15 X 28 X 19

  1. 리모콘(https://www.acmicpc.net/problem/1107)

경우의수 = 1,000,000
숫자버튼을 누르고, 그 다음 +나- 중 하나만 연속해서 눌러야한다.
위 방법이 아니면 의미없는 방법이 포함되거나 같은 것이 반복되어서 최소를 구할수없다.

  1. 테트로미노(https://www.acmicpc.net/problem/14500)

회전,대칭가능 -> 블록의 개수 = 19가지
경우의수 = 19(어떤 테트로미노결정) X (NM)(=어디에 놓을건지 결정)

2. 건너 뛰며 해보기

  1. 카잉달력(https://www.acmicpc.net/problem/6064)

  2. 수이어쓰기1(https://www.acmicpc.net/problem/1748)

3. N중 for문

  1. 1,2,3 더하기(https://www.acmicpc.net/problem/9095)

4. 재귀★★★★★

1.순서와 관련된 문제
2.선택과 관련된 문제

  1. N과M (1)★ (https://www.acmicpc.net/problem/15649)
  • 순서와 관련된 문제
  1. N과M (2)★★★ (https://www.acmicpc.net/problem/15650)
  • 순서와 선택★★★★★ 두가지 관점에서 문제풀이 가능
  1. N과M (3)★ (https://www.acmicpc.net/problem/15651)
  • 중복가능한점을 이용
  1. N과M (4)★ (https://www.acmicpc.net/problem/15652)

  2. N과M (5)(https://www.acmicpc.net/problem/15654)

  3. N과M (6)(https://www.acmicpc.net/problem/15655)

  4. N과M (7)(https://www.acmicpc.net/problem/15656)

  5. N과M (8)(https://www.acmicpc.net/problem/15657)

  6. N과M (9)(https://www.acmicpc.net/problem/15663)

  7. N과M (10)(https://www.acmicpc.net/problem/15664)

  8. N과M (11)(https://www.acmicpc.net/problem/15665)

  9. N과M (12)(https://www.acmicpc.net/problem/15666)

5. 순열

모든 순서를 시도해보아야하고, 순서가 매우 중요한 의미가 있을때 사용한다.
임의의 수열을 다른 순서로 섞는 연산
첫순열(오름차순)에서 다음순열, 다음순열, ... , 마지막 순열(내림차순)까지 이동한다

다음순열

  1. a[i-1] < a[i]를 만족하는 가장 큰 i를 찾는다. -> O(N)
  2. j>=i 이면서 a[j]>a[i-1]를 만족하는 가장 큰 j를 찾는다 -> O(N)
  3. a[i-1]과a[j]를 swap한다. -> O(1)
  4. a[i]부터 순열을 뒤지는다. -> O(N)
  5. 전체순열 시간복잡도: O(N x N!)

문제

  1. 다음 순열(https://www.acmicpc.net/problem/10972)

  2. 이전 순열(https://www.acmicpc.net/problem/10973)

  3. 모든 순열(https://www.acmicpc.net/problem/10974)

  4. 차이를 최대로(https://www.acmicpc.net/problem/10819)

  5. 외판원 순회2(https://www.acmicpc.net/problem/10971)

  6. ★★★로또(https://www.acmicpc.net/problem/6603)

6. 재귀

다음상태란: 문제의 정답을 아직 구하지못하였고, 정답을 구하러가기 위해서 문제의 조건을 위배하지 않으면서 다음 상태를 만들어줘야 한다!

문제

  1. 1,2,3 더하기(https://www.acmicpc.net/problem/9095)

브루트포스(재귀)를 이용할때 찾아봐야하는것

  • 불가능한 경우 (sum>goal) : 재귀호출을 계속해도 정답을 절대 찾을수없는 경우 또는 문제의 조건을 위배한 경우
  • 정답을 찾은 경우 (sum==goal)
  • 다음 경우(재귀함수)를 호출 (go(count+1,sum+i,goal))
  1. 암호 만들기(https://www.acmicpc.net/problem/1759)
  • 경우의 수 = 2^c
  • 불가능한 경우 (i>=alpha의크기)
  • 정답을 찾은 경우 (만든 password의 길이==n)
  • 다음 경우 호출:
    1. i번째를 사용(go(n,alpha,password+alpha[i],i+1))
    2. i번째를 사용x (go(n,alpha,password,i+1))
  • 시간복잡도: 2^c
  1. 퇴사 (https://www.acmicpc.net/problem/14501)
  • 경우의 수 = 2^N
  • 함수 : go(day,sum)
  • 불가능한 경우 (day>n+1)
  • 정답을 찾은 경우 (day==n+1)
  • 다음 경우 호출:
    1. 상담을 한다 (go(day+t[day],sum+p[day]))
    2. 상담을 하지않는다 (go(day+1,sum))
  • 시간복잡도: 2^N
  1. 스타트와 링크(https://www.acmicpc.net/problem/14889)
  • 경우의 수 = 2^N
  • 함수 : go(index,first,second)
  • 불가능한 경우 ()
  • 정답을 찾은 경우 (index==n+1)
  • 다음 경우 호출(두 경우 모두 호출 전에 first 또는 second에 index를 넣고 호출 후에 빼는 과정이 필요):
    1. index사람을 1번 팀에 넣는다 go(index,first,second)
    2. index사람을 2번 팀에 넣는다 go(index,first,second)
  • 시간복잡도: 2^N
  1. <백트래킹을 이용>링크와 스타트(https://www.acmicpc.net/problem/15661)
  • 경우의 수 = 2^N
  • 함수 : go(index,first,second)
  • 불가능한 경우 (first의 크기>n/2 or second의 크기>n/2)
  • 정답을 찾은 경우 (index==n+1)
  • 다음 경우 호출(두 경우 모두 호출 전에 first 또는 second에 index를 넣고 호출 후에 빼는 과정이 필요):
    1. index사람을 1번 팀에 넣는다 go(index,first,second)
    2. index사람을 2번 팀에 넣는다 go(index,first,second)
  • 시간복잡도: 2^N
  1. <백트래킹을 이용>부등호(https://www.acmicpc.net/problem/2529)
  • 경우의 수 = 9^k
  • 함수 : go(index,num)
  • 불가능한 경우 (index>n+1)
  • 정답을 찾은 경우 (index==n+1)
  • 다음 경우 호출: go(index+1,num+to_string(index))
  1. <백트래킹을 이용>맞춰봐(https://www.acmicpc.net/problem/1248)

7. 비트마스크

문제에 전체개수 중 일부를 이용해서 모든 방법을 구할때 이용할수있다.

비트마스크 연산

  1. 정수로 집합을 나타낼수 있다.
    {1,3,4,5,9} = 570 = 2^1 + 2^3 + 2^4 + 2^5 + 2^9
  2. 0~N-1까지 정수로 이루어진 집합을 나타낼수있다.
  3. 비트마스크 연산
    • 검사연산: 정수에 어떤 비트가 1인지 검사할수있다. ex(570 & (1<<1) = 2 -> 1번째 비트가 포함되어있는지 검사)
    • 추가연산: ex) 2번째(4) 비트추가하기 -> 570 | (1<<2) = 574
    • 제거연산: ex) 1번째(2) 비트제거하기 -> 570 & ~(1<<1) = 568
    • 토글연산: ex) 1번째(2) 비트토글하기 -> 570 ^ (1<<1) = 568
    • 전체집합 = (1<<N) - 1, 공집합=0

문제

  1. 집합(https://www.acmicpc.net/problem/11723)
  2. 부분수열의 합(https://www.acmicpc.net/problem/1182)

모든 집합의 개수=2^N
모든 집합을 구해보면 된다!

  1. 스타트와 링크(https://www.acmicpc.net/problem/14889)

모든 집합의 개수=2^N
모든 집합을 순회해본다!

  1. 종이조각(https://www.acmicpc.net/problem/14391)

  1. 최솟값을 구하는 문제에서 의미없는 것이 있는 방법은 절대 최소가 될수없다.
  2. 최솟값을 구하는 문제에서 중복이 존재하는 방법은 절대 최소가 될수없다.
  3. 백트래킹: 재귀함수를 이용해 브루트포스를 하다보면, 더이상 함수호출이 의미없는 경우가 생기는데 이런 경우를 제외하고 브루트 포스를 진행하면 백트래킹이라고 한다.

0개의 댓글