알고리즘 [Hash Map]

해시 맵이란?(해시 맵 == 해시테이블)(swift 는 딕셔너리처럼되어있다.) : Key - Value로 값을 저장한다. Key Value 100 변요한 101 박휘순 102 최우식 103 이병헌 키값을 해쉬로 바꿔 메모리를 효율적으로 관리하도록한다. 키값에 대해 해쉬함수를 key%4로 정의 하게된다면 길이 4인 배열에 저장 할 수있다. ex) key 100인 경우, hash 값은 0 (=100%4) 이 되므로 empList[0] = 변요한 출력 하지만 서로 다른 키에 대해 동일한 해시 값이 생성되는 경우에는 충돌이 발생된다. 충돌문제 해결책 1. 열린 어드레싱 방법 충돌이 발생했을때, 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장한다. -선형 조사법 k라는 키에서 충돌 발생 시 조사..

2022.07.23

알고리즘 힙[Heap]

힙에 대한 기본적인 예시) Binary Tree - [O(1)] add : O(log N) delete: O(log N) TOP : O(1) Binary Heap - O(n) 부모 노드가 항상 자식노드보다 커야한다. 삽입하여 값을 변경할 경우 O(log n) 새로운 값을 넣게 되면 부모노드와 비교하고 자리 변동이 일어나기 때문이다. [9, 7, 5, 1, 3] 자식 노드에서 부모 노드로 갈 경우 3이 1로 가려는경우 4 -1 / 2 = 1 (1.5 이지만 내림한다) index -1 / 2 : to parent 부모 노드에서 자식 노드로 갈 경우 2*index + 1 : Lest child 2 * 1 + 1 = 3 (7에서 1로 갈 경우 Index=1 결과값 index3은 1이다) 2*index + 2 :..

2022.07.23

알고리즘[Graph]

그래프 소개 그래프는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조이다. -정점(Vertex) : 자료를 저장하려는 자료의 단위, 노드(Node)라고도 말한다. -간선(Edge) : 정점 사이를 연결하는 선으로 두 정점 쌍(u, v)로 표현함. 그래프는 정점들의 집합 V와 간선들의 집합E를 사용하여 (V, E)로 나타냅니다. - G =(V, E) V = {1, 2, 3, 4, 5} E = {(1,2), (1,5), (2,3), (2,4), (2,5), (3,4), (4,5)} 그래프 용어 -방향성(유향) 간선(Directed edge) 1. 방향을 가진 정점의 쌍(u,v)으로 화살표로 표현하고 단방향을 가리킵니다. 2. 첫번째 정점u는 출발점을 의미하고 두 번째 ..

2022.07.23

알고리즘 트리(Tree)

AVL 트리는 스스로 균형을 잡는 이진 탐색 트리입니다. 트리의 높이가 h일 때 이진 탐색 트리의 시간 복잡도는 O(h)입니다. 한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용하게 됩니다. AVL트리는 다음과 같은 특징을 가집니다. AVL 트리는 이진 탐색 트리의 속성을 가집니다. 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 입니다. 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄입니다. AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 입니다. (트리는 데이터 + 다음 데이터의 주소값을 갖는 형태) 시간 복잡도 트리의 시간..

2022.07.23

알고리즘 링크드 리스트(linked list)

알고리즘 링크드 리스트 -연결 리스트는 데이터와 포인트로 구성된 노드 간의 link을 이용해서 리스트를 구현한 자료구조입니다. 연결 리스트는 배열의 고정크기의 단점을 보완하기 위해 만들어졌으며 배열과 달리 연속적인 메모리 공간에 저장 되어 있지 않기 때문에 연결이 필요합니다. 그림을 설명 한다면..... - Head 는 리스트의 처음을 나타냅니다. - 노드는 데이터와 다음 노드를 가리키는 Next 포인터로 구성돼 있습니다. - 각 노드는 next 포인터를 사용하여 다음 노드와 연결됩니다. - 마지막 노드는 null을 가리켜 리스트의 끝을 나타 냅니다. 시간 복잡도 시작 위치에 대한 삽입/삭제 = O(1) 1.0 마지막 위치에 대한 삽입/삭제 = O(1)-(마지막 요소 위치를 아는경우) 1.1 마지막 위치..

2022.07.23