it 내용 정리

divide-and-conquer은 서로 상관관계가 없는 문제를 해결하는데 적합하다. 반면, dynamic programming은 서로 상관관계가 있는 문제를 해결하는데에 적합하다. dp[i][j] --> 개의 보석을 만큼의 한도의 가방에 넣었을 때 보석의 가치 보석 1개를 넣었을 때 보석의 무게가 100, 가치가 1000이라 했을 때 dp[1][100]=1000 dp[[i][j]=max(dp[i-1][j], LIS 최장 증가 부분 수열 11053 카드 구매하기 11052 포도주 시식 2156 --> 일반항만 생각하면 되는 것이 아니고 한 단계 더 생각해야 한다. 1074 Z 분할과 정복은 문제 자체로 나오기보다는 수단으로 나온다. 4등분하고 Z 형태의 순서로 방문하는 것은 크기와 상관없이 항상 적용되는..

추가 삭제를 양쪽 끝에서 빠른 속도로 할 수 있다. empty deque은 생성자 없이 만들 수 있다. DFS BFS 관련한 여행경로 문제를 풀어보겠다. 1. 주어진 배열을 그래프로 만든다. 2. 큐를 만들고 (출발 노드,[경로]) 삽입 3. 경로 찾는 함수를 작성한다. 4. 가능한 경로를 다 찾은 후 알파벳 순으로 정렬& 첫번째 경로 리턴 pop() 함수는 rightmost element를 제거하는 용도로 사용한다. 파이썬의 리스트에서 지원하는 pop()과 작용방식 같다 deque 는 각 명령을 O(1)으로 지원하는데에 반해, Queue 모듈은 멀티쓰레드 환경을 지원하기 때문에 더 느리다고 하네요 참고로 한가지 더 팁을 드리자면, copy.deepcopy() 또한 매우 느린 작업