자료구조8 자료구조 - 해시테이블 (Java, HashMap) 1. 개념해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소로 하여 데이터를 key와 함께 저장하는 자료구조key를 활용하여 value값 조회 가능매우 빠른 평균, 삽입, 삭제, 탐색연산이 제공되는 자료구조 구성- key hash function의 input고유한 값키 값 그대로 저장할 경우 다양한 키의 길이만큼 구성해야하므로 일정한 길이의 해시로 변경함- hash functionkey를 고정된 길이의 해시로 변경해주는 함수로 해시 함수를 거치는 과정을 "hashing"이라고 함서로 다른 key가 같은 hash 값을 같게 되는 경우를 해시 충돌이라고 하며, 이 충돌이 적을 수록 좋은 해시함수라고 할 수 있음- value저장소에 저장되는 값- hash table해시함수를 사용하여 해시값으로 매.. 2024. 5. 24. 자료구조 - 한방향 연결리스트, 양방향 연결리스트 1. 연결리스트1) 개념자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하나의 전체적인 자료구조를 이룸.링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않음자료의 크기를 동적으로 조절해 메모리의 효율적인 사용 가능.(추가 삭제 빠름)2) 노드연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위- 구성요소데이터 필드 : 원소의 값링크 필드 : 다음 노드의 주소 ( 마지막 노드는 링크 값을 null로 가짐)- 헤드 : 리스트의 처음 노드를 가리키는 레퍼런스 2. 한방향 연결리스트1) 연결구조노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가짐헤드가 가장 앞의 노드를 .. 2024. 5. 24. (자료구조 & 알고리즘 정리) 트리(Tree) (2023.06.13) 1. 트리 개념 1) 비선형 자료구조 2) 원소들 간에 1:n관계를 가지는 자료구조 3) 상위 원소에서 하위 원소로 내려가면서 확장되는 트리 모양의 자료구조 => 루트노드만 접근할 수 있으면 트리의 모든 노드들을 다 탐색할 수 있게 됨. 4) 용어 노드 : 트리의 원소 트리는 한 개 이상의 노드로 이루어진 유한집합이며 다음 조건을 만족 노드 중 최상위 노드를 루트라 함 나머지 노드들은 분리집합으로 분리 가능 위의 분리집합들은 다시 하나의 트리가 됨(재귀적 정의), 루트의 부트리(subtree)라고 함 간선 : 노드와 노드를 연결하는 선, 부모 노드와 자식 노드를 연결 루트 노드 : 트리의 시작 노드인 최상위 노드(트리 전체 탐색 시 루트노드부터 탐색) 형제 노드 : 같은 부모 노드의 자식 노드들 조상 노.. 2023. 6. 13. (자료구조 & 알고리즘 정리) 재귀, 완전탐색, 순열, 조합, 부분집합 정리(2023.06.04) 1. 재귀 1) 개념 - 자기 자신을 다시 호출하는 함수 - 스택에 자료구조가 쌓이는 방식과 동일하게 함수가 쌓여 처리됨. 가장 최근에 호출된 함수가 종료조건(return 혹은 함수 흐름 종료)이 충족되면 함수가 종료되며 가장 상단(최근)에 쌓인 함수가 꺼내져 처리되는 방식을 따름. - 종료 조건 명시 필수. 제대로 명시하지 않을 경우, 함수가 무한히 호출되어 스택 오버플로우 발생될 수 있음. 2) 재귀( vs 반복문) 의 장단점 (1) 장점 가시성이 높음 구현이 쉬움 변수를 많이 만들 필요가 없어짐. (2) 단점 지속적으로 함수를 호출하면서 지역변수, 매개변수, 반환값 모두를 stack에 저장함으로써 선언한 변수만 사용하는 반복문에 비해 메모리를 더 많이 사용. 이는 속도저하로 이어짐. 3) 꼬리재귀 .. 2023. 6. 5. 자료구조 - 큐(Queue), 데크(Deque) 1. 큐(Queue) 1) 개념 - FIFO(First In First Out) 방식 : 은행의 번호표를 생각하면 된다. 먼저 온 데이터가 먼저 나간다. - 삽입(insert) : 스택에서의 삽입을 push라고 부른다면 큐에서는 enqueue라고 부른다. - 삭제(delete) : 큐에서는 dequeue라고 부른다.(데크(deque)와 용어가 똑같지만 큐에서는 삭제를 의미) - enqueue는 value를 큐의 오른쪽에 삽입하고 deque는 가장 왼쪽 값을 삭제 후 리턴한다. - 스택에서는 가장 top의 값과 index가 무엇인지 알아야했던 것과 달리 큐에서는 enqueue를 할 땐, 큐가 현재 어디까지 차 있는지의 index를 알아야 하고 deque를 할 땐 가장 밑에 있는 index(가장 먼저 들어온.. 2022. 11. 24. 자료구조-순차적 자료구조 : 배열, 리스트(2022.09.21) 1. 배열 1) 가장 기본적인 순차적 자료구조. 2) 인덱스(index) : 배열의 각 특정 위치에 있는 값을 나타내는 상수로 맨 처음 값의 index는 '0'으로 시작하여 1씩 증가. 3) 특징 - 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인 형태로 구성된 자료구조 - 메모리 낭비. 인덱스에 따라 값을 유지해서 중간의 데이터가 삭제되어도 빈자리가 남게 된다. - 배열의 크기가 유동적이지 못하다. 처음 지정한 크기보다 적은 데이터가 들어있어도 배열의 크기에는 변동이 없으며, 반대로 처음에 지정한 크기보다 많은 데이터를 넣거나 삽입하려고 할 경우 에러가 발생한다. => 따라서, 접근을 자주 해야하고 개수가 고정적인 데이터의 경우 배열을 사용하는 것이 적합하다. 4) 연산 - 읽기 & 쓰기 배열에서 .. 2022. 9. 24. 이전 1 2 다음
