본문 바로가기

Algorithm9

선택 정렬 정렬(sorting) : 데이터를 특정한 기준에 따라 순서대로 나열하는 것일반적으로 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용된다. 선택 정렬처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복매번 가장 작은 것을 선택한다는 의미에서 '선택'정렬 알고리즘이라고 한다.      array = [7,5,9,0,3,1,6,2,4,8]for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스. 맨 처음 시작은 0번째 인덱스로 for j in range(i+1, len(array)): # 처리되지 않은 데이터에서 if array[min_index] > array[j]: min.. 2023. 12. 17.
시간복잡도 시간복잡도시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석시간 복잡도가 높다 == 수행 시간이 길다시간 복잡도가 낮다 == 수행 시간이 짧다공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석공간 복잡도가 높다 == 많은 메모리가 필요하다공간 복잡도가 낮다 == 많은 메모리가 필요하지 않다 가장 빠르게 증가하는 항만 고려하면 된다.(상한)-> 연산 횟수가 3N^3 + 5N^2 + 1000000이라면 O(N^3)으로 표현 - 좋은 것 부터(빠른)O(1) :상수 시간O(logN) : 로그 시간O(N) : 선형 시간O(NlogN) : 로그 선형 시간O(N^2) : 이차 시간O(N^3) : 삼차 시간O(2^n) : 지수 시간O(N!) : 팩토리얼 시간- 나쁜 것 까지(.. 2023. 12. 6.
DFS, BFS :: DFSDepth-First Search깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.(실제로 DFS는 인접한 노드가 여러 개 있을 수 있기 때문에, 어떤 노드부터 방문할지를 결정하기 위한 기준이 필요하다. 방문 기준은 문제가 요구하는 내용에 따라서 조금씩 달라질 수 있는데 보통 번호가 낮은 노드부터 방문한.. 2023. 10. 12.
그리디 알고리즘 그리디(Greedy) 알고리즘 (탐욕 알고리즘)  현재 상황에서 지금 당장 좋은 것만 고르는 방법.매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않음. 부분 최적해는 구하지만 전체 문제에서의 최적의 해는 구하지 못하게 되는 경우가 발생한다. ( 눈 앞의 이익만을 쫓는 선택이 최고의 선택이라고 할 수 없다. 나중에 미칠 영향까지 생각하면서 선택하는 것이 최고의 선택이라고 말할 수 있는 경우가 대부분이다. ) 즉 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠오릴 수 있는 능력을 요구한다.그리디 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선.. 2023. 10. 6.

티스토리툴바