우선 입력받은 배열을 바로 정렬하고, 그 배열로 부분집합을 만드는 것까지는 바로 생각이 난다.
하지만 그렇게 만든 부분집합에서 조건으로 걸러야 한다.
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 hansoo(num):
hansoo_list = []
while num > 0:
hansoo_list.append(num % 10)
num //= 10
for t in range(len(hansoo_list) - 2):
if hansoo_list[t+1] - hansoo_list[t] != hansoo_list[t+2] - hansoo_list[t+1]:
return False
return True
우선 해당 수가 한수인지 판별해주는 함수이다.
만약 100 미만의 수가 들어오면 배열의 크기가 2 이하가 되기 때문에 무조건 True가 반환되게 된다.
100 이상의 수가 들어오게 된다면, 해당 수를 모두 쪼개서 배열에 저장한다.
그리고 반복문을 통해 간격이 다른 구간이 있다면 바로 False를 반환한다.
import sys
N = int(sys.stdin.readline())
result = 0
def hansoo(num):
hansoo_list = []
while num > 0:
hansoo_list.append(num % 10)
num //= 10
for t in range(len(hansoo_list) - 2):
if hansoo_list[t+1] - hansoo_list[t] != hansoo_list[t+2] - hansoo_list[t+1]:
return False
return True
for i in range(1, N + 1):
if hansoo(i):
result += 1
print(result)
당연히 해당 좌표를 비우고 간다면 모든 게임판을 채울 수 없게 되고, 이 이외의 블록 종류들은 다른 칸에서 놓는 블록의 모양과 중복이 된다.
게임판을 받았을 때 다음으로 채워야 하는 좌표를 반환해주는 함수이다.
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])
위 함수를 포함한 전체 코드이다.
단어가 많아진다면 트라이를 통해서 더 빠르게 구현할 수 있겠지만 난이도는 많이 높아질 것 같다....