어떤 알고리즘 / 데이터 구조를 이름으로 “인식”하고 알아야합니까? [닫은] 사항은 요구하지 않습니다.

나는 자신이 상당히 숙련 된 프로그래머라고 생각합니다. 저는 5 년 넘게 프로그래밍을 해왔습니다. 내 약점은 용어입니다. 나는 스스로를 가르친다. 그래서 프로그램하는 법을 알면서도 컴퓨터 과학의 좀 더 공식적인 측면을 모른다. 그렇다면 이름으로 인식하고 알 수있는 실용적인 알고리즘 / 데이터 구조는 무엇입니까?

알고리즘 구현에 대한 책 권장 사항은 요구하지 않습니다. 구현에 신경 쓰지 않고 알고리즘 / 데이터 구조가 문제에 대한 좋은 해결책이 될 때를 인식하고 싶습니다. 나는 “인식해야 할”알고리즘 / 데이터 구조의 목록을 더 요구하고있다. 예를 들어 다음과 같은 문제에 대한 해결책을 알고 있습니다.

레이블이 0-999 인 로커 세트를 관리합니다. 사람들은 사물함을 빌리러 돌아와서 사물함 열쇠를 돌려주기 위해 돌아옵니다. 어떤 사물함이 무료이며 어떤 사물함을 사용하는지 아는 관리 소프트웨어를 어떻게 구축 하시겠습니까?

해결책은 대기열 또는 스택입니다.

내가 찾고있는 것은 “B-Tree를 사용해야하는 상황-여기에서 사용해야하는 검색 알고리즘”등과 같은 것입니다. 그리고 더 복잡한 (그러나 일반적으로 사용되는) 데이터 구조 / 알고리즘이 작동합니다.

Wikipedia의 데이터 구조 및 알고리즘 목록을 보려고 시도했지만 약간 과잉이라고 생각합니다. 그래서 내가 알아야 할 필수 사항이 무엇인지 더 찾고 있습니다.

답변

객관적인 답변 :

이 질문에 대한 나의 초기 응답은 곧 CS 학생이 되려는 경험적 경험과 CS 분야에서 함께 일하고 싶은 사람들의 유형에 대한 나의 의견에 근거한 것이 었습니다. 실제로 ACM SIGCSE 및 IEEE 컴퓨팅 사회의 주관적인 의견과 관련하여 객관적인 답변이 있습니다. ACM 과 IEEE 기관 은 10 년마다 컴퓨팅 산업의 상태에 대한 전문 지식을 바탕으로 학부 컴퓨터 과학 커리큘럼에 대한 제안을 자세히 설명 하는 공동 출판물 에 협력 하고 있습니다. 자세한 내용은 cs2013.org를 참조하십시오 . 위원회 는 커리큘럼 권장 사항을 나열한 최종 보고서를 발표합니다 .

즉, 나는 여전히 내 목록이 꽤 좋다고 생각합니다.

아래의 원래 답변.

무엇을 알아야합니까?

최저한의

나는 숙련 된 프로그래머가 최소한 컴퓨터 과학에 대한 학부 수준의 지식을 가지고 있어야한다고 생각합니다. 물론, CS는 확고한 커뮤니티 CS가 자리 잡고 있으며 대부분의 전문직의 초점이 좁기 때문에 컴퓨터 과학 의 작은 하위 집합만으로도 많은 직장에서 효과적 일 수 있습니다 . 또한 많은 사람들이 학부 과정 이후에도 전문화 될 것입니다. 그러나 나는 기초 CS 지식에 대한 특권이 아니라고 변명하지 않는다고 생각합니다.

제목 문제에 답하기 위해 학부 CS 학생 (숙련 프로그래머를위한 기초)이 졸업시 알아야 할 사항은 다음과 같습니다.

