알고리즘분석 검색 결과
11 개의 검색 결과가 있습니다.
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 3.5. 탐욕 알고리즘 2

위 그림에서 u와 v가 서로 연결되 있는지 어떻게 확인할 수 있을까요? 눈으로 확인하는 것은 굉장한 노력이 필요하지만, 컴퓨터는 같은 집합에 있는지 여부만 확인함으로써 간단하게 알아낼 수 있습니다. 이와 비슷하게 각 웹페이지가 서로 연결되어 있는지, 네트워크가 서로 연결되어 있는지 확인하는 것도 같은 맥락으로 볼 수 있습니다. 이번 포스팅에서는 이전 탐욕 알고리즘 포스팅을 응용하여 u와 v가 연결되어 있는지를 살펴보는 방법에 대해서 알아보도록 하겠습니다. 목차 0. 배경 해결해야 할 내용을 최소한으로 줄여서 문제를 파악해보도록 하겠습니다. 위 사진은 tree 형태로 component를 나타낸 것입니다. (linked list, array로도 표현할 수 있습니다!) 우리가 파악하고 해결 해야 할 문제는 아..

2021. 6. 10. 03:47
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 3. 탐욕 알고리즘

그리디 알고리즘(탐욕적인 알고리즘)은 결정을 해야할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달하는 알고리즘입니다. 이 알고리즘의 맹점은, 그 당시에는 최적이지만 전부 모아서 최종적인 해답을 만들었을 때 그 해답이 최적이라는 보장은 없다는 것입니다. 그래서 이 알고리즘을 사용할 때에는 항상 최적의 해답을 주는 지를 반드시 검증해야합니다. 이 알고리즘의 설계 절차는 다음과 같습니다. 0. 선정 과정 : 현재 상태에서 가장 좋은 해답을 찾아 해답모음에 추가시킨다 1. 적정성점검 : 새로 얻은 해답 모음이 적절한지를 결정한다 2. 해답점검 : 새로 얻은 해답 모음이 최적의 해인지를 결정한다 이론적인 내용에 대해 보다 자세히 알고 싶다면 아래 Greedy Algorit..

2021. 4. 29. 12:59
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 2. 동적계획법

이번 포스팅에서는 동적계획법에 대해서 알아보도록 하겠습니다. 동적계획법은 앞서 배운 분할정복 방법과 반대인 상향식 해결방법(bottom up)입니다. 분할정복식처럼 문제를 나눈 후에 나누어진 부분들을 먼저 풀고, 인덱스를 이용해 작은 문제들의 중복해결을 배제합니다. 그리고 작은 문제의 해결들을 점차 큰 문제의 해결로 확산하는 것이죠. 특히 이전에 풀었던 정보를 저장한다는 것이 가장 중요한 동적계획법의 핵심 내용입니다! 그렇다면 여러 예를 살펴보면서 동적 계획법에 대해서 더 자세히 알아봅시다! 목차 0. 동적계획법 - 이항계수 고등학교때 배운 이항계수를 구하는 방법입니다. nCk라는 공식을 가지고 있는데, 이걸 파이썬으로 구현하면 아래와 같습니다. # 재귀적 방법, 시간복잡도 2*nCk-1 def bin(..

2021. 4. 29. 12:20
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 1. 분할정복법

이번 포스팅에서는 문제를 해결하기 쉽도록 여러 작은 부분으로 나눈 후에 각각 해결하고, 해결된 답안들을 한데 모아서 문제를 해결하는 분할정복법에 대해서 알아보도록 하겠습니다! 목차 0. 분할정복 - 이분탐색 분할정복은 분할 - 정복 - 통합 순으로 진행되는 전형적인 하향식(top-down) 접근방법입니다. 무슨 말인지 파악하기 위해 재귀적 방식으로 만든 간단한 이분탐색을 가져왔습니다. 이분탐색을 분할, 정복, 통합으로 나눠보면 아래와 같습니다. 분할 : 배열을 반으로 나누어서 x가 중앙에 위치한 항목보다 작으면 왼쪽에 위치한 배열 반쪽을 선택하고, 그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택합니다. 정복 : 선택된 반쪽 배열에서 x를 찾습니다. 통합 : X # 찾는 item의 index를 호출 def..

2021. 4. 29. 11:05
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 0.5. 시간복잡도와 공간복잡도

원래는 하나의 포스팅으로 계획했으나, 내용이 너무 길어져서 이렇게 따로 뒷 부분을 분리하게 되었습니다. 이전 시간에 간단한 알고리즘에 대해서 알아봤다면, 이번 시간에는 알고리즘의 성능을 판단하는 시간복잡도와 공간복잡도에 대해서 간단하게 알아보도록 하겠습니다. 목차 0. 알고리즘의 분석 우선 공간복잡도는 입력크기에 따라서 작업공간(메모리)이 얼마나 필요한지를 결정하는 절차입니다. 그리고 시간복잡도는 입력크기에 따라서 단위연산이 몇 번 수행되는지 결정하는 절차입니다. 현대 시대에 와서는 공간은 넉넉하기 떄문에 공간복잡도보다는 시간복잡도에 더 큰 관심을 가지는 경우가 많습니다. 시간복잡도 분석은 보통 단위연산(비교문, 지정문), 혹은 입력크기(배열의 크기, 리스트의 길이, 행과 열의 크기, 트리의 마디와 이음..

2021. 4. 29. 09:24