본문 바로가기

파이썬

 (70)
[ BOJ / 파이썬 ] 1932. 정수삼각형 오.. 이제 DP는 어느정도 감 잡아가는 느낌이다 이예에 ~ 진짜 몇 달 전에 이 정도 문제도 감이 안 잡혔었는데... 정말 난독증이었던걸까.. 🙄😥 하여간 데이터 배열 자체에 메모제이션으로 해결할 수 있는 간단한 문제였다. 대신 핵심포인트는 해당 열의 첫 값과 끝 값을 예외처리해줘야 함. n = int(input()) triangle = [list(map(int, input().split())) for _ in range(n)] for i in range(1, n): row = triangle[i] triangle[i][0] += triangle[i-1][0] for j in range(1, len(row)-1): triangle[i][j] += max(triangle[i-1][j], triangle[..
[ BOJ / 파이썬 ] 1182.부분수열의 합 백트래킹의 n과 m이나 n queen 문제와는 살짝 차이가 있는 풀이 유형을 익힐 수 있었다. 보통 visited[n] = 1 func(n) visited[n] = 0 이런 식으로 방문여부를 방문append() - 재귀 깊이 + 1 - 방문pop() 요런 느낌이었는데. 이 문제에서는 func( 이 단계에서 실행 X, depth+1) func( 이 단계에서 실행 O, depth+1) 이런 식으로 풀어나갔다. ... 그리고 해당 문제 풀이에서는 정말 기초적인 수학 이해가 필요했다. 크기가 양수인 부분수열일 때만이라는 조건을 그냥 넘기려 했는데 예제 입력처럼 합이 0인 경우 = 그러니까 크기가 0인 경우는 예외처리를 할 필요가 있었던 것이다. 놓치기 쉬운 부분이었다. 풀이. 정답 import sys input..
[ BOJ / 파이썬 ] 15649. N과 M(1) 음 .. ? 의외로 꽤 빨리 풀리고.. 이전 문제 풀이보다 실행시간도 줄었다..! 음 .. 실력이 늘긴 늘었나 진짜. 코드. 통과. import sys input = sys.stdin.readline n, m = map(int, input().split()) visited = [0] * (n+1) result = [] def recur(k): if k == m: print(*result) return for i in range(1, n+1): if not visited[i]: visited[i] = 1 result.append(i) recur(k+1) visited[i] = 0 result.pop() recur(0) 처음에는 현재 방문한 배열(visited) 하나만 두고 k가 일정 깊이 도달했을 때 그냥..
[ BOJ / 파이썬 ] 쿼드트리 재귀 재귀 문제에서 지금 반복해 연습 중인 도형 자르기 문제. 6개월 전 풀었던 풀이를 바탕으로 시간복잡도 줄이기 위해 코드를 정리해나가봤다. 우선, 6개월 전 풀이. # 하.. 처음에 quadtree짤 때, return 받아서 print하게 한 걸, # 수정하면서 같이 안 고쳐줘서 엄한 데서 오류 찾고 있었다. 시간 많이 잡아먹었다:-( import sys input = sys.stdin.readline n = int(input()) board = [list(map(int, input().strip())) for _ in range(n)] def quadtree(x, y, n): if n == 1: print(board[x][y], end="") return canCompress = True for i..
[ BOJ / 파이썬 ] 11729. 하노이 탑 이동 순서 와.. 정말 초등 기초 교구느낌이었던 하노이 탑인데.. 생각해보면 나는 어렸을 때 풀어본 적이 없다. 하하 그래서일까 꽤 버거웠다. 핵심은 반복되는 재귀 구조의 일반항을 찾아내는 것. function(n) 에서 function(n-1)을 이용한 function(n)의 내용을 정리하는 게 핵심이었다. 사실 이게 재귀 문제의 핵심이라 어려운 부분인데.. 그래서 더 끈질기게 이 문제 잡고 늘어지면서 이해를 했던 것 같다. 어떤 문제를 만나도 잘 풀어낼 수 있도록 문제 자체에서 그 방식을 읽어내는 사고를 갖고자 했다. 정말 ! 정말 ! 도움이 많이 됐던 글.. ( 링크 ) 위의 글을 참고해서 풀어낸 코드. 정답. def move(k, start, to): global result result.append((st..
[ BOJ / 파이썬 ] 2178.미로 탐색 BFS BFS문제 중 거리 측정 유형이다. BFS문제의 가장 전형적인 유형이기도 하고, 개인적으로 주구장창 풀었던 스타일이라 술술 써내려갔다. 문제 ( 링크 ) 기본적인 BFS는 방문 여부를 담을 배열을 따로 두지만, 해당 문제에서 밟아야할 공간이 1이므로 1 이상인 경우는 방문했다고 여기며 그 자리에 현재까지의 최단거리를 바로 대체해 넣는 방식으로 코드를 작성했다. 제출 1. 통과 import sys input = sys.stdin.readline from collections import deque def main(): n, m = map(int, input().split()) board = [list(map(int, list(input().strip()))) for _ in range(n)] dx ..
[ BOJ / 파이썬 ] 4949.균형잡힌 세상 1차 풀이 . 실패 import sys input = sys.stdin.readline def checkIsCorrect(text): stack = [] pair = {']':'[', ')':'(' } for t in text: if t == '[' or t =='(': stack.append(t) if t == ']' or t == ')': if not stack: return False if stack and stack[-1] != pair[t]: return False if stack and stack[-1] == pair[t]: stack.pop() if stack: return False else: return True def main(): text = '' while text != '.': t..
[ 백준 ] 18080 알파벳 개수 보호되어 있는 글입니다.
[ BOJ / 파이썬 ] 2178 미로 탐색 / 제출 1 / 첫 제출에 틀렸습니다. 가 나와서 당황했었다. 잘 .. 한 것 같은데 뭐지.. 복사하면서 줄 바꿈 등이 잘 못 옮겨졌었던 것이었습니다. 동일 소스코드를 줄정렬한 것이 아래 코드입니다. / 제출 2 / ### from collections import deque n, m = map(int, input().split()) board = [list(map(int, input())) for _ in range(n)] visited = [[False] * m for _ in range(n)] visited[0][0] = True q = deque([[0, 0]]) # 하 우 상 좌 dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] # n-1, m-1 도착할 때까지 최단거리 whi..
[ BOJ / 파이썬] 1926 그림 / 제출 1 / from collections import deque #세로, 가로 n, m = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(n)] dx = [1, 0, -1, 0] dy = [0, -1, 0, 1] visited = [[False]*m for _ in range(n)] q = deque([]) def bfs(): cnt = 0 while q: cnt += 1 x, y = q.pop() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

티스토리툴바