데이터 구조

  • 머신 데이터 표현
    • 1, 2의 보수 및 관련 산술
    • 단어, 포인터, 부동 소수점
    • 비트 액세스, 시프트 및 조작
  • 연결된 목록
  • 해시 테이블 (맵 또는 사전)
  • 배열
  • 나무
  • 스택
  • 대기열
  • 그래프
  • 데이터베이스

알고리즘

  • 정렬 :
    • 버블 정렬 (나쁜 이유를 알기 위해)
    • 삽입 정렬
    • 정렬 병합
    • 빠른 정렬
    • 기수 스타일 정렬, 카운팅 정렬 및 버킷 정렬
    • 힙 정렬
    • 보고 및 양자 정렬 (=
  • 수색:
    • 선형 검색
    • 이진 검색
    • 깊이 첫 검색
    • 너비 우선 검색
  • 문자열 조작
  • 되풀이
  • 나무 순회
  • 순회 목록
  • 해싱 함수
  • 해시 테이블, 트리, 목록, 스택, 대기열, 배열 및 집합 또는 집합의 구체적인 구현
  • 스케줄링 알고리즘
  • 파일 시스템 탐색 및 조작 ( 아이 노드 또는 동등한 레벨).

디자인 패턴

  • 모듈화
  • 공장
  • 건축업자
  • 하나씩 일어나는 것
  • 개 작자, 번안 자, 제작자
  • 데코레이터
  • 플라이급
  • 관찰자
  • 반복자
  • 상태 머신]
  • 모델 뷰 컨트롤러
  • 스레딩 및 병렬 프로그래밍 패턴

패러다임

  • 피할 수 없는
  • 객체 지향
  • 기능의
  • 선언적
  • 정적 및 동적 프로그래밍
  • 데이터 마크 업

복잡성 이론

  • 복잡성 공간
  • 계산 가능성
  • 일반 상황에 맞는 무료 튜링 머신 언어
  • 정규식
  • 계산 및 기본 조합

을 넘어서

나중에 질문에 대한 내용을 이해하려면 위의 내용을 잘 알고 있다면 주어진 시나리오에 적합한 패턴, 알고리즘 및 데이터 구조를 쉽게 식별 할 수 있어야합니다. 그러나 최상의 솔루션이없는 경우가 많습니다. 때로는 두 가지 악 중 작은 것을 골라야하거나 단순히 똑같이 실행 가능한 두 가지 해결책 중 하나를 선택해야 할 수도 있습니다. 이 때문에 동료들로부터 당신의 선택을 방어 할 수있는 일반적인 지식이 필요합니다.

