728x90 반응형 알고리즘7 이코테 2021 - 동적 계획법 (Dynamic Programming) Dynamic Programming : 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법> 쉽게 말하면, 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍은 일반적으로 두가지 방식으로 구현할 수 있다.: 탑다운방식(위 → 아래), 보텀업 방식 (아래 → 위) 조건1) 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음 2) 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결 Dynamic : 동적 - 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당DP알고리즘의 대표적인.. 2024. 8. 3. 이코테 2021 - 이진 탐색 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진탐색 >> 정렬된 리스트에서 특정한 데이터를 빠르게 탐색할 수 있도록 하는 알고리즘>> 시작점과 끝점, 중간점을 명시해야 함 EX) 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾기> 중간점의 값이 두개가 될 경우, 소수점 이하를 제거(4.5 → 4)하여 중간점을 설정한다.> 이때, 중간점의 값(8)과 찾고자 하는 값(4)를 비교하여 중간점의 왼쪽 혹은 오른쪽의 값들만 탐색한다.>> 효율 증가 > 왼쪽의 값들을 기준으로 시작/끝 점을 재설정한다. 그러면 중간점도 재설정 되므로 중간점은 2 (1.5 .. 2024. 7. 12. 이코테 2021 - 정렬 정렬 (Sorting) : 데이터를 특정한 기준에 따라 순서대로 나열하는 것일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다데이터의 개수가 적을 때데이터의 개수가 많지만, 데이터의 범위가 특정 범위로 한정되어 있을 때이미 데이터가 거의 정렬되어 있을 때 선택 정렬 : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 EX) 0-9까지 10장의 숫자카드 순서대로 정렬하기 전체 데이터 중 가장 작은 '0'을 선택하여 맨 앞의 데이터 '7'과 자리를 바꾼다. '7'과 자리를 바꾼 '0'을 제외한 나머지 데이터 중에서, 가장 작은 '1'을 선택하여 맨 앞 데이터인 '5'와 자리를 바꾼다. 마찬가지로 이미 정렬이 끝난 '0'과 '1'을 제외한 나.. 2024. 7. 10. 이코테 2021 - DFS & BFS 재귀함수 재귀함수 (Recursive Function) : 자기 자신을 다시 호출하는 함수def recursive_function(): print('재귀함수 호출') recursive_function()recursive_function()> 파이썬에서는 최대 재귀 깊이 제한이 있어, 이를 실행하면 오류메시지가 뜬다.(RecursiveError : maximum recursion depth exceeded while calling a Python object.)> 따라서, 재귀함수를 사용할 때는 재귀 함수의 종료조건을 명시하여 반복문이 끝나도록 해야 한다. Ex) 팩토리얼문제# n! = n * (n-1) * (n-2) * ... * 1def factorial_recursive(n): if n Ex.. 2024. 6. 17. 이전 1 2 다음 728x90 반응형
