코테 (70) 썸네일형 리스트형 [ BOJ / 파이썬 ] 14501.퇴사 공부의 참맛을 느껴가는 중... 아 기분 좋다 진짜 ..🤸♀️ 해당 문제는 현재 한국 코테 바이블 이코테에 수록되어 있는 문제인데 대학 다니면서 처음 코딩테스트에 대해 접한 초반에 풀어보고 진짜 이해가 도통 되지 않아 좌절했던 문제다. 풀이가 이해된 뒤에도 뒤에서부터 인덱스를 접근해야만 이 문제를 풀 수 있나..? 싶어서 계속 의아했었는데 드디어 내 사고방식에 근거해서 이 문제를 풀 수 있었다. n = int(input()) T = [] P = [] total = [0] * (n+1) for i in range(n): time, price = map(int, input().split()) T.append(time) P.append(price) for i in range(n): if i > 0: tota.. [ BOJ / 파이썬 ] 9461. 파도반 수열 dp 좋다.. 감이 잡히니까 확실히 내 타입 문제란 걸 알겠다. 원래도 규칙성 있는 걸 좋아해서 수열 문제 좋아했는데, DP자체가 일반항 세우는거라 불규칙성 속에서 규칙 찾아내는 게 핵심이라 수열 문제가 많은 것이었다. 그래서 DP가 비교적 난이도가 쉬운 문제도 많이 분포하는 것이었다. 그러니까 DP문제는 사실상 DP테이블을 만드는 자체가 힘든게 아니라 DP테이블, 즉 메모제이션(탑다운 방식)을 차용할 생각만 떠올리면 되는것이고, 그 규칙을 찾아내느냐가 핵심인 경우가 많았다. 물론 내가 문제를 아직 많이 못 접해서 DP테이블을 어렵게 사용하는 걸 모르기 때문에 하는 얘기일 수도 있다. 어렵게 내려면 엄청 어려워질 수 있다고 한다. 뭐 이거야 계속 하다보면 늘겠지.. 하여간 해당 문제는 이게 수열이라는걸 .. [ 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 / 파이썬 ] 1003. 피보나치 함수 너무 흔한 재귀 함수 문제인 줄 알았는데 시간제한이 빡빡해서 최대값 40을 찍어보니 아 역시.. 어차피 바텀업 느낌으로 가는 문제이고 하위 문제를 상위에서 갖다 쓰는거라 중복을 최소화할 방법을 찾고자 했다. 그냥그냥 DP로 풀 수 있었다! 피보나치 자체가 n >= 2 부터 fibo(n) = fibo(n-1)+fibo(n-2)의 식을 갖고, 3까지 찍어보니 정말 그 아래 값들의 0과 1등장횟수를 각각 더해주면 된다. 처음에는 피보나치 함수 자체에서 해당 테이블을 갱신하려고 했으나, 일단 일반식을 얻어낸 이상 그냥 dp 테이블 정의하고 for문 돌려 착착 순서대로 채우면 되는거였다. tc = int(input()) for testCase in range(tc): result = [0, 0] n = int(i.. [ 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.. [ 백준 ] 18080 알파벳 개수 보호되어 있는 글입니다. [ BOJ / 파이썬 ] 1074 Z / 제출 1 / import sys input = sys.stdin.readline n, r, c = map(int, input().split()) def findOrderZ(n, r, c): if n == 0: return 0 half = 2**(n-1) if r < half and c < half: return findOrderZ(n-1, r, c) if r < half and half 이전 1 2 3 4 ··· 7 다음
