나는 데이터 구조에서 좋은 온라인 코스를 찾고 있지만 Google은 알고리즘 코스에 대한 결과도 반환한다는 것을 발견했습니다.
이 과정에서는 분할 및 정복 방법, 그래프 알고리즘, 실제 데이터 구조 (힙, 해시 테이블, 검색 트리) , 무작위 알고리즘 등 알고리즘 설계의 몇 가지 기본 원리를 학습
합니다. [출처]
과
이 수업이 끝나면 그래프 및 기타 중요한 데이터 구조 를위한 새로운 알고리즘을 고안 하고
이러한 알고리즘의 효율성을 평가하는 데 필요한 주요 개념을 이해하게됩니다 . [출처]
과
이 과정은 계산 문제의 수학적 모델링에 대한 소개를 제공합니다. 여기에는 이러한 문제를 해결하는 데 사용되는 일반적인 알고리즘, 알고리즘 패러다임 및 데이터 구조가 포함됩니다 . [출처]
내 질문은 : 알고리즘과 데이터 구조가 밀접하게 연결되어 있습니까? 함께 이해해야하거나 하나의 주제가 다른 주제보다 더 근본적입니까?
편집 :이 질문을 끝내기 위해 투표하는 사람들 에게이 질문을 개선하는 이유와 방법을 알려주시겠습니까? 올바른 질문을하는 것은 교육 과정의 일부입니다.
답변
모든 종류의 혼합물이 존재합니다. (실제) 데이터 구조가 필요없는 알고리즘, 알고리즘과 관련이없는 데이터 구조가 있지만 대부분 두 구조가 하나의 패키지로 제공됩니다.
편집 : @Doval이 올바르게 지적했듯이 데이터 구조 자체에는 관련된 작업이 없습니다. 데이터 구조와 알고리즘을 결합하는 작업은 추상 데이터 형식을 형성합니다.
알고리즘이없는 데이터 구조
예를 들어 적절하게 불리는 2 차원 좌표를 저장하기위한 데이터 구조를 고려하자 Point. 포인트에 대해 수행해야 할 알고리즘은 많지 않으며 실제로는 xand의 y값에 대한 컨테이너 일뿐 입니다. 물론이 데이터 구조를 제공하면 모든 종류의 알고리즘을 추가 할 수 있습니다 (거리 계산, 볼록 껍질, 사물).
개별 데이터의 축적 인 많은 데이터 구조를 생각할 수 있습니다. 이것들은 실제로 자주 발생하지만, 좋은 교재는 만들지 않습니다. 일단 이해하면, 단일 데이터 항목을 새로운 데이터 구조에 축적 할 수 있다는 것입니다. 위의 Point예제 다음에 이라는 멋진 데이터 구조를 제공하면 Point3D3 차원 공간과 동일한 작업을 수행 할 수 있습니까?)
(실제) 데이터 구조가없는 알고리즘
“실제”는 모든 흥미로운 알고리즘이 정수 나 부울과 같은 기본 데이터 유형을 필요로하기 때문에이 문맥에서 데이터 구조로 간주하고 싶지 않습니다. 위와 마찬가지로 이러한 알고리즘은 일반적으로 다소 간단한 알고리즘입니다. 특히 데이터 구조에 들어가기 때문에 복잡한 상태가 아닙니다 (다음 섹션 참조).
이러한 알고리즘의 예는 두 숫자의 최대 공약수를 계산하는 것입니다. gcd에 대한 Euklid의 알고리즘은 실제로 두 정수만 보유하고 조작 할 필요가 있습니다.
일이 더 흥미로워지기 시작하면 곧 추상 데이터 유형의 세계로 들어갑니다. 예를 들어, 에라토스테네스의 체는 배열을 기반으로합니다. 배열이 여전히 원시인지 여부에 대해 지금 토론을 할 수 있거나 실제로 정수가 데이터 구조가 아닌지 토론 할 수 있습니다. 어느 쪽이든, 데이터 구조없이 완전히 존재하는 알고리즘은 분리 된 존재를 허용하더라도 다소 지루합니다.
데이터 구조와 결합 된 알고리즘, 일명 추상 데이터 유형
이제 이것들은 흥미로운 것들이지만, 두 가지 다른 이유가 있습니다. 일반적으로 데이터 구조 우선 또는 알고리즘 우선 두 가지 방향으로 접근 할 수 있습니다.
추상 데이터 유형은 데이터 구조 + 알고리즘 / 작업의 조합에 의해 정의되지만, 우리는 종종 그것들 중 하나에 초점을두고 그것들을보고 다른 하나를 인 에이 블러로 간주합니다.
데이터 구조, 알고리즘
사용하기 쉬운 추상 데이터 유형이 있지만 내부적으로 작동하도록 다소 복잡한 알고리즘이 필요합니다. 예를 들어, a HashMap는 사용하기 쉽지만 멋진 해시 함수를 포함하고 내부의 해시 충돌을 처리합니다. 그러나 사용자로서의 관점에서 볼 때 데이터를 보유하고있는 것이 아니라 자신을 위해하는 것이 아닌 것으로 간주합니다.
아래의 마지막 그룹과 달리 이러한 데이터 구조는 사용자를 이러한 알고리즘에 노출시키지 않습니다. HashMap내부 해시 함수를 사용하기 위해이를 알거나 신경 쓸 필요가 없습니다 . (그러나 효과적으로 사용하려면 다음 사항을 알고 싶을 수도 있습니다.)
알고리즘, 데이터 구조
다른 방향은 단순히 사용할 수는 있지만 의도 한대로 작동하도록 내부적으로 데이터 구조가 필요한 알고리즘이 있다는 의미입니다. 예를 들어 BSP (Binary Space Partitioning) 알고리즘을들 수 있습니다.이 알고리즘 Point은 주어진 쿼리 포인트에 가장 가까운 대규모 포인트 세트에서 2 차원 을 간단히 요청할 수 있습니다 . 그러나 실제로 알고리즘을 작성하려면 내부에 트리 구조 (및 거리 계산과 같은 추가 알고리즘)가 필요합니다.
일반적으로이 그룹의 알고리즘은 내부 상태 표현을 위해 관련 데이터 구조를 사용한다고 말할 수 있습니다. 나는이 알고리즘 그룹이 가장 다양하며이 일반적인 체계에 맞는 많은 다른 알고리즘을 찾을 수 있다고 주장한다. 관점에서 볼 때 우리는 그것들이 우리를 위해 무언가를 (f.ex. 정렬)하고 데이터 보유 부분에 대해서는 크게 신경 쓰지 않기 때문에 흥미로운 것으로 간주합니다.
밀접하게 관련된 데이터 구조 및 알고리즘
마지막으로, 데이터 구조가 있습니다. 데이터 구조는 직접적으로 대응하는 알고리즘과 매우 밀접한 관련이 있습니다. 일반적인 예는 이진 트리로, 의미있는 것을 원할 때 트리 워킹 알고리즘의 주제를 심도있게 (폭 우선, 폭 우선, 무엇이든) 강제합니다.
이러한 경우, 결과 추상 데이터 유형에 대한 관점의 초점을 수시로 변경합니다. 때로는 트리 구조에 관심이 있고 몇 분 후에 트리에서 찾기 작업을 실행할 수 있는지에 대해 걱정 한 다음 노드를 삭제하고 구조가 나중에 어떻게 보이는지 궁금해 할 것입니다. 이 모든 것이 위의 다른 섹션에서도 마찬가지이지만, 예를 들어에서 데이터를 저장하거나 데이터를 검색 Map할 때 또는 링크 된 목록을 정렬 할 때 가장 중요하게 생각하는 것은 아닙니다 .
답변
데이터 구조는 종종 알고리즘의 세부 사항에 영향을줍니다. 이 때문에 두 사람은 종종 손을 잡고 간다.
예를 들어 잔디를 자르기위한 알고리즘을 고려하십시오. 잔디를 자르는 방법은 잔디의 실제 구조에 영향을받을 수 있습니다. 조밀하게 포장 된 교외에있는 작은 집에 살면서 잔디밭이 면적이 몇 미터에 불과한 작은 사각형이라면, 트랙터 / 승용 모어 대신 푸시 모어로 잔디를 자르는 것이 좋습니다. 잔디밭에 평평한 초원 면적의 에이커가 많은 경우에는 잔디 깍기 기계와 달리 잔디 깎는 기계를 선호 할 수 있습니다 (모어가 결국 작업을 수행 할 수 있음). 잔디밭이 넓고 평평한 면적이지만 작은 언덕과 여러 개의 나무가있는 토지가있는 경우, 잔디 깍기와 잔디 깍기 또는 다른 잔디를 포함하는 잔디를 자르는 데 더 흥미로운 알고리즘을 개발할 수 있습니다 절단 기술.
궁극적으로 데이터 구조는 알고리즘 개발 방법 (또는 사용할 알고리즘)에 대한 결정에 중대한 영향을 줄 수 있습니다. 이러한 이유로 두 주제는 종종 서로 관련이 있습니다.
그 반대의 경우도 있습니다 : 때때로 우리가 사용하고자하는 알고리즘은 알고리즘을 지원하기 위해 개발 한 데이터 구조에 영향을줍니다 (적어도 컴퓨팅을 시작할 때). 예를 들어 배열 목록에서 연결된 목록의 아이디어로, 결국 빠른 목록을 찾기 위해 정렬 된 목록을 저장하기위한 BST로 이동합니다.