알고리즘 캠프

개념

완전탐색 : 가능한 경우의 수를 모두 조사하는 방법
컴퓨터는 1억(10^8)=1초 이기 때문에 컴퓨터에게 있어서 부르트 포스는 어렵지 않다.

문제

2231 분해합

숫자를 가지고 각자리의 합이 원하는 값이 나오면 된다.

여기에서 제한이 1,000,000 밖에 되지 않기 때문에 1부터 시작해서 값 이전까지 구하면 된다.

import sys,heapq
sys.stdin=open("input.txt","r")
input=sys.stdin.readline

t=int(input())

ans=0
flag=True
for i in range(1,t):
    ans=i
    temp=str(i)
    for j in range(len(temp)):
        ans+=int(temp[j])
    if(ans==t):
        print(i)
        flag=False
        break
if(flag):print(0)

1018 체스판 다시 칠하기

지민이가 mxn 판을 가지고 와서 8x8 의 검흰이 반복되는 체스판을 만드는 문제이다.

나올수 있는 경우가 (M-7)x(N-7) 정도 될것이다. 하지만 제한이 50이다. 여기에 추가로 8x8 칸을 모두 확인할 테니 50x50x8x8=160,000 경우밖에 없다.

조금 더 빠르게 검사하는 방법
Case 1: 모든 B 짝수이면 모든 W 홀수
Case 2: 모든 B 홀수이면 모든 W 짝수

import sys,heapq
sys.stdin=open("input.txt","r")
input=sys.stdin.readline

n,m=map(int,input().split())
a=list(list(map(str,input().rstrip())) for _ in range(n))
ans=1e9
for i in range(n-7):
    for j in range(m-7):
        # num1은 정상적인 것
        # num2는 수정해야 하는 것
        num1=0
        num2=0
        for k in range(i,i+8):
            for l in range(j,j+8):
                if(a[k][l]=='W'):
                    if((k+l)%2==0): num1+=1
                    else: num2+=1
                else:
                    if((k+l)%2==0): num2+=1
                    else: num1+=1
        ans=min(ans,num1,num2)

print(ans)

15649 N과 M(1)

브루트포스 재귀의 대표적인 유형

8가지 수를 8칸에 넣는 것이기에 8^8<10^8 의 문제이다.

그냥 for문을 8중으로 중첩시키어야 하는데 당연컨데 풀 수가 없다. 그래서 이렇게 for문이 과하게 중첩되거나 가변적이면 재귀를 이용하는 방법이 있다.

재귀함수란? 어떤 함수에서 자기 자신을 호출하는 함수를 지칭한다.
반드시 기조코드를(반환코드) 잘 세우자

---

백트래킹 : 현재 상태에서 가능한 후보군으로 가지를 치며 탐색하는 알고리즘

위와 같이 할 수 있는 경우로 가지를 치는 알고리즘이다.

변수로는 인덱스,입력값들 + 확인 배열,정답 배열

import sys,heapq
#sys.stdin=open("input.txt","r")
input=sys.stdin.readline

n,m=map(int,input().split())

a=[0]*(m)
check=[False]*(n+1)
def go(index,n,m):
    if(index==m):
        print(' '.join(map(str,a)))
        return
    
    for i in range(1,n+1):
        if(check[i]): continue
        check[i]=True
        a[index]=i
        go(index+1,n,m)
        check[i]=False

go(0,n,m)

15650 N과 M(2)

import sys,heapq
sys.stdin=open("input.txt","r")
input=sys.stdin.readline

n,m=map(int,input().split())

a=[0]*(m)
check=[False]*(n+1)
def go(index,select,n,m):
    if(index==m):
        print(' '.join(map(str,a)))
        return
    
    for i in range(select,n+1):
        if(check[i]): continue
        check[i]=True
        a[index]=i
        go(index+1,i,n,m)
        check[i]=False

go(0,1,n,m)

9663 N-Queen

내가 알기로는 이건 DFS 문제이다.

필수적인 것은 같은 (/)대각선에 위치한 것의 행과 열의 합은 동일하다.
() 행과 열을 뺀것과 동일하다.

import sys,heapq
sys.stdin=open("input.txt","r")
input=sys.stdin.readline

n=int(input())
ans=0
c=[0]*n

def check(index):
    for i in range(index):
        if(c[i]==c[index] or abs(c[i]-c[index])==index-i):
            return False
    return True

def go(index,n):
    global ans
    if(index==n):
        ans+=1
        return
    
    for i in range(n):
        c[index]=i
        if(check(index)):
            go(index+1,n)
go(0,n)
print(ans)

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <cmath>
#include <stack>
#include <string>
#include <queue>
#define ll long long
#define len 1001
using namespace std;

int ans, i,n;
int c[16];
bool check(int index) {
	for (int i = 0; i < index; ++i) {
		if (c[i] == c[index] || abs(c[i] - c[index]) == (index - i)) return false;
	}
	return true;
}
void go(int index){
	if (index == n) {
		ans += 1;
		return;
	}
	for (int i = 0; i < n; ++i) {
		c[index] = i;
		if (check(index)) {
			go(index + 1);
		}
	}
}
int main(void) {
	freopen("input.txt", "r", stdin);
	
	cin >> n;
	go(0);
	printf("%d",ans);
}