본문 바로가기
320x100

PS84

[CLASS 4]백준 11660번 - 구간 합 구하기 5 11660번 : 구간 합 구하기 5 연산을 딱 한번만 시킨다면 그냥 for문으로 돌아도 상관 없겠지만 연산 횟수 M이 많을 수 있기 때문에 시간을 단축하기 위해 DP로 짜야 한다. 그리고 이 문제는 좀 짜증나는게 dp테이블의 크기를 딱 n으로 만든다면 입력한 인덱스와 1차이가 나는 문제 때문에 머리가 아파진다. 그래서 dp테이블은 1 큰 크기로 만드는게 정신건강에 좋다. 내 코드: # dawitblog.tistory.com from sys import stdin input = stdin.readline n,m = map(int,input().split()) mat = [list(map(int,input().split())) for _ in range(n)] dp = [[0]*(n+1) for _ in r.. 2021. 3. 14.
[CLASS 4]백준 5639번 - 이진 검색 트리 5639번 : 이진 검색 트리 트리를 그냥 주는게 아니라 전위 순회한 결괏값을 주기 때문에 처음에 나는 먼저 트리를 구현->후위 순회를 하는 코드를 작성했다. 내 코드(python 시간 초과): # dawitblog.tistory.com import sys sys.setrecursionlimit(20000) input = sys.stdin.readline # 노드 class Node: def __init__(self,val): self.val = val self.lchild = None self.rchild = None # 트리 class Tree: def __init__(self): self.root = None # 트리에 노드 추가 def add(self,val): if(self.root == Non.. 2021. 3. 12.
[CLASS 4]백준 1991번 - 트리 순회 1991번 : 트리 순회 트리를 순회하는 세 가지 방법을 구현하면 된다. 재귀로 구현하되 탐색 순서(answer문자열에 노드를 추가하는 순서)만 달리해주면 쉽게 구현할 수 있다. 내 코드: # dawitblog.tistory.com from sys import stdin input = stdin.readline dic = {} def preOrder(node): global answer answer += node if dic[node][0] != '.': preOrder(dic[node][0]) if dic[node][1] != '.': preOrder(dic[node][1]) def inOrder(node): global answer if dic[node][0] != '.': inOrder(dic[no.. 2021. 3. 9.
[CLASS 4]백준 1932번 - 정수 삼각형 1932번 : 정수 삼각형 항상 생각하는 것이지만, DP문제는 처음에 풀 때 머리가 참 아픈데 풀고 나면 이걸 왜 못하고 있었을까 라는 생각이 든다. 이 문제는 약간 고정관념이 있으면 풀기 힘든 것 같다. 피라미드를 꼭대기부터 브루트포싱으로 모든 경로를 탐색하며 푼다면 무조건 시간 초과가 뜬다. 내가 바로 처음에 이짓을 했다. 내 코드(시간 초과): # dawitblog.tistory.com from sys import stdin input = stdin.readline def triangle(h,k): if h != n: if h: if k == h: ans[h][k] = ans[h-1][k-1] + t[h][k] elif k == 0: ans[h][k] = ans[h-1][k] + t[h][k] el.. 2021. 3. 4.