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

[알고리즘분석] 7.5. 계산복잡도 : 검색 2 (完)

안녕하세요! 코딩하는 경제학도 쏘코입니다. 드디어 이번 포스팅이 알고리즘분석의 마지막 포스팅이 될 것 같습니다. 참 길었습니다 ㅠㅠ 이번 포스팅에서는 해시와 문자열 매칭으로 검색을 구현하는 방법에 대해 알아보도록 하겠습니다. 목차 0. 해싱 만약 키가 주민등록번호라면 해당 번호의 저장소 를 모두 만들기는 굉장히 어렵습니다. 13자리의 숫자를 담아야 하기 때문입니다. 그렇다면 어떻게 효율적으로 인덱스를 관리할 수 있을까요? 이럴 때 사용할 수 있는 방법이 바로 해싱입니다. 0부터 99의 인덱스를 가진 크기가 100인 배열을 만든 후에, 키를 0~99 사이의 값을 가지도록 해시(hash)합니다. 여기서 해시함수는 키를 배열 인덱스값으로 변환하는 함수입니다. 예를 들면 h(key) = key % 100 으로 ..

2021. 6. 16. 09:21
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 7. 계산복잡도 : 검색

알고리즘분석 카테고리의 마지막은 검색의 계산복잡도에 대한 내용이 되겠습니다. 이번 포스팅에서는 검색 방법들의 계산복잡도를 알아보도록 하겠습니다. 목차 0. 검색의 하한 먼저 검색 문제의 정의부터 알아보도록 합시다. 검색 문제는 n개의 키를 가진 배열 S와 어떤 키 x가 주어졌을 때, x = S[i]가 되는 첨자 i를 찾는 것입니다. 만약 x가 배열 S에 없다면 오류로 처리해야하죠. 이전 포스팅에서 배웠던 정렬을 이용해서 배열을 정렬한 후에 이진(이분) 검색 알고리즘을 사용하면 시간복잡도가 W(n) = floor(lg n) + 1이 되어서 매우 효율적인 알고리즘을 만들 수 있습니다. (floor는 내림, ceil은 올림입니다!) 그렇다면 이진 검색보다 더 좋은 알고리즘을 만들 수 있을까요? 정답은 아니다입..

2021. 6. 15. 22:16
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 6.5. 계산복잡도 : 정렬 2

깔끔하게 정렬되어있는 저 펜들도 처음에는 막 흐뜨러져 있었을 수 있습니다. 저 친구들을 올바른 자리에 똑바로 정렬시키는 것도 하나의 알고리즘이라고 할 수 있겠죠? 이전 포스팅에서 O(n^2)의 시간복잡도를 가진 친구들에 대해서 알아봤다면, 이번 포스팅에서는 보다 나은 효율(O(n lg n))을 가진 알고리즘들에 대해서 공부할 예정입니다. 바로 내용으로 넘어가시죠! 목차 0. 합병정렬 합병정렬은 분할정복의 대표적인 예시입니다. 분할정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 뒤 결과를 모아서 원래의 문제를 해결하는 방법을 사용합니다. 합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 만..

2021. 6. 14. 21:49
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 6. 계산복잡도 : 정렬

이번 포스팅의 주제는 계산복잡도, 그 중에서도 정렬의 계산복잡도입니다. 어떤 알고리즘의 효율을 측정할 때는 시간복잡도와 공간복잡도를 생각합니다. 그리고 문제를 풀 때는 두 가지 케이스가 있는데, 더 효율적인 알고리즘을 찾기 위해 노력하는 케이스와 더 효율적인 알고리즘 개발이 불가능하다는 것을 증명하는 케이스가 있습니다. 예를 들면 정렬의 경우 O(n log n)보다 더 좋은 알고리즘을 개발하는 것은 불가능하다는 것이 입증되었습니다. 따라서 조금이라도 개선하기 위해서 상수적으로 더 효율적인 알고리즘을 개발하는 쪽으로 연구가 진행되고 있습니다. 그렇다면 현재 우리가 사용하는 정렬들은 어떻게 동작하며 얼마나 효율적인지 궁금해지지 않나요? 이번 포스팅에서는 계산복잡도의 개념부터 각종 정렬들을 뜯어보고 정렬들의 ..

2021. 6. 12. 17:45
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 5. 분기한정법

분기한정법은 이전 되추적 기법에서 사용했던 상태공간트리와 유망한지 여부를 사용합니다. 되추적은 특정 답을 뽑아내기 위한 방법이었다면, 분기한정법은 최적의 해를 구하는 문제에 사용할 수 있는 방법입니다. 위 사진은 최소화 분기한정법의 대표 사진입니다. 만약 저 팻말이 최소 트래킹 코스 거리를 나타낸다면 (실제 거리 >= 팻말 표시) A를 트래킹했을 때 거리가 200 미만이라면 B를 트래킹 할 필요 없겠죠? 또한 A와 B의 하한이 지금처럼 나와있다면, 당연히 A를 먼저 트래킹하는 것이 유리하겠죠? 생각보다 어렵지 않습니다. 정말요 ^^ 그렇다면 바로 분기한정법에 대해 알아보러 가시죠! 목차 0. 배낭채우기 분기한정법은 영어로 branch and bound입니다. 가지랑 영역? 정도로 해석할 수 있겠네요. 모..

2021. 6. 11. 17:19
# 학습 내용 정리/알고리즘분석(Python)

[알고리즘분석] 4. 되추적

되추적은 어떤 문제에서 계속 검색해나가다가 검색이 중단되었을 때 다시 돌아오는 알고리즘입니다. 이 알고리즘은 게임, 바둑 등에서 다음 수를 찾을 때 이렇게 하면 안되겠다 싶을때 다시 돌아오는 그런 과정을 말하는 것입니다. 미로를 탈출할 때 한 방향으로 쭉 가다가 막혀있으면 더 이상 그 방향으로는 진행하지 않겠죠? 이것과 정확히 일치하는 방식입니다. 목차 0. 되추적의 기초 먼저 트리를 방문하는 방식에는 여러 가지가 있는데, 대표적으로 preorder, inorder, postorder, level order가 있습니다. preorder, inorder, postorder은 자료구조 시간에 배웠던 내용입니다. 이에 대해서 이전 블로그에 포스팅이 되어있는데, 이쪽으로 옮기지는 않은 상태이기 때문에 간단하게 ..

2021. 6. 10. 18:41