CodingTest/Baekjun Online Judge (111) 썸네일형 리스트형 [ BOJ / 파이썬 ] 11727. 2xN 타일링 2 보호되어 있는 글입니다. [ 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 / 파이썬 ] 12100 2048(Easy) 보호되어 있는 글입니다. [ 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 / 파이썬 ] 9663. N-QUEEN 백트래킹을 효율적으로 풀어내는 것과 배열의 대각선 형태의 접근에 대해서 정리할 수 있는 좋은 문제였다. - 배열 사용해서 방문값을 저장해두기 - - 대각선 - 왼쪽에서 오른쪽으로 내려오는 대각선 칸들은 같은 줄마다 x+y 값이 같다. 오른쪽에서 왼쪽으로 내려오는 대각선 칸들은 같은 줄마다 x-y+n-1 값이 같다. 대각선 개수는 2*n - 1개. 정답코드. 통과. import sys input = sys.stdin.readline def queen(k): global result if k == n: result += 1 return for i in range(n): if not col[i] and not diagLtoR[i+k] and not diagRtoL[k-i+n-1]: col[i] = 1 diag.. [ 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 / 파이썬 ] 2447. 별 찍기 - 11 아 .. 요게 안 되네 진짜 ㅠㅜㅠ 싶어서 꽤 오래 걸렸다. 접근법은 알겠는데 묘하게 구현에서 뻑나서 결국 몇 개월 전 스스로 풀었던 풀이를 보고 완성했다. 이번에 못 해낸 이유는 재귀에서 조건에 만족했을 때 바로 프린팅을 찍으려고 한 점. 재귀 도는 순서상 프린트를 한 번에 하는게 안 된다. 그래서 미리 같은 사이즈의 결과 배열을 만들어두고, 재귀함수를 돌면서 가장 말단에 갔을 때 결과 배열을 업데이트하고 마지막에 완성된 결과물을 한 번에 프린팅해야한다. 해당 정답 코드. import sys input = sys.stdin.readline n = int(input()) template = [['*','*','*'],['*',' ','*'],['*','*','*']] def recursive(x, y, .. [ 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 / 파이썬 ] 1629. 곱셈 간단한 재귀 문제인데, 수학적 개념이 약해 감을 잡기 어려웠다. 나머지에 대한 원리를 이해한 뒤 재귀적으로 코드를 풀어내는 것 자체는 비교적 수월하게 작성했다. 예시의 10, 11, 12 input에 대하여 10^11 % 12 = ?? 10^1 * (10^5 % 12)^2 = 10^1 * (10^1 * (10^2 % 12)^2) = 10^1 * (10^1 * (10 % 12)^2)^2) =.. 요렇게 쪼개 나갔다. 제출 1. 실패 -> 시간초과. getMod를 두 번 부르게 되며 매 연산마다 반으로 나눠 logN으로 나누는 이득을 전혀 못 보게 했다. 그래서 시간초과 남.. def getMod(a, b, c): if b == 1: return a % c return a**(b%2) * getMod(a, .. 이전 1 2 3 4 5 ··· 12 다음 목록 더보기