[C++] ICPC 25W 5회차 - 완전탐색, 이분탐색

1. bruteforce(무차별 대입공격)

모든 경우에 대하여 조건에 맞는지 검사하는 방법

다음 연립방정식에서 x와 y의 값을 계산하시오.

   ax+by=c dx+ey=f 각 칸에는 -999 이상 999 이하의 정수만 입력할 수 있다.

<푸는방법>

• 식정리: ax + by = c , dx + ey = f , x = (c-by)/a로 구해두고 d(c-by)/a+ey = f , d(c-by) + ae , y = af y(ae-bd) = af-dc , y = (af-dc)/(ae-bd) 로 구할 수 있나?! --> 오류발생 !!
  • y = (af-dc)/(ae-bd) 에서 ae-bd=0이라면 0으로 나누는 오류 발생, 이를 케어해줬다 해도 나누는 연산으로 인해 각종 억까 발생가능
• x와 y의 범위가 [-999,999]인 정수이므로 모든 (x,y)쌍을 만들었을 때 대략 2000*2000개이다.
  • x와 y를 정해놓고 고 ax+by=c & dx+ey=f를 만족하는지 검사하는 것은 O(1)로 해낼 수 있다.
  • 모든 (x,y)쌍을 만들고 조건으로 주어진 식을 만족하는지 검사하는 것으로 풀 수 있음!

void solve(){
	int a,b,c,d,e,f; cin>>a>>b>>c>>d>>e>>f;
    for(int x=-999; x<=999; x++){
    	for(int y=-999; y<=999; y++){
        	if(a*x+b*y==c && d*x + e*y == f){
            	cout << x << " "<< y << endl;
                return;
              }
          }
     }
}

 

 

브루스포스

• 모든 경우에 대하여 조건에 맞는지 검사하는 방법
  • 모든 답의 후보에 대해서 해당 후보가 조건을 만족하는지 검사한다.
• 위 두가지로 시간복잡도를 계산하면 O(답의 후보의 개수) x O(조건을 검사하는 데에 걸리는 시간복잡도)와 같이 나타낼 수 있다.
• 오류발생한 접근방식: f(a,b,c,d,e,f)=(x,y)꼴  -> a,b,c,d,e,f를 받아서 정답인 x,y 구해내기
• 브루트포스로 풀었을 때는 f(x,y)=0 or 1 꼴! -> x,y를 받아서 해당 x,y가 조건 만족하는지 보기

Q. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계의 게임이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다. 1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다. 2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다. 1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ʻ땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

• 높이를 고정한다는 아이디어가 없다면 풀이를 떠올리기 굉장히 어려움
• 높이를 고정하고 나면 f(i)=높이를 i로 통일할 때의 최소시간 이라는 식 작성 가능
  • f(0)~f(256)까지 구한 뒤 가장 걸린 시간이 적은 높이가 답!
  • 걸린시간은 높이가 정해져있을 때 O(NM)으로 구할 수 있으므로 총 시간복잡도 : O(NM)
  • 땅의 높이는 걸린시간 계산해낼 수 O, 걸린시간은 땅의 높이를 계산해낼 수 X, 땅 평탄화 방법은 257개뿐.

코드

int n, m, b; cin>>n>>m>>b;
for(int i=1; i<=n; i++){
	for(int j=1; j<=m; j++) cin>>arr[i][j];
 }
 
 ll ans=1e18, h;
 for(int y=256; y>=0; y--){
 	ll tmp=0;
    ll bent=b;    
    for(int i=1; j<=n; i++){
		for(int j=1; j<=m; j++){
    	if(arr[i][j] >=y){
        	bent += (arr[i][j]-y);
            tmp+=(arr[i][j]-y)*2;
            } else {
            	bent -= (y-arr[i][j]);
                tmp += (y-arr[i][j]);
            }
           }
           }
           if (bent>=0 && tmp <ans){
           ans=tmp;
           h=y;
           }
           }
           cout << ans << " " << h << endl;

 

2. binary search

• 단조성이 있는 자료에서 탐색 범위를 절반씩 줄여가는 탐색방법
  • 단조성이 있는 자료 : ex) 정렬되어 있는 배열
  • 탐색범위 줄이기 : ex) 마음속으로 1부터 100 사이의 수를 하나 정하고, 다른 사람이 내가 생각한 수 맞추는 것. 만약 말한 수가 내가 생각한 수와 다르다면 내가 생각한 수가 더 큰지 or 작은지 얘기를 해 줌.
    • 단조성으로 인해 up, down이 나올 때마다 절반의 탐색범위 삭제시킬 수 O. 이분탐색은 완전탐색의 최적화
      • 검사해야 하는 후보의 개수: 완전탐색 O(N) , 이분탐색 O(logN)으로 이분탐색이 굉장히 작음

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

Input

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

