완전 탐색

에라토스테네스의 체

n=1000
primes=list(range(n+1))
primes[1] = 0

for i in range(2,int((n+1)**0.5)):
  if primes[i] != 0:
    for j in range(2*i, n+1, i):
        primes[i] = 0

+ 추가적으로 그냥 반목문에 의해 소수 구하기

def sol1(n):
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False

    return True

number = 100
print(sol1(number))

백트랙킹

아래의 문제들은 파이썬 라이브러리를 사용하면 간단히 풀수 있지만 백트랙킹을 이해하는데 좋은 문제들이다.

결과값의 순서를 보고 코드의 차이점을 머리속으로 생각을 해보자!

1. 중복O + 순서있게 (product 함수)

n,m = 3,2
arr = []
result = []
def sol(depth):
    global n,m,arr,result
    if m == depth:
        result.append(list(arr))
        return

    for i in range(1,n+1):
        arr.append(i)
        sol(depth+1)
        arr.pop()

sol(0)
print(result)

2. 중복 x + 순서있게 (permutations 함수)

15649번: N과 M (1)

n,m = 3,2
arr = []
visit = [False]*(n+1)
result = []

def sol(depth):
    global n,m,arr,visit,result
    if depth == m:
        result.append(list(arr))
        return

    for i in range(1,n+1):
        if visit[i] == False:
            visit[i] = True
            arr.append(i)
            sol(depth+1)
            arr.pop()
            visit[i] = False

sol(0)
print(result)

 

3. 중복O + 고르기 (combinations_with_replacement 함수)

15652번: N과 M (4)

n,m = 3,2
arr = []
result = []

def sol(depth,start):
    global n,m,arr,result

    if depth == m:
        result.append(list(arr))
        return

    for i in range(start,n+1):
        arr.append(i)
        sol(depth+1, i)
        arr.pop()

sol(0,1)
print(result)

4. 중복x + 고르기 (combinations 함수)

15650번: N과 M (2)

n,m = 3,2
arr = []
result = []

def sol(depth,start):
    global n,m,arr,result
    if depth == m:
        result.append(list(arr))
        return
    for i in range(start,n+1):
            arr.append(i)
            sol(depth+1, i + 1)
            arr.pop()

sol(0, 1)
print(result)