알고리즘3 [알고리즘] 동적 계획법 (Dynamic Programming) 👨🏻🏫 fastcampus 알고리즘/기술면접 완전 정복 올인원패키지 - 이준희 강사님 1. 정의 동적계획법 (DP 라고 많이 부름) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 Memoization 기법을 사용함 Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨 예: 피보나치 수열 분할 정복 문제를 나눌 수 없을 때까지 .. 2022. 9. 8. [알고리즘] 정렬 알고리즘 👨🏼🏫 이준희 강사님 fastcampus(알고리즘 이론) 목록의 요소를 특정 순서대로 넣는 알고리즘, 대개 숫자식 순서와 사전식 순서로 정렬 정렬의 시간 복잡도 1. 버블 정렬 가장 느린 알고리즘 ### 수도코드(sudo) Bubblesort(A) for i from 1 to A.length for j from 0 to A.length -1 if A[j] > A[j+1] swap a[j] with a[j+1] def bubblesort(A): for i in range(1,len(A)): for j in range(0, len(A)-1): if A[j] > A[j+1]: A[j], A[j+1] = A[j+1], A[j] bubblesort([2,3,5,1]) 2. 병합 정렬 ‘존 폰 노이만(John v.. 2022. 9. 7. <공부> [이것이 코딩 테스트다 with 파이썬] 4장 구현 예제 https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2 4장 구현 이론 예제 4-1 [상하좌우] 난이도 ●○○ ㅣ 풀이 시간 15분ㅣ시간 제한 1초ㅣ메모리 제한 128MB 여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1크기의 정사각형으로 나누져 있다. 가장 왼쪽 좌표는 (1,1)이며, 가장 오른쪽 아래 좌표는 (N,N)에 해당한다. 여행가 A는 상,하,좌,우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1,1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다. L:왼쪽으로 한 칸 이동 R:오른쪽으로 한 칸 이동 U:위로 한칸 칸 이동 D:.. 2021. 11. 24. 이전 1 다음
