본문 바로가기
728x90
반응형

자료구조_알고리즘16

알고리즘) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 작은 문제의 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 -> 일반적으로 탑 다운(하향식)과 바텀 업(상향식) 두가지 방식으로 구성 다이나믹 프로그래밍 -> 동적 계획법 자료구조의 동적 할당과는 다르게 전혀 의미 없이 동적 이라는 수식어가 붙은 경우 동적 할당 => 프로그램이 실행되는 도중에 필요한 메모리를 할당하는 것 다이나믹 프로그래밍의 사용 조건 1. 최적 부분 구조 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제를 해결하면 큰 문제도 해결할 수 있는 경우 2. 중복되는 부분 문제 동일한 작은 문제를 반복적으로 해결하는 경우 대표적으로 피보나치 수열이 있다 1, 1, 2, 3, 5, 8, 13.. 점.. 2021. 6. 8.
알고리즘) 이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 데이터를 탐색하기 위해 앞에서부터 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 -> 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 -> 중간점이 두개인 경우 보통 소수점 이하를 제거하여 낮은 값으로 사용 단계마다 탐색 범위를 2로 나누는 것과 동일하기 때문에 시간 복잡도는 O(logN) 파이썬 이진 탐색 라이브러리 특정 범위에 속하는 데이터 개수 구하기 파라메트릭 서치 => 최적화 문제를 결정 문제로 바꾸어 해결하는 기법 -> 최대한 값을 낮추거나 높일 때 여러번의 결정 문제를 해결하면서 최적 값을 찾는 경우 -> 특정 조건을 만족하는 가장 알맞는 값을 찾는 최적화 문제 -> 일반적으로 이진 탐색으로.. 2021. 6. 6.
알고리즘) 정렬 알고리즘 정렬이란 데이터를 특정 기준에 따라 순서대로 나열하는 것 1. 선택 정렬 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 비교하여 맨 앞의 데이터와 바꾸는 것 -> 가장 작은 데이터를 맨 앞으로 이중 반복문으로 구현 시간복잡도는 O(N^2) 2. 삽입 정렬 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 -> 데이터를 하나씩 선택해 다른 데이터와 하나씩 비교하며 작으면 왼쪽 크면 오른쪽에 위치시킴 선택 정렬에 비해 구현 난이도는 높지만, 더 효율적 시간복잡도는 O(N^2) 현재 데이터가 정렬되어있을수록 시간복잡도는 O(N)에 가까워짐 3. 퀵 정렬 기준 데이터를 설정, 기준보다 큰 데이터와 작은 데이터의 위치를 변경 일반적으로 가장 많이 사용된다 병합 정렬과 함께 대부분.. 2021. 6. 5.
알고리즘) DFS(깊이 우선 탐색), BFS(넓이 우선 탐색) 그래프의 깊은 부분을 우선 탐색하는 알고리즘 -> 스택 자료구조 혹은 재귀함수를 이용 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있으면 해당 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 2번을 더이상 수행할 수 없을 때 까지 반복 인접한 노드에서 어디 부터 방문해야할지는 문제에서 주어진다 방문하지 않은 인접 노드가 여러개일 경우 보통은 번호가 낮은 인접 노드부터 파이썬은 그래프를 표현하기 위해 2차원 배열을 이용 ``` graph = [ [], [2, 3, 8] [1, 7] [1, 4, 5] [3, 5] [3, 4] [7] [2, 6, 8], [1, 7] ] def dfs(graph, v, visited): visited[v] = True prin.. 2021. 6. 4.
728x90
반응형

티스토리툴바