본문 바로가기
728x90

자료구조

 (10)
[자료구조] 해시 충돌 해결 2021.08.01 - [자료구조] - [자료구조] Hash / Hash Function / Hash Table 에 이어서. 해시 함수가 서로 다른 key를 해시 값으로 변환했음에도 동일한 결과물이 나온 상황이다. 어떤 상황인지 코드와 함께 알아보자. 앞선 포스팅에서 10개의 데이터를 저장할 10개의 Slot을 지닌 해시테이블을 만들었다. let keys = [10, 21, 32, 43, 54, 65, 76, 87, 98, 109] let values = ["홍길동", "이석훈", "강호동", "유재석", "박명수", "이효리", "하창수", "박지원", "김구", "윤봉길"] func getHash(_ key: Int) -> Int { let hashValue = key % hashTable.count..
[자료구조] Hash / Hash Function / Hash Table 해시테이블 은 키(Key)와 값(Value)로 이뤄진 자료구조이다. Swift의 딕셔너리를 떠올리면 쉬운데, 내부 동작은 실제론 배열과 같다. key를 해시함수를 통해 해시 값으로 변환하고 해시테이블에 해시 값과 대응되는 저장공간에 Value를 저장하는 것이다. 용어 키 Key : 고유한 값으로 Hash Function을 통해 HashValue로 변환한다. 해시 Hash : 임의의 값(Value)를 고정된 길이로 변환하는 것 해시함수 Hash Function : Key에 대한 산술 연산을 이용해 데이터가 저장된 공간을 가리키는 Hash Value 를 구한다. 해시 값 Hash Value : Key 를 Hash Function로 연산한 결과. 이를 기반으로 Hash Table에서 해당 Key에 대응 되는 ..
[자료구조] 스택 바로 이전에 공부한 Queue가 FIFO(First In First Out)의 선입선출 방식이라면, 스택은 LIFO(Last In First Out)의 후입선출 방식이다. 스택을 떠올리면 무언가를 쌓는 이미지를 보통 연상하게 되는데 , 요소를 순서대로 밀어넣고(Push) 빼는(Pop) 동작을 수행할 수 있다. Push Push는 아래 그림과 같이 하나 하나 요소를 밀어넣는다. 1 뒤에 2를 push한 후 다음 push연산이 발생하는 위치는 2의 뒤가 되겠다. 이렇게 항상 마지막 요소에서 연산이 일어나는것이 Stack의 특징이다. Pop 그림으로 본다면 간단하지 그지없다. 위에서 Push가 하나하나 요소를 밀어넣었다면 이번에는 반대로 하나씩 끄집어 내는 연산을 하는것이다. push와 같이 요소를 꺼내는것 ..
[자료구조] 큐-2 (원형 큐) 기존의 선형 큐는 dequeue를 하면 앞 부터 쌓였던 데이터가 빠져나간다. Head는 빠져나간 자리의 다음 데이터를 가리키게 되며 비어있는 자리로는 데이터를 추가 할 수 없게 된다. 굳이 재사용을 하겠다면 dequeue를 하고 비어있는 자리를 메꾸기 위해 뒤 데이터들을 앞쪽으로 당겨야하는 작업이 필요한데 , 그렇게 되면 O(n)만큼의 시간복잡도가 발생하게 된다. 이런 비효율적인 구조를 보안한 것이 바로 원형 큐다. 원형큐의 동작이 어떻게 이뤄지는지 그림으로 보자. 순서는 좌측 상단부터 시작한다. enqueue를 진행하면서 rear는 계속 한 단계 뒤의 공간을 가리키게 된다. dequeue를 진행하면 선형 큐의 방식처럼 head(front)도 한 단계 뒤로 계속 이동한다. 선형 큐와 똑같아 보이지만 de..
[자료구조] 큐-1 이번에 정리해 볼 것은 Queue! iOS개발을 하다보면 DispatchQueue... 와 같은 Queue개념을 사용하는 API들이 존재하는데 , 큐는 선입선출(First In First Out - FIFO) 방식으로 데이터를 순서대로 관리한다. 무슨 말이냐. 데이터를 관리하는 큐 공간에 A-B-C의 데이터를 순서대로 넣었다면, 데이터를 뽑는 순서도 A-B-C가 들어간 순서 그대로를 보장한다는 것이다. 그렇기 때문에 큐는 순서를 보장해야 하는 작업을 해야할 때 주로 사용 하는 자료구조이다. 마치, 마트의 계산대에서 계산하려고 줄을 기다리는 사람들의 모양이랄까. 한 줄로 늘어선 줄은 앞에 선 사람 부터 차례로 계산을 하고 빠져나간다. 큐도 이와 같은 방식으로 동작한다고 생각하면 된다. 큐의 종류 선형 큐와..
[자료구조] 연결리스트-3 (양방향 연결 리스트) 2021.07.12 - [자료구조] - [자료구조] 연결 리스트-1 2021.07.12 - [자료구조] - [자료구조] 연결리스트-2 (추가/삭제)- 에 이은 내용 이전 포스팅의 Remove에서 마지막 노드를 삭제하기 위해 head부터 마지막 노드까지 순차적으로 이동했다. 나중에 정리하겠지만, 이렇게 삭제를 하게 될 경우 remove시도 시 데이터의 갯수만큼 시간복잡도가 증가하기 때문에 빅오 표기법으로 O(n)의 시간복잡도를 갖게 되는 최악의 알고리즘이 된다. 이를 피하기 위해서 검색알고리즘을 사용하는데 지금 우리는 알고리즘을 추가하여 시간복잡도를 줄이기 보다, Head와 마찬가지로 Tail이라는 마지막 노드를 가리키는 변수를 추가하여 마지막 노드를 삭제해보려 한다. 이때 양방향 연결리스트에 대해서 함께..
[자료구조] 연결리스트-2 (추가/삭제) 2021.07.12 - [자료구조] - [자료구조] 연결 리스트-1 에 이은 내용 앞선 포스팅에서 노드를 구성했다면 이번 포스팅에선 노드를 관리하고 추가/삭제가 용이한 연결리스트 클래스를 만들것이다. 노드클래스가 준비되었으니 바로 시작하자. LinkedList클래스를 생성하면 head라는 속성을 추가해준다. 변수명은 조금 달라도 되지만 보통 첫번째 노드를 가리키는 명칭이면 된다. head에는 LinkedList의 첫번째(0번째) 노드를 할당하자. 1. Append class LinkedList { var head: Node? func append(value: Int) { let newNode = Node(data: value) if head == nil { head = newNode } else { va..
[자료구조] 연결 리스트-1 자료구조의 리스트는 순차리스트(배열)과 연결리스트(Linked List)로 나뉜다. 연결리스트는 순차리스트와 달리 삽입/삭제 등 변화에 더욱 편리한 자료구조인데, 이러한 강점은 연결리스트의 각 요소가 어떻게 구성되는지 알면 이해가 된다. 연결리스트의 각 요소를 Node(이하 노드)라고 하는데, 노드는 정보를 담는 데이터와 연결된 다른 노드의 주소(포인터)를 담는다. 그림으로 표현한다면 아래와 같다. Data와 Next Address를 묶어서 하나의 노드라고 한다. Next Address는 위에서 말한 다음 노드의 주소를 담고있다. 언어에 따라서 NextAddress에 타입은 적절한 형태로 바뀔 수 있겠지만 보통의 경우 NextAddress에 할당되는것은 다음으로 연결되어야 할 노드의 주소가 된다. 노드 ..
[자료구조] 배열 데이터를 빈틈없이 나열한 자료구조를 배열(순차리스트)이라고 한다. 배열은 일직성으로 쭈욱 나열된 1차원 배열, 1차원 배열의 각 데이터(요소)에 1차원 배열을 하나 더 붙인 모양의 2차원 배열 입체적인 사각면체로 가로, 세로, 높이에 빈틈없이 데이터를 나열한 3차원 배열 등이 있다. 출처 : https://programfrall.tistory.com/52 데이터를 물리적 주소에 순차적으로 저장하고 인덱스를 갖고 있기 때문에 배열내 각 요소에 바로 접근이 가능하다. 그러므로 데이터 접근이 매우 빠르다는 장점이 있다. 배열은 언어마다 조금씩 메모리에 저장되는 방식이 다르다고는 하지만, 일반적으로 아래와 같은 그림으로 표현한다. 배열의 첫요소 a[0] 의 주소를 알고 있다면 그 뒤로 붙는 연속된 요소들을 알 ..
자료 구조란? 자료구조(DataStructure) 란, 사전적 의미로는 CS(ComputerSience)에서 데이터의 접근 및 수정을 효율적으로 하기 위한 조직/체계 를 의미한다고 한다. 많은 양의 데이터를 관리할 때 그 안에서 공통된 규칙이나 패턴을 찾아 체계적인 메커니즘이 잡혀 있어야 한다. 조금은 추상적일 수 있는 말이지만 예시를 보고 이해해보자. 현실에서의 자료구조 대표적인 현실 자료구조로는 학생들을 관리하는 학교에서 찾아 볼 수 있다. 학교는 수십명에서 수백명에 이르기까지 수많은 학생들을 관리하고 있다. 이때 '홍길동' 이라는 학생을 무작위로 나열된 학생명단에서 찾으려 한다면 매우 어려울게 분명하다. 예를 들어 학생이 1000명의 학교의 무작위로 나열된 학생 명단에서 찾는다고 했을때 최소 1회, 최악의 경우 ..
728x90

티스토리툴바