취업/알고리즘이야23 [개념] 동적 프로그래밍 (동적 계획법) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 하나의 문제를 작은 다누이로 쪼개어 해결, 결괄르 수집 및 병합하여 최종 결론을 만들어냄 특징 - 한번 계산해서 해결한 것은 다시 해결하지 않기 => 계산한 데이터를 저장한다. (리스트 등) "메모이제이션" 문제 특징 조건 1) 최적 부분 구조 : 큰 문제를 작은 문제를 나누기 2) 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결 => 점화식으로 나타낼 수 있어야! (점화식->재귀함수) 문제형태 (키워드) - 최대 구간의 합, shortedst, longedst, most.. 풀이방식 1) top down : 재귀 이용하여 dp 채우기 2) bottom up : 반복(for)로 앞아서 채워 마지막 도출 문제 예시 - 피보나.. 2022. 5. 5. 2차원 리스트에 max를 함부로 쓰지마세요!! 그냥 쓰지마! 합이 최대인 것이 반환됨. 극복방법 https://devbull.xyz/python-2caweon-baeyeolyi-coedaegabs-coesogabs-cajgi/ 2022. 5. 4. [백준] 2178 미로 탐색 # bfs : 최단거리 보장 # bfs : "바로 보드에 저장해버리자 (이동 시 1씩 증가) -> 거기까지 가는데 걸리는 값 개념으로 접근!" # 문제 풀이 from collections import deque # input n,m = list(map(int, input().split())) # 출력 : 지나야하는 최소 칸 수 mymap = [] for i in range(n): mymap.append(list(map(int,list(input())))) # 여기서 약간 err (int -> str) print(mymap[0][0],type(mymap[0][0]) , " 2022. 5. 4. [질문] 2차원 구현 시 x, y 헷갈림 2022. 5. 3. [이론] 동적프로그래밍 동적 프로그래밍 하나의 문제를 작은 단위로 쪼개어 해결하고 결과를 수집 및 병합하여 최종 결론을 만들어내는 일련의 과정 프로그램 해결과정에서 연산의 결괏값을 저장하고 그 이후에 중복된 연산의 저장된 값을 꺼내어 쓸 수 있다. 하위문제가 여러개로 구성된다. dp 라는 일종의 리스트에 데이터를 저장한다. : 메모이제이션 >>>> 점화식!!! → 중복 연산이 안 생기게 한다. 초기화를 -1로도 하는구나 동적 프로그래밍 문제 특징 모든 경우의 수를 파악해서 진행하면, 지수승의 시간 복잡도를 지님 모든 경우의 수를 조합하면서 확인하는 과정을 가지는 문제 sort, 이진탐색 → X 키워드 : shortest, longest, minimized ,maximized, least, most, fewest, greates.. 2022. 5. 3. 파이썬 웹 IDE : replit https://replit.com/ 2022. 5. 1. 2차 리스트 깊은복사 yourmap = [i[:] for i in realmap] 2022. 5. 1. bfs/dfs 보호되어 있는 글 입니다. 2022. 4. 22. 반례는 어떻게 만드는거지? 따로 생각을 하나? 2022. 4. 15. dfs, bfs 풀 때 입력이 노드 기준인지, 정점 기준인지 잘 파악하는 게 중요할 듯 양방향인지 단방향인지 잘 파악! 2022. 4. 15. mutable : list, dict 위 두개 빼고는 ok (나머지는 call by value) mutable 객체들은 값의 변경이 일어날떄 주소가 참조하는 값이 모두 변경 이들은 call by reference 하므로, [[]*2] => 이렇게 만들고 각 append 접근 시에 [] 2개의 주소가 같아 [] 2개 모두에 값을 쓴다. a = [[]*2] a[0].append(1) 내 생각 : a => [[1],[]] 실제 결과 : a=> [[1],[1]] // 주소가 같아서 참조 https://dpdpwl.tistory.com/82 2022. 4. 15. 열 다음에 행 접근 열 다음에 행 접근 2022. 4. 13. 이전 1 2 다음