다음은 알고리즘 및 데이터 구조에 대한 팁입니다.

  • 이진 검색은 정렬 된 데이터에만 사용할 수 있습니다.
  • 기수 스타일 정렬은 훌륭하지만 정렬 된 유한 클래스가있는 경우에만 가능합니다.
  • 나무는 해시 테이블과 같이 거의 모든 것에 좋습니다. 해시 테이블의 기능을 외삽하여 효율성을 높이면서 많은 문제를 해결할 수 있습니다.
  • 배열은 가장 높은 수준의 데이터 구조를 지원하는 데 사용할 수 있습니다. 때때로 “데이터 구조”는 배열의 위치에 액세스하기위한 영리한 수학에 지나지 않습니다.
  • 언어의 선택은 문제를 극복하거나 항해하는 것의 차이 일 수 있습니다.
  • ASCII 테이블과 128 요소 배열은 암시 적 해시 테이블 (=
  • 정규 표현식은 많은 문제를 해결할 수 있지만 HTML 구문 분석 에는 사용할 수 없습니다 .
  • 때로는 데이터 구조가 알고리즘만큼 중요합니다.

위의 내용 중 일부는 머리가없는 것처럼 보일 수도 있고 일부는 모호하게 보일 수도 있습니다. 좀 더 자세하게 설명하고 싶으면 할 수 있습니다. 그러나 내 희망은 “문자열의 모든 문자 발생 횟수를 계산하는 함수 디자인”과 같은보다 구체적인 질문에 직면했을 때 ASCII 테이블과 128 개의 요소 배열에 대해 깔끔한 암시 적 해시를 형성하는 팁을 살펴보십시오. 답을위한 표.

이러한 아이디어를 바탕으로 귀하의 질문에 요약 된 사물함 문제에 대한 답변을 제안하겠습니다.

귀하의 질문에 제기 된 문제에 대한 답변.

이것은 귀하의 질문에 가장 적합한 대답은 아니지만 너무 복잡하지 않은 흥미로운 질문이라고 생각합니다. 그리고 그것은 로커가 비어 있는지 여부를 결정하기 위해 선형 시간이 필요한 대기열 또는 스택 사용의 시간 복잡성을 확실히 극복 할 것입니다.

사물함은 0-999입니다. 이제 고정 된 수의 로커가 있으므로 0-999 범위에서 충돌없이 해싱 함수를 쉽게 구상 할 수 있습니다. 이 함수는 단순히 h (x) = x mod 1000입니다. 이제 [개념적으로] 정수 키와 1000 요소 char 배열의 내용을 값으로 사용하여 해시 테이블을 구성합니다. 고객이 사물함 78을 예약하여 사용하려면 78을 해시 함수에 넣고 (78을 반환) 해당 번호를 배열의 기본 포인터에 추가하여 오프셋 값으로 지정된 위치에 실제 값을 저장합니다 . 마찬가지로 78이 사용 중인지 확인해야하는 경우 해당 위치에 저장된 값을 읽고 참과 비교하여 확인하십시오.

이 솔루션은 이진 트리에 의해 백업 된 우선 순위 큐의 경우 log (n) 시간 저장 및 검색과 달리 조회 및 저장을 위해 일정한 시간에 작동합니다. 설명은 의도적으로 상세하므로 더 높은 개념이 효율적인 알고리즘으로 정리 된 것을 볼 수 있습니다.

사용 가능한 모든 로커를 알아야 할 경우 우선 순위 대기열이 더 좋지 않을까요? 우선 순위 큐에 사용 가능한 로커가 k 개인 경우 모든 로커를 반복하면 k 단계가 수행됩니다. 또한 우선 순위 대기열 구현에 따라 우선 순위 대기열을 다시 작성해야 할 수도 있습니다. k * log (k) : (k <1000) 단계가 필요합니다. 배열 솔루션에서는 1000 개의 요소 배열 만 반복하고 열려있는 배열 만 확인하면됩니다. 사용 가능하거나 사용 된 목록을 구현에 추가하여 k 시간 만 체크인 할 수도 있습니다.

답변

Steven S. Skiena 의 알고리즘 디자인 매뉴얼 은 검색중인 소스와 같습니다. 두 번째 부분은 관련 알고리즘을 검토 할 때 분류 된 문제 목록입니다. 가 웹 버전 .

답변

“해야한다”는 없습니다. A. 기본 복잡성 클래스 (선형, 대수 등)에 익숙해 지십시오. B. B- 트리와 같은 멋진 데이터 구조로 가능한 간단한 배열만으로 무엇이든 할 수 있다는 것을 깨달으십시오. 적절한 구조 / 알고리즘을 선택하는 요령은 성능, 예상 입력 크기 및 구현 복잡성의 균형을 맞추는 것입니다.

그런 다음 상태 머신, 그래프 이론, 볼록 이론 (선형 프로그래밍 등)과 같이 추상적이지만 엄청나게 유용한 것들이 있습니다 (유용성이 즉시 명백하지는 않지만).

답변

MIT 는 알고리즘 소개를 위한 무료 강의 노트, 비디오, 과제 및 시험 자료를 게시 합니다. 강연 제목 덮여 알고리즘 / 데이터 구조 등을 열거한다.

이것은 당신이 알아야 할 것에 대한 동료 검토 합의입니다. 아마도 훌륭한 학습 자료 일 것입니다.

답변