우선 입력받은 배열을 바로 정렬하고, 그 배열로 부분집합을 만드는 것까지는 바로 생각이 난다.
하지만 그렇게 만든 부분집합에서 조건으로 걸러야 한다.
make_key(cur_candidate + [candidate[index]], index + 1)
make_key(cur_candidate, index + 1)
이렇게 재귀함수로 현재의 값을 추가하는 집합 하나, 추가하지 않는 집합 하나를 만들어준다.
def make_key(cur_candidate, index):
if index == C:
value = len(set(cur_candidate).intersection(important))
if len(cur_candidate) == L and value >= 1 and (L - value) >= 2:
for i in cur_candidate:
print(i, end='')
print()
return
else:
make_key(cur_candidate + [candidate[index]], index + 1)
make_key(cur_candidate, index + 1)
이렇게 하나씩 추가하다가 인덱스가 C를 넘어갔을 때, 현재 부분집합의 길이가 L이고 모음이 하나 이상 있고 자음이 2개 이상 있을 때만 출력이 되도록 해줬다.
import sys
L, C = map(int, sys.stdin.readline().split())
candidate = sorted(list(map(str, sys.stdin.readline().split())))
important = {'a', 'e', 'i', 'o', 'u'}
def make_key(cur_candidate, index):
if index == C:
value = len(set(cur_candidate).intersection(important))
if len(cur_candidate) == L and value >= 1 and (L - value) >= 2:
for i in cur_candidate:
print(i, end='')
print()
return
else:
make_key(cur_candidate + [candidate[index]], index + 1)
make_key(cur_candidate, index + 1)
make_key([], 0)
하지만 2, 4, 6, 8... 이렇게는 셀프 넘버가 아닌 것을 보고 d(1) = 1 + 1 = 2가 된다는 것을 깨닫고 풀 수 있게 되었다.
만약 푸는 중간에 알게 되었다면 고생 좀 했을 것 같다.
우선 d(n)에 대한 함수를 만들어주자.
def d(n):
d_result = n
while n > 9:
d_result += (n % 10)
n //= 10
return d_result + n
해당 수와 쪼갠 수들을 모두 더해서 반환해주는 d(n) 함수이다.
result = [True for i in range(1, 10001)]
def d(n):
d_result = n
while n > 9:
d_result += (n % 10)
n //= 10
return d_result + n
for i in range(1, 10000):
if result[i]:
print(i)
num = i
while num < 10000:
num = d(num)
if num < 10000:
result[num] = False
1부터 10000까지 반복을 하면서 만약 result[i]에 대한 수가 True라면 해당 수를 출력하고, 그 수로 만들 수 있는 수들을 연쇄적으로 모두 지워준다.
당연히 해당 좌표를 비우고 간다면 모든 게임판을 채울 수 없게 되고, 이 이외의 블록 종류들은 다른 칸에서 놓는 블록의 모양과 중복이 된다.
게임판을 받았을 때 다음으로 채워야 하는 좌표를 반환해주는 함수이다.
def find(h_len, w_len):
for q in range(h_len):
for r in range(w_len):
if board_list[q][r] == '.':
return [q, r]
return [-1, -1] # 모든 칸이 덮여있으면
모든 칸에 블록이 있다면 -1, -1을 리턴해주어 호출한 곳에 알려준다.
게임판에 해당 타입의 종류의 블록을 놓을 수 있는지 알려주는 함수이다.
def is_blank(x, y, block_type):
for q in range(3):
if 0 <= x + block[block_type][q][0] < h and 0 <= y + block[block_type][q][1] < w:
if board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] == '#':
return False
return True
게임판을 '#'으로 덮어주거나, '.'으로 치워주는 함수이다.
def cover_block(x, y, block_type, blank_or_block):
for q in range(3):
board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] = blank_or_block
백트래킹에서는 정답의 경우가 없으면 복구를 해줘야 하기 때문에 blank_or_block으로 '.'도 받아서 복구도 할 수 있도록 하였다.
block_type으로 블록의 종류를 받고 해당 칸 만큼 채워주거나 치워준다.
def solve(board_list, h, w):
global result
result = 0
# 놓을 수 있는 블록의 종류
block = [[[0, 0], [1, 0], [0, 1]], [[0, 0], [0, 1], [1, 1]], [[0, 0], [1, 0], [1, 1]], [[0, 0], [1, 0], [1, -1]]]
def cover():
global result
x, y = find(h, w)
if x == -1 and y == -1:
result += 1
return
for q in range(4):
if is_blank(x, y, q):
cover_block(x, y, q, '#')
cover()
cover_block(x, y, q, '.')
def find(h_len, w_len):
for q in range(h_len):
for r in range(w_len):
if board_list[q][r] == '.':
return [q, r]
return [-1, -1] # 모든 칸이 덮여있으면
def is_blank(x, y, block_type):
for q in range(3):
if 0 <= x + block[block_type][q][0] < h and 0 <= y + block[block_type][q][1] < w:
if board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] == '#':
return False
return True
def cover_block(x, y, block_type, blank_or_block):
for q in range(3):
board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] = blank_or_block
cover()
print(result)
사용한 함수의 전체이다.
함수 안에 함수들을 넣어서 최대한 깔끔하게 정답을 리턴할 수 있도록 했다.
cover() 함수에서 find를 좌표들을 돌며 채워주고 복구해주는 백트래킹 방법을 사용했다.
만약 find()에서 -1, -1을 리턴받으면 외부 전역 변수 result에 +1을 해준다.
import sys
result = 0
def solve(board_list, h, w):
global result
result = 0
# 놓을 수 있는 블록의 종류
block = [[[0, 0], [1, 0], [0, 1]], [[0, 0], [0, 1], [1, 1]], [[0, 0], [1, 0], [1, 1]], [[0, 0], [1, 0], [1, -1]]]
def cover():
global result
x, y = find(h, w)
if x == -1 and y == -1:
result += 1
return
for q in range(4):
if is_blank(x, y, q):
cover_block(x, y, q, '#')
cover()
cover_block(x, y, q, '.')
def find(h_len, w_len):
for q in range(h_len):
for r in range(w_len):
if board_list[q][r] == '.':
return [q, r]
return [-1, -1] # 모든 칸이 덮여있으면
def is_blank(x, y, block_type):
for q in range(3):
if 0 <= x + block[block_type][q][0] < h and 0 <= y + block[block_type][q][1] < w:
if board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] == '#':
return False
return True
def cover_block(x, y, block_type, blank_or_block):
for q in range(3):
board_list[x + block[block_type][q][0]][y + block[block_type][q][1]] = blank_or_block
cover()
print(result)
for _ in range(int(sys.stdin.readline())):
H, W = map(int, sys.stdin.readline().split())
board = []
blank_cnt = 0
for i in range(H):
board.append(list(sys.stdin.readline().strip()))
blank_cnt += board[-1].count('.')
# 빈칸의 수가 3의 배수가 아니면 어차피 덮지 못하니 continue
if blank_cnt % 3 != 0:
print(0)
continue
solve(board, H, W)
요즘 브루투 포스 알고리즘을 풀면서 생각하는 건데 브루트 포스 문제는 백트래킹 기법을 같이 사용해서 푸는 문제가 많은 것 같다.
재귀함수를 이용하다보니 조건을 만족하면 되돌아 오는 백트래킹을 많이 쓰는 것 같다.
덕분에 함수 다루는 실력이 좀 향상된것 같다. ㅎㅎ (지극히 내 생각이다.....)
함수를 2개 사용했다.
첫 번째 함수는 현재 있는 멤버에 새로운 친구가 들어갈 수 있는지 확인해주는 함수이다.
# 새로 들어온 친구가 들어갈 수 있는지 확인하는 함수이다.
# 리스트에 첫 번째 인덱스는 0이 있으니 제외하고 시작하자.
def is_friend(plus_friend, member_list):
for q in member_list[1:]:
if plus_friend not in friends[q]:
return False
return True
굳이 설명할 필요가 없을 거라고 생각된다.
두번째 함수는 재귀함수 + 백트래킹 함수 + 탐색 함수이다.
이 함수가 핵심이다.
# cur_cnt는 현재 만들어진 멤버의 수, cur_list는 그 멤버의 번호이다.
def find_friends(cur_cnt, cur_list):
# 멤버를 K명 모으면 함수를 종료한다. (재귀함수의 기저사례)
if cur_cnt == K:
for q in cur_list[1:]:
print(q)
return True
# 순서대로 들어가기 때문에 cur_list에 있는 번호가 가장 큰 멤버는 -1의 인덱스에 있다.
# 대신 빈 리스트에 -1을 부르면 에러가 뜨기 때문에 이 함수 호출 전에 반복문으로 0을 넣어주고 시작한다.
for q in range(cur_list[-1] + 1, N + 1):
if is_friend(q, cur_list):
cur_list.append(q)
if find_friends(cur_cnt + 1, cur_list):
return True
cur_list.pop()
return False
우선 함수가 종료되는 조건은 멤버의 수가 K가 되는 조건이다.
글을 작성하면서 생각해보니 굳이 cur_cnt를 쓰지 않고 len함수를 이용해서 인수를 하나 줄일 수 있었을 것 같다.
아래 반복문은 아직 확인하지 않은 값을 is_friend로 확인하면서 가능하다면 해당 멤버를 추가해 다시 함수를 호출하는 부분이다.
백트래킹에서 사용하듯이 만약 해당 값으로 답을 찾을 수 없다면 다 확인해본 후에 pop등을 이용해서 값을 빼주어야 한다.
import sys
K, N, F = map(int, sys.stdin.readline().split())
friends = [[] for i in range(N + 1)]
for i in range(F):
a, b = map(int, sys.stdin.readline().split())
friends[a].append(b)
friends[b].append(a)
# 새로 들어온 친구가 들어갈 수 있는지 확인하는 함수이다.
# 리스트에 첫 번째 인덱스는 0이 있으니 제외하고 시작하자.
def is_friend(plus_friend, member_list):
for q in member_list[1:]:
if plus_friend not in friends[q]:
return False
return True
# cur_cnt는 현재 만들어진 멤버의 수, cur_list는 그 멤버의 번호이다.
def find_friends(cur_cnt, cur_list):
# 멤버를 K명 모으면 함수를 종료한다. (재귀함수의 기저사례)
if cur_cnt == K:
for q in cur_list[1:]:
print(q)
return True
# 순서대로 들어가기 때문에 cur_list에 있는 번호가 가장 큰 멤버는 -1의 인덱스에 있다.
# 대신 빈 리스트에 -1을 부르면 에러가 뜨기 때문에 이 함수 호출 전에 반복문으로 0을 넣어주고 시작한다.
for q in range(cur_list[-1] + 1, N + 1):
if is_friend(q, cur_list):
cur_list.append(q)
if find_friends(cur_cnt + 1, cur_list):
return True
cur_list.pop()
return False
if not find_friends(0, [0]):
print(-1)
이 문제의 전체코드이다.
import sys
K, N, F = map(int, sys.stdin.readline().split())
friend = {i+1: [] for i in range(N)}
for i in range(F):
first, second = map(int, sys.stdin.readline().split())
friend[first].append(second)
friend[second].append(first)
def judge(plus_friend, members):
for per in members:
if per not in friend[plus_friend]:
return False
return True
def backtracking(per_cnt, cur_members):
if per_cnt == K:
for i in cur_members:
print(i)
exit(0)
for i in range(cur_members[-1] + 1, N + 1):
if judge(i, cur_members):
backtracking(per_cnt + 1, cur_members + [i])
for i in range(1, N):
backtracking(1, [i])
print(-1)
전에 풀었던 코드인데 재귀함수를 빠져나올 방법을 찾지 못해서 그냥 exit로 프로그램을 종료해버렸었다.
물론 이렇게 풀어도 되기는 하지만 재귀함수, 백트래킹을 제대로 사용하기 위해 함수를 빠져 나올 수 있는 방법을 생각하며 풀어야겠다.
이 보글게임 문제를 브루트포스, 재귀로 풀 수 있다. (그냥 알고리즘만 구현해보고 채점은 안해봐서 모르겠다... 그냥 참고만)
def hasword(cur_x, cur_y, target_word, visited): # 해당 위치에 찾는 단어가 있는지 확인하는 함수
# 범위를 확인하지 않고 넘어오기 때문에 범위 확인을 가장 먼저 해준다.
if not (0 <= cur_x < 5 and 0 <= cur_y < 5):
return False
if len(target_word) == 0:
return True
if target_word[0] != board[cur_x][cur_y]:
return False
for t in range(8):
go_x = cur_x + dx[t]
go_y = cur_y + dy[t]
if not (0 <= go_x < 5 and 0 <= go_y < 5):
continue
if not visited[go_x][go_y]:
continue
visited[go_x][go_y] = False
if hasword(go_x, go_y, target_word[1:], visited):
return True
visited[go_x][go_y] = True
return False
이 알고리즘에서 가장 중요한 함수이다.
이 문제를 해결하기 위해서는
현재 위치(cur_x, cur_y)에 첫 글자가 있는가?
주위의 8칸 중, 그 위치에서 시작해서 단어의 나머지 글자들을 찾을 수 있는가? 를 알아야 한다.
여기서 현재 위치에 첫 글자가 있으면, 주위 칸으로 가서 두번째 문자부터 시작하면 된다.
이 일을 문자가 없어질 때까지 반복한다. (target_len의 길이 == 0이 종료조건)
이렇게 문제를 부분 문제로 나누어서 풀 수 있어야 한다. (솔직히 떠올리기가 어려운 것 같다.)
이 알고리즘을 구현하면서 visited를 사용해 한 글자를 두 번 이상 사용하지 못하게 만들었다.
N = int(input('단어의 수를 입력 : '))
words = []
for i in range(N):
words.append(list(input().strip()))
print('보드를 입력')
board = []
for i in range(5):
board.append(list(input().strip()))
dx = [-1, -1, -1, 1, 1, 1, 0, 0]
dy = [-1, 0, 1, -1, 0, 1, -1, 1]
def hasword(cur_x, cur_y, target_word, visited): # 해당 위치에 찾는 단어가 있는지 확인하는 함수
# 범위를 확인하지 않고 넘어오기 때문에 범위 확인을 가장 먼저 해준다.
if not (0 <= cur_x < 5 and 0 <= cur_y < 5):
return False
if len(target_word) == 0:
return True
if target_word[0] != board[cur_x][cur_y]:
return False
for t in range(8):
go_x = cur_x + dx[t]
go_y = cur_y + dy[t]
if not (0 <= go_x < 5 and 0 <= go_y < 5):
continue
if not visited[go_x][go_y]:
continue
visited[go_x][go_y] = False
if hasword(go_x, go_y, target_word[1:], visited):
return True
visited[go_x][go_y] = True
return False
def solve(target_word):
for q in range(5):
for w in range(5):
visited_list = [[True] * 5 for i in range(5)]
if hasword(q, w, target_word, visited_list):
return True
return False
for i in range(N):
if solve(words[i]):
print(*words[i])
위 함수를 포함한 전체 코드이다.
단어가 많아진다면 트라이를 통해서 더 빠르게 구현할 수 있겠지만 난이도는 많이 높아질 것 같다....
def pick(cur, cur_list):
if cur == n:
print(*cur_list[1:])
return
for i in range(cur_list[-1] + 1, m + 1):
cur_list.append(i)
pick(cur + 1, cur_list)
cur_list.pop(-1)
함수를 사용했고 cur가 현재 선택한 원소의 수, cur_list가 현재 선택한 원소의 배열이다.
여기서 수를 작은 수부터 차례로 넣었기 때문에 다음에 추가할 수는 cur_list[-1]보다 큰 수부터 보면 된다.
(현재 함수에서 추가할 수는 cur_list[-1]보다 1 큰 수 부터 m까지만 보면 된다는 말)
반복문을 이용하여 수를 넣어주고, 그 배열을 바탕으로 함수를 호출하고, 배열에 들어간 수를 다시 빼주고를 반복한다.
브루투포스로 분류하기는 했지만 백트래킹 알고리즘이기도 하다. (코드를 조금만 수정하면 백준 15650의 답이다.)
해당함수를 바탕으로 작성한 전체 코드이다.
함수가 현재 배열에 있는 가장 마지막 값을 기준으로 작동하기 때문에 배열에 0을 넣어주고 시작한다.
출력시에는 1번 인덱스부터 출력할 수 있도록 한다.
# m개 중에서 n개를 고르는 모든 조합을 찾는 알고리즘, 완전탐색
import sys
print('n과 m을 입력 : ', end='')
n, m = map(int, sys.stdin.readline().split())
def pick(cur, cur_list):
if cur == n:
print(*cur_list[1:])
return
for i in range(cur_list[-1] + 1, m + 1):
cur_list.append(i)
pick(cur + 1, cur_list)
cur_list.pop(-1)
pick(0, [0])