지난 학기들의 기록59 [강의노트] 무방향 그래프 - 1 그래프 - 1 알고리즘에서 정말 중요한 추상 자료형인 그래프를 배워보자 그래프 ADT 그래프 추상 자료형은 정점과 간선 정보쌍을 가지고 있는 자료형이다. 아래 그림을 통해 이해하면, 정점은 공항도시의 이름 간선은 정점사이의 거리를 저장하게 된다. 이때 정점은 vertex 의 V로, 간선은 edge의 E라고 앞으로 칭할 것이다. 그래프는 간선의 방향성에 따라서 방향간선과 무방향 간선으로 구분된다. 아래의 예시는 정점 인천과 LA, 그리고 두 정점을 있는 간선을 보여주고 있다. 첫번째 예시는 간선에 방향이 있고, 두번째 예시는 방향이 없다 이때 방향이 있는 간선을 방향간선 그래프라고 한다. 정점에 방향성이 추가되었으므로 시작 정점을 시점 도착 정점을 종점이라고 부른다. 예시에서는 인천에서 LA로 가는 비행기.. 2021. 11. 5. [강의노트] 해시 테이블 - 2 해시 테이블 - 2 https://man-25-1.tistory.com/177 [강의노트] 해시 테이블 - 1 해시 테이블 - 1 해시 테이블에 대한 강의 내용을 정리한 포스팅입니다. 개인 공부를 위해 작성되는 게시글이니 참고해주세요. 해시테이블 해시테이블은 키 - 주소 매핑에 의해 구현된 사전 ADT man-25-1.tistory.com 위의 게시글에 이어지는 내용입니다. 개방주소법에서의 갱신 이전글에서 개방주소법 알고리즘의 삭제는 조금 복잡한걸 언급했었다 한번 알아보자. 비활성화 전략이라는 개념이 나오는데 이것은 이전에 설명한 삭제에서 생기는 오류를 방지하기 위한 전략이다. findElement메소드를 보면 탐색과정에서 empty 상태를 탐색의 끝으로 보고 비어있는 셀을 만나면 탐색을 실패한것으로 간.. 2021. 10. 29. [강의노트] 해시 테이블 - 1 해시 테이블 - 1 해시 테이블에 대한 강의 내용을 정리한 포스팅입니다. 개인 공부를 위해 작성되는 게시글이니 참고해주세요. 해시테이블 해시테이블은 키 - 주소 매핑에 의해 구현된 사전 ADT 이다. (이전에 선형트리 사전, 이진탐색트리 사전을 배웠었다) 키 - 주소 매핑에 대한 예시를 들면 학번을 키 값으로 설정해서 학번에 따라 방 배정을 했을경우 학번 - 방번호에 대한 매핑이 된 것 예시로는 컴파일러의 심볼 테이블, 환경변수들의 레지스트리 등이 있다. 해시테이블 은 버켓 배열 + 해시 함수이다. 위의 예시에서 방 이 버켓 배열이라면, 학번을 3으로 나누었을때 나머지에 따라서 방을 분배하자 와 같은 아이디어가 해시함수에 해당된다고 할 수 있다. 항목들의 키를 주소(즉, 배열 첨자)로 매핑함으로서 1차원.. 2021. 10. 25. [강의노트] 사전ADT를 이용한 선형탐색과 이진탐색 - 3 사전ADT를 이용한 선형탐색과 이진탐색 - 3 사전ADT 3번째 강의노트로 아래의 두 게시글에 이어지는 내용입니다. 사전ADT를 이용한 선형탐색과 이진탐색 - 1 [강의노트] 사전ADT를 이용한 선형탐색과 이진탐색 - 1 사전ADT를 이용한 선형탐색과 이진탐색 - 1 먼저 이전시간까지 다룬 정렬알고리즘들을 복습할 겸 정리해보고, 새로 배울 내용인 사전 ADT를 공부해보자. 비교정렬 알고리즘의 비교 정렬의 안정성 man-25-1.tistory.com 사전ADT를 이용한 선형탐색과 이진탐색 - 2 [강의노트] 사전ADT를 이용한 선형탐색과 이진탐색 - 2 사전ADT를 이용한 선형탐색과 이진탐색 - 2 https://man-25-1.tistory.com/172 [강의노트] 사전ADT를 이용한 선형탐색과 이진탐.. 2021. 10. 13. 이전 1 2 3 4 5 6 ··· 15 다음