• STL set을 사용하면 쿼리당 O(logN)에 가능 BUT 이분탐색을 이용해보자.
  1. 배열A 정렬
  2. M개의 수에 대해 각 수가 배열A에 있는지 확인
  3. 정렬되어 있는 배열 A에서 x라는 수를 찾을 때 만약 A[i]가 x보다 크다면 A[i+1]을 볼 필요 x
  4. 따라서 답이 될 수 있는 구간의 중앙을 잡은 뒤 그 중앙을 기준으로 구간을 나눠가면 된다.
  5. 만약 찾는 수와 만났다면 거기서 종료하면 된다.
  6. 만약 계속 옮겼는데 구간 [L,R]의 크기가 0이 되고, 관심없는 구간이 존재하지 않는다면 그대로 종료하면 된다.

코드

int n; cin >> n;
for (int i=1; i<=n; i++) cin >> A[i];
sort(first A+1, last: A+n+1); //여기서 A가 아니라 왜 A+1이라 하는거지?
int m; cin >> m;
while (m--){
	int x; cin>>x;
    int l=1, r=n;
    int ok=0;
    while (l<=r){
    	int mid=(l+r)/2;
        if(A[mid]==x){
        	ok=1;
            break;
            }
            if(A[mid]>x){
				r=mid-1;
             }
			else if(A[mid]<x){
            	l=mid+1;
              }
              }
              cout << ok << '\n';
          }

• 코드에서 sort(A+1, A+n+1) 이렇게 A+1을 사용하는 이유는 배열의 인덱스가 1부터 시작하도록 맞추기 위해서.
  • sort(A,A+n)을 하면 인덱스 0부터 n-1까지 정렬
  • 이 코드에서는 배열을 1번 인덱스부터 사용하고 있음 -> A[1]부터 A[n]까지 정렬하려면 +1을 해 줘야 함.
• 이분탐색으로 수 하나를 찾을 때마다 O(logN)이고, 찾아야 하는 수가 M개. -> O(MlogN+NlogN)으로 풀 수 있다.

 

 

• 이분탐색은 단순히 배열에서만 사용할 수 있는 것 X

전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다. 풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다. 대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다! 각 스태프가 풍선 하나를 만드는 시간(분) Ai를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?

 

Input

스태프의 수 N과 풍선의 개수 M이 입력된다. (1 ≤ N, M ≤ 1 000 000) 다음 줄에 N명의 각 스태프들이 풍선 하나를 만드는 데 걸리는 시간 Ai가 순서대로 주어진다. Ai는 1 000 000 이하의 자연수이다.

[2가지 접근법]

1. 레전드 식정리를 통해 M개 이상을 만드는 최소 시간 찾기(불가능)
2. 그냥 모든 시간에 대해서 M개 이상인지 확인하기
   • f(i)=시간이 i일때 풍선 M개를 만들 수 있는가? 
     • 만들 수 있으면 1, 없으면 0으로 정의
     • f(i)를 구하는 시간: 시간이 i일때 만드는 풍선의 개수를 구한 뒤 M개 이상인지 보면 됨.
       • i/A[1]+i/A[2]+...+i/A[n]이 M이상인지 확인 -> O(N)
         • 답이 될 수 있는 i의 범위: M*100만
         • 만약 스태프가 1명, 만들어야 하는 풍선 M이 100만개, 스태프가 풍선 하나를 만드는 데 걸리는 시간이 100만이라면 저런 결과가 나올 수 있음
           • 그러면 i의 범위는 1부터 1e12(1조)이고, 검사하는 데에는 O(N)이 소요되니 절대 시간 내에 풀 수 없음.
         • BUT 얘를 이분탐색으로 최적화. 
           • 만약 i시간일 때 M개를 만들 수 있으면 i+1시간일 때도 만들 수 있나? YES!
           • 만약 i시간일 때 M개를 만들 수 있으면 i-1시간일 때도 만들 수 있나? NO.
           • 이분탐색 -> 탐색할 값이 1e12개에서 log2(1e12)로 바뀐다. 값을 검사하는건 O(N)이니 총 시간복잡도는 O(Nlog(1e12))가 된다!

ll n,m; cin >> n >> m; // 근데 대체 저 ll은 무엇이란 말인가
for(int i=1; i<=n; i++) cin >> A[i];
ll l=1, r=1e12;
ll ans;
while(l<=r){
	ll mid=(l+r)/2;
    ll cnt=0; 
    for(int i=1; i<=n; i++){
    	cnt+= mid/A[i];
        }
        if(cnt >= m){
        	ans = mid;
            r=mid-1;
            }
            else{
            l=mid+1;
            }
            }
            cout << ans << endl;

• ll : long long의 줄임말로 보통 다음과 같이 typedef 사용해서 "typedef long long ll; 처럼 정의.
  
  • long long : 64비트 정수형-> 큰 범위 숫자를 다룰 때 사용