[ 알고리즘 ]/알고리즘11 [알고리즘] 6. 다이나믹 프로그래밍 /* '이것이 취업을 위한 코딩 테스트다' 책의 저자이신 나동빈 님의 예시와 제가 학교 수업에서 배운 내용을 바탕으로 정리했습니다. */ 1. 다이나믹 프로그래밍 - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과 (작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식 (탑다운 - 하향식, 보텀업 - 상향식)으로 구성된다. - 다이나믹 프로그래밍은 동적 계획법이라고도 부른다. - 일반적인 프로그래밍 분야에서의 동적 (Dynamic)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. - 반면에, 다이나믹 프로그램에서 '다이나믹'은 별다른 의미 없이 사용된.. 2022. 1. 6. [알고리즘] 5. 이진 탐색 /* '이것이 취업을 위한 코딩 테스트다' 책의 저자이신 나동빈 님의 예시와 제가 학교 수업에서 배운 내용을 바탕으로 정리했습니다. */ 1. 이진 탐색 알고리즘 - 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색하는 방법 (순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법) - 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. - 단계마다 탐색 범위를 2로 나누느 것과 동일하므로 연산 횟수는 logN에 비례한다. - 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장한다. def binary_search(start, end, target, array): if start > .. 2022. 1. 4. [알고리즘] 4. 정렬 알고리즘 /* '이것이 취업을 위한 코딩 테스트다' 책의 저자이신 나동빈 님의 예시와 제가 학교 수업에서 배운 내용을 바탕으로 정리했습니다. */ 1. 정렬 알고리즘 - 정렬 (sorting) : 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. - 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 2. 선택 정렬 : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array) - 1): for j in range(i+1, len(array)): if array[i] > array[j]: array[i], arr.. 2022. 1. 3. [알고리즘] 3. BFS & DFS /* '이것이 취업을 위한 코딩 테스트다' 책의 저자이신 나동빈 님의 예시와 제가 학교 수업에서 배운 내용을 바탕으로 정리했습니다. */ 1. 그래프 탐색 알고리즘 - 탐색 (search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 - 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다. - DFS / BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다. 2. 스택 자료구조 - 먼저 들어 온 데이터가 나중에 나가는 형식 (선입후출 - FILO)의 자료구조 - 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. 2-*. 스택 구현 stack = [] stack.append(1) stack.append(2) stack.append(3) stack.append(.. 2022. 1. 3. 이전 1 2 3 다음
