맛대의 블로그

https://www.acmicpc.net/problem/12865 N,K = map(int,input().split()) backpack = [0]*(K+1) for _ in range(N): W,V = map(int,input().split()) for i in range(len(backpack))[::-1]: if backpack[i] and i + W

https://www.acmicpc.net/problem/5639 tree 만들기 tree를 list로 만들어 root를 1번 index, 자식 노드를 1_2, 1_2+1 형식으로 이용하려고 하였음(3번 index의 자식노드는 6번,7번) node가 한쪽으로 쏠려있을 경우 2^n의 index가 필요해 질 수 있음 dictionary를 이용하여 tree 구성 dictionary의 key를 parent, value를 child로 (value[0]은 왼쪽 노드, value[1]은 오른쪽 노드) 후위순회 재귀를 이용하여 해결하려고 하였으나 노드 수가 10,000개 까지 이므로 python의 경우 recursion error 발생 stack을 만들어 값을 저장해 두고 tree의 값을 바꿔가면서 후위순회로 출력되게..

https://www.acmicpc.net/problem/17070 dp 활용 dp 활용을 안하면 시간 초과에서 해결 방법을 모르겠음.. dp에 현재 좌표,파이프 방향 기록 다음에 이동할 위치(ni,nj)에 방향별 방법의 수 = (ni,nj)에 도달 가능한 이전 좌표(i,j)에서 (ni,nj)로 해당 방향 파이프를 두는 방법의 수 합 import sys def solve(): dp = [[[0] * N for _ in range(N)] for __ in range(N)] dp[0][0][1] = 1 for i in range(N): for j in range(2,N): if not arr[i][j] and not arr[i-1][j] and not arr[i][j-1]: dp[1][i][j] = dp[0..

All review you 리뷰를 중심으로 영화를 추천해주는 웹 사이트 처음 해본 프로젝트 느낀점 gitlab을 이용하여 버전관리 branch를 이용하여 각각 push후 merge request, merge 할 때 충돌이 일어날 경우 당황했으나, 좀 많이 겪다 보니 왜 git을 이용하여 버전관리를 하는지 이해하게 됨 코드스타일 Vue에서 코드 작성하는 방법의 차이를 많이 느낌 다른 분이 작성한 코드를 수정하게 될 일이 좀 있었는데, 데이터의 흐름을 파악하는데 꽤 시간이 걸림 server와 client에서 어떻게 자료를 처리해야 하는지에 대한 이해 server(Django)에서 데이터 이런 식으로 보내주면 되겠지 하고 초기 명세서에 작성했으나 많은 부분이 바뀌게 됨 정보 가공을 server에서 할 때 편한..

https://www.acmicpc.net/problem/2638 bfs활용, 고민 했던 사항들 치즈 내부의 공기와 외부의 공기 구분이 필요 N*M 크기에서 최외각은 항상 비어 있는것을 이용하여 (0,0)에서 bfs로 외각 공기만 que에 추가 무한 루프를 방지하기 위해 공기인것을 확인 한 곳은 visited로 방문 체크 공기에 녹아 사라질 치즈를 체크하기 위해 cheeze 변수에 공기에 노출된 격자수를 기록하여 한번에 녹임 녹일 치즈가 없을 경우 ==> 치즈가 없어진 경우 그때까지의 반복 횟수를 return from collections import deque def bfs(): global arr que = deque() que.append((0,0)) cnt = 0 while True: cheeze..

bfs 사용 체크를 벽을 부셨을때, 안부셨을때로 구분 풀이에서는 이동할 좌표 visited에 현재 좌표 visited 값 +1을 줬는데 필요 없는 코드, 그냥 방문체크면 충분 from collections import deque def bfs(i,j): if N == 1 and M == 1: return 1 que = deque() que.append((i,j,0)) cnt = 1 while que: cnt +=1 for _ in range(len(que)): ci,cj,b = que.popleft() # ci,cj = 현재 좌표 b = 벽 부순 횟수 for way in range(4): ni,nj = ci+di[way],cj+dj[way] # ni,nj = 이동할 좌표 if ni == N-1 and n..

https://www.acmicpc.net/problem/9465 dp 활용 왼쪽에서부터 찢을지 말지 선택한다고 생각 선택한 지점을 찢을 경우 지금까지의 최대값 = (왼쪽 대각선 한칸 전, 왼쪽으로 두칸 전, 왼쪽 대각선 두칸 전)중 최대값 + 현재 지점의 값 ```python T = int(input()) for tc in range(T): n = int(input()) point = [list(map(int,input().split())) for _ in range(2)] for i in range(1,n): if i == 1: point[0][1] += point[1][0] point[1][1] += point[0][0] else: point[0][i] = max(point[1][i-1],point..

https://www.acmicpc.net/problem/2096 dp 활용 해당 줄을 선택시의 최대,최소값을 dp에 저장 메모리 문제 바로 전의 값만 필요하므로 dp에 현재값,이전값만 저장공간 배치 2로 나눈 나머지연산을 통해 이전값, 현재값 저장 import sys N = int(sys.stdin.readline()) dp = [[[0,0] for _ in range(3)] for __ in range(2)] for i in range(N): temp = list(map(int,sys.stdin.readline().split())) ii = i % 2 for j in range(3): if j == 0: dp[ii][j][0] = max(dp[1-ii][j][0],dp[1-ii][j+1][0])+te..

bfs 활용 순간이동의 경우 0초로 계산 => 숨바꼭질2에서 하던 방식 불가 => visited에 도달 시간 기입 순간이동과 걸을 떄를 따로 반복문 사용 from collections import deque def solve(): if N == K: return 0 visited[N] = 0 que = deque() que.append(N) while que: now = que.popleft() next = now*2 while 0< next

https://www.acmicpc.net/problem/12851 bfs 활용 시간을 줄이기 위해 visited에 방문 체크(먼저 index에 해당하는 숫자에 도달할 경우만 que에 추가하게 하기 위해) 방법의 수도 알아야 하기 떄문에 visited를 한꺼번에 처리 1에서 3이 목표라고 할 때 1에서 2 가는 방법이 2가지인데 한꺼번에 안하면 한가지로 bfs에 들어가기에 from collections import deque def solve(): ans_cnt,ans_way = 0,0 if N==K: print(0) print(1) return visited = [0]*100001 visited[N] = 1 que = deque() que.append(N) cnt = 0 while not ans_cnt..