# ---------- Import ----------
from copy import deepcopy
import sys
input = sys.stdin.readline
# ---------- Function ----------
def Rotate_90_Degree(board):
ret = [[0]*length for _ in range(length)]
for r in range(length):
for c in range(length):
ret[c][length-1-r] = board[r][c]
return ret
def Rotate_270_Degree(board):
ret = [[0]*length for _ in range(length)]
for r in range(length):
for c in range(length):
ret[length-1-c][r] = board[r][c]
return ret
def Reflect(board):
for i in range(length):
board[i] = board[i][::-1]
return board
def LFT(board):
for i in range(length):
line = list(filter(None, board[i]))
for idx in range(len(line)-1):
if not (line[idx] - line[idx+1]):
line[idx] *= 2
line[idx+1] = 0
line = list(filter(None, line))
line += [0] * (length - len(line))
board[i] = line
return board
def UP(board):
board = Rotate_270_Degree(board)
board = LFT(board)
return Rotate_90_Degree(board)
def DN(board):
board = Rotate_90_Degree(board)
board = LFT(board)
return Rotate_270_Degree(board)
def RGT(board):
board = Reflect(board)
board = LFT(board)
return Reflect(board)
def BoardGame2048(board, move_count):
if move_count == 5:
global max_block
max_block = max(max_block, max(map(max, board)))
return
for direct in ["U", "D", "L", "R"]:
copy_board = deepcopy(board)
BoardGame2048(switch[direct](copy_board), move_count+1)
return
# ---------- Main ----------
max_block = 0
switch = {"U":UP, "D":DN, "L":LFT, "R":RGT}
length = int(input())
board = [list(map(int, input().split())) for _ in range(length)]
BoardGame2048(board, 0)
print(max_block)
# ---------- Import ----------
import sys
input = sys.stdin.readline
# ---------- Function ----------
def NonRecursiveDFS(x, y):
global max_move
alphabet = set([(x, y, graph[0][0])])
while alphabet and max_move < 26:
x, y, footprint = alphabet.pop()
for dx, dy in dxy:
nx = x + dx
ny = y + dy
if 0 <= nx < row and 0 <= ny < col\
and graph[nx][ny] not in footprint:
alphabet.add((nx, ny, footprint + graph[nx][ny]))
max_move = max(max_move, len(footprint)+1)
# ---------- Main ----------
row, col = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(row)]
dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
max_move = 1
NonRecursiveDFS(0, 0)
print(max_move)
# ---------- Function ----------
def DFS(x, y, cur_move):
global max_move
max_move = max(max_move, cur_move)
for dx, dy in dxy:
nx = x + dx
ny = y + dy
if 0 <= nx < row and 0 <= ny < col and graph[nx][ny] not in alphabet:
alphabet.add(graph[nx][ny])
DFS(nx, ny, cur_move+1)
alphabet.remove(graph[nx][ny])
# ---------- Main ----------
row, col = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(row)]
alphabet = set()
alphabet.add(graph[0][0])
dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
max_move = 1
DFS(0, 0, 1)
print(max_move)
처음에 작성하고 조금 다듬은 코드이다.
골드 4에 백트래킹, 시간 제한 2초에 정답 비율 29.316%을 보고 시간에 유의해야 겠다 생각했다.
접근법은 이러하다.
우선 지나는 알파벳들의 종류는 중복해서 지나서는 안 된다. 또한 시간에 유의해야 한다.
list로 저장해서 not in list로 확인할 수 있지만, 이건 시간복잡도가 O(n)이 걸린다.
하지만 set은 중복을 피하는 저장이 가능하고 not in set을 사용하면 시간복잡도가 O(1)이다.
이점을 감안하여 처음부터 set() 자료구조를 선택했다.
visited로 간 곳을 확인하려고 했지만, 의미없는 일이었다.
가장 처음에는 (graph[nx][ny] not in alphabet) and (visited[nx][ny] == 0)으로 작성했다.
if max_move == 26 or (row * col) - cur_move <= max_move:
return
26이 아니라 한 가지 조건을 더 넣어주었다.
남아있는 칸((row * col) - cur_move)이 max_move보다 작다면 굳이 더 이동할 필요가 없다.
그러니까, 남아있는 칸을 전부 탐색해도 max_move보다 작으면 탐색의 의미가 없다는 말이다.
그런 생각으로 위의 식을 작성해주었다.
6% 채점까지 더 늘어났다. 더 생각해보자.
if (row * col) - cur_move <= max_move or max_move == 26:
return
생각해보면 26이 되는 경우보다, 가지 못하게 되는 경우가 더 많지 않을까?
이런 생각으로 위의 두 조건식의 순서를 바꿔주었다.
지금 작성하면서 드는 생각이지만, 애초에 저 조건식을 잘못 짰다.
우연히 저 경우에 맞아떨어지면서, 마치 저 식이 맞은 듯한 상황이 된 것이다.
채점할 때도 %가 올라가서 맞나...? 싶었는데 아니다.
어쨌든 8%로 더 높아지긴 했지만, 조금 사고를 바꿀 필요가 있다. 애초에 식도 틀렸고 말이다.
너무 작은 거에 얽매이고 있다. 큰 틀에서 바라봐보자.
현재 DFS를 이용한 백트래킹으로 코드를 구현했고, TLE가 뜬다.
DFS와 백트래킹, 그리고 TLE.
어라? 그럼 비재귀 DFS로 짜면 되지 않나?
alphabet = set([(x, y, graph[0][0])])
생각해보면 갈 수 있는 최대 경우의 수는 26이다.
모든 경로를 저장한다고 가정했을 때, 문자열 26개, 좌표를 나타내는 숫자 2개.
그리고 이런 저장 공간이 26개 있다고 할 때, 계산해보면 1MB도 사용하지 않는다.
정확하게는 680B를 사용한다.
└ Python3에서 list는 기본 56B, 3개의 주소 공간을 할당하는데 각 8B해서 80B다. 80 * 26 = 680
문제 조건의 256MB가 차고 넘칠 정도로 많이 남는다.
# ---------- Function ----------
def NonRecursiveDFS(x, y):
global max_move
alphabet = set([(x, y, graph[0][0])])
while alphabet and max_move < 26:
x, y, footprint = alphabet.pop()
for dx, dy in dxy:
nx = x + dx
ny = y + dy
if 0 <= nx < row and 0 <= ny < col and graph[nx][ny] not in footprint:
alphabet.add((nx, ny, footprint + graph[nx][ny]))
max_move = max(max_move, len(footprint)+1)
그리고 백트래킹으로 값을 넣고 뺀다면, 가장 첫 혹은 마지막 값에만 접근한다.
즉 0번째 값 아니면 -1번째 값이다. 이건 list로 탐색해도 무조건 O(1)이다.
그래서 alphabet에 좌표와 여태껏 이동한 발자취(footprint)를 저장한다.
alphabet이 빌 때까지 계속 돌고, 혹은 max_move가 26이 되는 순간 종료한다.
4방위를 탐색하면서 범위 내에 있고, footprint에 그 값이 없다면,
alphabet에 nx, ny 좌표와 현재 footprint에 graph[nx][ny]를 이은 값을 저장한다.
그리고 max_move를 업데이트한다.
종료 조건문은 따로 작성해주지 않아도 상관없다.
조건에 맞는 모든 구역을 다 돌면 종료하거나(while alphabet), 조기 종료(max_move < 26)한다.
그렇게 맞았다. 문제 풀이에 걸린 시간은 대략 45분 정도 걸렸다.
문제 해결 능력은 올라간다는 느낌이 들기는 하는데 아직도 부족하다.
문제를 잘 푼다는 게 기초가 충분하다는 사실과는 별개니까.
또한, '잘' 푼다지 '빨리' 푼다는 아니다. 코딩 테스트에서는 여유 시간을 생각해서 30분에는 끝내야 한다.
# ---------- Import ----------
from itertools import combinations
import sys
input = sys.stdin.readline
# ---------- Main ----------
makeLength, inputLength = map(int, input().split())
text = input().rstrip().split()
text.sort()
for isRight in list(combinations(text, makeLength)):
aeiou = 0
aeiouNOT = 0
for check in isRight:
if check in ["a", "e", "i", "o", "u"]:
aeiou += 1
else:
aeiouNOT += 1
if aeiou > 0 and aeiouNOT > 1:
print(''.join(isRight))
# ---------- Comment ----------
# 조건: 3글자 이상이고, 모음이 최소 1개 이상
# 따라서 자동으로 자음 2개 이상을 충족하리라 생각
# 하지만 모음 2개, 3개인 경우에는 미충족, 따라서 자음도 세줘야 함
처음 봤을 때, python의 combinations 라이브러리로 해결할 수 있을 것 같았다.
보통 combinations로 푸는 문제들은 백트래킹에 해당하는데, 혹시나 했는데 역시나였다.
가능한 모든 경우의 수를 다 돌아야 하기 때문에 브루트포스 문제도 당연했다.
└ 실은 코테를 준비하다보니 브루트포스 문제가 많이 보여서 연습하려고 브루트포스 카테고리에서 골랐다.
└ 신입의 문제는 불필요한 시간과 메모리 낭비, 즉 더티 코드일 가능성이 높으니 브루트포스를 자주 물어보는 것 같다.
골드 5 문제치고는 쉽다고 생각했다.
그냥 조합해보고 모음이 있는지 없는지 확인만 하면 되는 거 아닌가? 생각했다.
# ---------- Import ----------
from itertools import combinations
import sys
input = sys.stdin.readline
# ---------- Main ----------
makeLength, inputLength = map(int, input().split())
text = input().rstrip().split()
text.sort()
vowels = ["a", "e", "i", "o", "u"]
for v in list(combinations(text, makeLength)):
for check in vowels:
if v in check:
print(''.join(v))
continue
처음에 작성한 코드이다.
모음(vowel) 리스트를 만들어놓고, combinations list와 비교한다.
그리고 join 구문을 활용하여 공백을 제거하여 출력하려고 했다.
if v in check:
^^^^^^^^^^
TypeError: 'in <string>' requires string as left operand, not tuple
TypeError가 발생했다. 코드를 살펴보니 반대로 작성했다.
v가 list에서 확인한 조합들이라, 예를 들면 ["a", "f", "h"] 같은 리스트이다.
check는 vowels의 하나 원소들인 "a", "e", "i" 등이다.
if v in check가 아니라 if check in v가 되어야 했다.
수정을 했음에도 틀렸습니다가 떠서 확인을 해보았다.
한 번씩만 출력을 해야 하는데 여러 번 출력을 했다.
정확하게는 조합한 단어에 들어있는 모음의 개수만큼 출력을 했다.
분명 for 문에서 빠져나오게 했는데...? continue를 썼구나 아하...
그래도 틀렸다. 코드 상으로는 틀린 게 없다고 생각했다.
그래서 문제 조건을 또 빼먹었구나 싶어서 살펴보았다.
최소 한 개의 모음과 최소 두 개의 자음, 그리고 조합하는 최소 문자열의 길이는 3이다.
이 조건은 주의했었지만 크게 신경 쓸 필요가 없다고 생각했다.
왜냐하면 최소 길이가 3일 때, 모음이 1개라도 들어가면 자동으로 나머지는 자음이 2개가 되니까 말이다.
그래서 생각했다.
내 코드는 모음이 1개라도 들어가게 동작하는 코드가 맞나?
정말 최소한 1개만 있도록 확인하는 코드가 맞나?
아니었다. 1개가 있으면 break로 빠져나올 뿐, 1개만 있다고 보장하지는 않는다.
그러니까 모음만 4개가 있어도 출력을 했다는 것이다. 이는 자음 최소 조건을 충족하지 않았다.
조건 하나가 허투루 쓰이지를 않는다.
# ---------- Import ----------
from itertools import combinations
import sys
input = sys.stdin.readline
# ---------- Main ----------
makeLength, inputLength = map(int, input().split())
text = input().rstrip().split()
text.sort()
for isRight in list(combinations(text, makeLength)):
aeiou = 0
aeiouNOT = 0
for check in ["a", "e", "i", "o", "u"]:
if check in isRight:
aeiou += 1
else:
aeiouNOT += 1
if aeiou > 0 and aeiouNOT > 1:
print(''.join(isRight))
vowels라는 변수가 직관적이지 않아서 aeiou로 바꿨다.
aeiou는 모음, aeiouNOT은 자음을 세는 변수이다.
또 틀렸길래 다시 한 번 값을 확인해줬다.
? 왜...? 모음하고 자음값이 이상하지? 가만보니 두 개의 합이 전부 5다.
4가 아니라 5인 이유가 있을텐데...하고 가만보니 for문과 if문의 조건을 잘못 지정해줬다.
5가 왜 튀어나왔을까 하고 봤더니, ["a", "e", "i", "o", "u"]의 길이였다.
