자료구조 기초

자료구조란

• 컴퓨터에서 여러 자료들을 조직적, 체계적으로 저장하는 방법.

• 보통 동일한 자료형을 여런 저장하는 구조를 의미

• 자료구조에 따라 요소들 사이의 관계를 정의하는 규칙이 있음

• 다음 요인에 따라 상황마다 보다 효율적인 자료구조가 존재

  • 데이터에 접근하는 빈도
  • 데이터에 접근하는 방법

자료구조의 효율성

• 효율성은 주로 시간복잡도를 말함
• 공간 복잡도를 포함하는 경우도 있음

• 따라서 빅오 표기법을 주로 사용

• 보통 효율성을 논할 시 하드웨어 최적화를 고려 안한 이론이 전부

  • 대용량 데이터 사용시 그래도 맞음
  • 적은 용량 데이터는 그렇지 않을 수도 있음.

C에서 자료구조를 배우는 이유

• 배열을 제외한 자료구조는 하드웨어 위에서 프로그래머가 만든 개념
• 유수의 석박사들이 만듬

• 우리도 만들줄 알아야함

• 다른 언어에서는 이런 자료구조를 라이브러리로 줘서 직접 구현해가며 배울기회가 적다
• 자칫하면 추상적으로 이해해서 그냥 라이브러리만 쓸 걸 방지
• 포인터 연습하기에도 매우 좋은 기회

자료구조의 시간 복잡도

배열(array)

• 이미 수도 없이 사용함.
• 메모리 한 덩이를 표현하기 위한 가장 간단한 구조
• 여러 자료들을 그 메모리 덩이에 줄줄이 세워놓는 구조

• 각 자료는 색인(index)으로 접근

  • 연속된 메모리니 각 요소의 실제 메모리 상의 위치를 알 수 있음.

  • 위치 = 시작 주소 + sizeof(자료형) * 색인

배열의 삽입 예

• 새로운 데이터 들어올 때마다 기존 요소들이 뒤로 밀림.

• 이 다음에 0번째에 데이터를 넣으면 기존 0,1에 있던 값이 1,2로 이동

마지막 삽입

배열의 삽입

• 배열 맨 뒤에 넣으면 간단히 삽입하고 끝
• 그 외 경우에는 삽입하려는 위치의 요소부터 마지막 요소를 모두 뒤로 한칸 씩 민 뒤에 삽입.

배열의 삭제

뒤에 있던 걸 앞으로 복사해오면서 땡겨온다. 결과적으로는 삭제된 부분부터 전체적으로 한칸씩 앞으로 이동.

• 삭제하는 색인을 기준으로 뒤의 값들을 한칸씩 떙김
• 시간 복잡도 : O(n)

배열의 검색, 배열의 접근

배열의 검색

• 배열 속 요소들을 처음부터 차례로 방문하며, 찾고자 하는 값이 있는 지 확인
  • 있으면 해당 색인 반환
  • 없으면 -1을 반환

• 시간 복잡도 : O(n)

배열의 접근

• 이미 색인을 알고 있다면 곧바로 접근 가능
• 시간 복잡도 : O(n)

스택(stack)

• 자료의 삽입과 삭제에 대한 규칙이 있는 자료구조 중 하나

• 가장 먼저 자료구조에 삽입(push)된 데이터가 제일 마지막에 삭제(pop)됨.

스택을 선입후출 또는 후입선출이라고 함

• 가장 먼저 넣은 값이 가장 나중에 삭제
• 이를 4자로 줄여서 선입 후출(FILO)
• 혹은 가장 나중에 넣은 값이 가장 먼저 삭제되어 후입 선출이라고 한다.(LIFO)

스택은 중간에 있는 자료를 제거할 수 없다. 언제나 맨 위에 있는 자료만 제거가능. 즉 중간에 있는 데이터만 제거가 안됨.

스택 메모리와 개념이 같다.

• 스택 메모리도 같은 개념
• 데이터가 쌓여감에 따라 주소가 감소하므로 반대로 그릴뿐

• 배열로 쉽게 가능
• 그냥 배열의 앞부터 데이터를 추가
• 마지막 요소의 위치를 스택의 제일 위(top)이라고 생각하면 됨.

스택의 삽입

스택의 삽입 예

스택 삽입코드 예시

스택의 삽입

• 보통 푸시(push)라고 함

  • 제일 위에 밀어넣는다고 해서

• 시간 복잡도 : O(1)

스택의 제거

• 비어있냐 아니냐 먼저 검사. 비어있는데 빼면 이상한 일 발생

• 스택에서 뽑아낸다고 해서 pop이라고 함
• 시간 복잡도 : O(1)

스택의 검색

• 시간 복잡도 : O(n)
• 제일 위부터 찾을 떄 까지 뒤져야 함

• 보통 push()와 pop만 허용하므로 임의의 요소에 접근할 방법이 없다.

  • 그럼 검색은..?

전부 다 뽑고 확인 후 다시 넣어야한다.

• 모든 요소 다 제거 후 원상 복구 해야한다.

스택 검색의 시간 복잡도

• 모든 요소 제거 후 다시 원상 복구 해야함
• 그래서 제거에 O(n)+ 복구에 O(n)이 필요
• 따라서 O(2n)이지만 이건 그냥 O(n)이라 말함.

스택의 용도

• 일련의 자료들의 순서를 뒤집는 데 사용

• 왜 뒤집는지

  • 현재 데이터의 순서대로 연산하는 것이 적합하지 않은 경우
• 생각보다 스택이 유용한 곳이 매우 많다.

스택으로 자료순서 뒤집기

• 스택 요소 뽑아서 배열에 저장후 뒤집기

컴퓨터 연산 순서에 맞게 자료 재정리

• 다음과 같은식(문자열로 들어옴)을 평가하는 계산기를 만들면?

2*(4+5) -15 /3

• 이걸 중위 표기법이라 함(infix)
• 사람들에게 매우 익숙
• 그러나 순서대로 읽으면 평가 불가

• 이걸 후위 표기법(postfix)로 바꾸면 컴퓨터로 연산이 쉽다

• 중위 ->후위로 바꾸는 것도 스택으로 가능은 함

• 후위 표기법으로 적힌 식은 간단히 스택 이용해서 계산 가능

계산 로직

1 . 한 글자를 읽는다

2 . 글자 읽는데 성공시

• 피 연산자면 스택에 넣는다
• 연산자면, 피 연산자 둘을 스택에 꺼내 연산자로 계산 후 그 결과를 다시 스택에 넣는다.
• 1로 돌아감

3 . 글자 읽는데 실패시(마지막)

• 스택에서 꺼내면 그게 결과

재귀함수 제거에도 용이함

• 재귀함수는 함수 호출트리를 이용
• 함수는 각 호출마다 새로 스택프레임을 만들어서 중간 결과를 저장
• 따라서 스택 자료구조를 이용하면 꽤 많은 재귀함수를 재귀없이 반복문으로 구현 가능

큐(Queue)

• 스택과 마찬가지로 자료의 삽입과 삭제에 대한 규칙이 있는 자료구조 중 하나

• 가장 먼저 자료구조에 삽입 된 데이터(enqueue)가 제일 처음에 삭제(dequeue)됨.

큐 역시 임의 접근은 안됨

• 언제나 제일 처음에 있는 자료만 제거 가능
• 중간 자료로 임의 접근 안됨

큐의 비 효율적인 구현

• 그냥 배열 사용시 큐를 구현할 수는 있다
• enqueue하면 그냥 제일 뒤에 추가 O(1)

• dequeue하면 그냥 제일 앞에서 삭제 O(n)

근데 큐의 삭제도 O(1)아닌가?

큐의 삭제를 O(1)로 만들려면

• 내부적으로 배열 사용하되, 원형 버퍼(ring buffer)의 개념을 이해하면 가능

  • 어느 위치든 시작과 끝이 될 수 있다.

큐의 삽입

큐 삽입 예

s_front, s_back, s_num_count는 0으로 시작

s_back은 되돌이 표 하는 연산

데이터 삽입하다 보면 보임.

s_front와 s_back이 같은 배열 인덱스에 위치했다. 일직선이지만 원형으로 보면 됨.

s_back에서 집어넣는 걸 판단하고 현재 뺴야하는 위치 바꿈

큐의 삽입

• 보통 enqueue라고 함
  • 줄 제일 뒤에 세운다는 의미
• 시간 복잡도 : O(1)

큐의 삭제

큐의 삭제 예

큐 삭제 예시

5에서 4로 감소

리턴하면 10 반환하니 item도 10

큐의 제거

• dequeue라고 함
  • 앞에서 하나 빼온다
• 시간 복잡도 : O(1)

큐의 검색

• 시간 복잡도 : O(n)
• 제일 처음부터 찾을 떄까지 뒤져야 함
• 스택과 마찬가지로 보통 enqueue, dequeue만 허용하므로, 임의의 요소에 접근할 방법이 없다.

큐도 다 뽑아서 확인해야 한다.

• 모든 요소 다 제거했다가 다시 원상복구 해야됨.

큐 검색의 시간 복잡도

• 스택과 똑같음
• 모든 요소를 다 제거했다가 원상복구 해야함

• 그래서 제거에 O(n)+ 복구하는데 O(n)이 필요

• 따라서 O(2n)이지만, 이건 그냥 O(n)이라고 말함.

큐의 용도

• 현실 세계에서 대기줄이 필요한 경우에 다 가능
• 데이터 유입 속도가 소모속도보다 빠른 경우
• 데이터 제공자의 수가 소비자의 수와 다른 경우
  • 예: 은행 창구는 여럿인데 줄은 한줄로만 설 떄
  • 멀티 쓰레딩에서도 이런 일들을 함
• 입출력 스트림 버퍼링도 같은 개념

연결 리스트, 연결 리스트의 삽입/제거/검색

• 면접시 자료구조 구현하라면 가장 많이 나오는 중 하나가 연결리스트

• 연결리스트, 해시맵, 해시테이블 이 3개가 가장 많이 묻는 질문.

• 기본기도 아님. 당연히 해야하는 것. 실력 좋은 프로그래머라면 당연히 안보고 할 수 있어야 하는 것 들

지금까지 위의 자료구조들

• 여태껏 본 자료구조들은 메모리에서 연속된 저장 방법에 기초한다.

그러나 연결 리스트는 다름

• 여태껏 본 자료구조들은 메모리에서 연속 된 저장방법에 기초
• 연결 리스트는 그런 제약을 깸

연결리스트(linked list)

• 자료들이 메모리에 이렇게 산재해있음
  • 연결 리스트의 각 자료를 노드(node)라 부름

• 자료형이 어떻게 산재할 수 있는지?
  • 동적 메모리 할당으로 필요에 따라 각 노드를 할당.

근데 서로 어떻게 연결하는지

• 그 둘 사이의 선후 관계를 별도로 지정

  • 어떻게? 다음에 오는 노드 메모리의 주소를 기억

  • 어디에? 노드에 있는 포인터 변수에

  • 제일 마지막 노드는 다음에 올 노드가 없으니 널 포인터

• 노드는 서로 가리키는게 있다.

• 앞의 노드(데이터)에서 다음 노드가 있는 것의 주소를 가리킨다. 메모리 상 위치가 어디든 상관 없고 중요한 건 내 데이터의 다음 데이터를 가리키는 포인터가 있다는 점이 중요하다.

• 이 전체를 노드라고 한다. 이 노드 안에 있는것이 데이터.

• 그리고 다음 노드로의 포인터, 다음 노드를 가리키는 포인터, 노드 기반 에디터와 같은 개념

• 처음은 아무도 처음 노드를 가리치지 않으므로 헤드라고 한다.

• 마지막은 아무것도 가리키지 않으므로 널 포인터를 가지낟. 이걸 테일이라고 한다.

연결리스트는 어려울 수 있는 자료구조

• 연결리스트는 매우 훌륭한 면접문제
  • 메모리 관리 능력
  • 이중 포인터 사용 능력
• 여태까지 설레설레 자료구조 봤어도 이건 집중해서 봐야한다.

연결리스트의 삽입

• 이미 삽입할 위치를 알면 O(1)

10 다음 넣고 싶다. 10이 30의 주소(포인터로)를 가리키고 있는데 20으로 얘를 가리키게 한다.

즉 10에 든 주소를 20으로 옮기고 20의 주소를 30으로 가리키게 한다. 그럼 노드의 순서가 변경된 것

삽입할 위치만 알면 포인터 2개만 바꾸면 되니까 O(1)이라는 것.

• 밀고 당기고의 개념이 없다. 포인터로 다음 노드만 가리키면 됨

연결 리스트의 제거

30을 제거하고 싶은데 30을 뿅 제거하는게 아니라 30이 40을 가리키고 있었으니까 내 앞의 애가 30의 다음 애를 가리키게 하면 됨.

즉 30에 들어있던 주소값을 10 여기에 있는 주소값에 대입 시, 원래 30 가리키던 새로운 값이 대입 되니까 40을 가리키게 된다.

그래서 다음 가리키는 애만 누군지 바꿔주는 것으로 10,40,NULL을 알 수 있게 된다.

연결 리스트의 검색

• O(n)
• 제일 첫 노드부터 찾을 때 까지 찾아야 함
  • 보통 이 노드를 헤드라고 부름
• 색인으로 접근 불가능
• 이렇게 찾은 뒤 삽입을 하면 O(1)이 되는 것

만약 찾으려면 색인 0,1,2이런 개념이 있으려면 배열의 주소가 있고 오프셋을 바로 계산할 수 있어야 하는데 이건 불가

• 워낙 메모리가 산재해 있으므로 하나씩 찾아가는 것

그럼 찾는 개념은 뭔가?

35보다(들어가는 값보다) 작은 값이면 다음으로 건너뛰어야 하고, 큰 값을 보면 전 것과 지금 사이에 넣어야 함

어쩄든 먼저 찾는 것은 O(n)

일단 찾는 위치만 결정하면 실제 삽입하는 건 O(1)

• 삽입한 뒤 데이터를 밀고 당기고 하는게 없기 떄문

35를 넣으려면 헤드부터 찾고 30인 헤드면 다음부터 찾은 뒤 40을 찾고 40을 찾았으면 이 전에 넣어야 되는걸 알고 연결 시키면 된다.

그래서 찾는 과정은 O(n)

연결 리스트: 전체 출력 예 & 노드 메모리 해제 예, 헤드 노드

노드는 어떻게 만드나?

노드는 두가지 데이터를 담고 있다.

• 실제 데이터와 다음 노드로의 주소

그래서 구조체 필요 처음은 값 두번쨰는 다음 노드로의 주소(다음 노드 가리키는 포인터)

그리고 이 연결리스트를 출력하려면?

링크드 리스트는 기본적으로 어떤 크기가 잡혀있는 리스트가 아니다.

그렇기 떄문에 이걸 함수로 만들어놔도 데이터는 자유롭게 추가가능하니까 어떤 크기용 전용 함수가 아니라서 전역변수를 쓸 일도 없고 편하다

이건 함수를 많이 만든다. 다음에 이 노드 출력하고 그 다음 것 출력하고, 그다음 노드 출력하고, 그 다음 노드가 널 포인터면 마지막 노드다.

처음부터 끝까지 훑는 반복문. 그래서 p를 만들고 p에 헤드를 대입함.

즉, p로 다음노드 계속 가겠다는 의미(포인터로)

그럼 NULL이면 그냥 끝. NULL이 아니면 출력하라 하고 p->value를 출력.

출력한 뒤 나를 다음 노드로 옮기라는 걸 해줘야 됨.

• p->next로 내 다음 주소를 다시 나한테 대입하라고 지시.

• 그 순간 p는 다음노드를 가리키게 됨

헤드 노드

• 연결 리스트의 첫번쨰 노드를 가리키는 포인터

• 처음 시작할 때 값은 NULL
  • 아직 노드가 하나도 없기 때문
  • 여기다 새로운 노드를 동적 할당해서 대입해 줌

• 처음 시작시 헤드는 아무것도 가리키지 않음.

• 얘 포인터로 포현한 것

note * head = NULL;

• 만약 포인터가 아무것도 가리키지 않으면 사선 그어서 표현

메모리를 동적할당하면 반드시 해야하는 일이 있다. - > free() 추가

destroy()함수 추가

추가도 하고 삭제도 마음 대로 하지만 head를 destroy함수를 만들어서 해줘야한다.

destroy호출하는 순간 헤드로 가서 처음 것 지우고, 두번쨰꺼 지우고 그런식으로 하는 것.

그림은 데이터 3개 삽입해놓은 연결 리스트. 이 데이터 3개. 주소들. 이들이 들어간 메모리는 동적 할당으로 만든 거다라고 가정.

즉, malloc()으로 만들어서 struct 크기 만큼 만든 뒤, 뭔가 한 것.

p에 헤드를 넣는다. 그럼 p라는 변수가 생김. 포인터 변수인데. head.

연결리스트는 가리킨다는 표현밖에 못 씀(주소 직접 쓰면 너무 복잡해지므로)

p를 지운다(메모리 해제). 메모리 지우니까 1을 가리키는 것도 존재하지 않음. 그러나 헤드는 여전히 이 주소를 가리킴.

지워진 애일 뿐이지 더이상 1을 사용하면 안 되는게 전부.

그 다음 줄은 p가 next와 같아짐.

그리고 앞의 과정 반복. p는 뭘 가리키지만 사용 안할거기 떄문에 상관 없고 p,next또 같아지고

그러다 next가 NULL이 되는 곳이 있다.

이제 p를 지워주고 p가 next와 같아짐.

같아지면 p도 NULL이 됨. p가 널이 되면 끝

그럼 헤드는 아직도 엉뚱한 애를 가리킴. 근데 얘는 일단 주소가 복사되서 온 거기도 하고 실제 이 데이터를 호출한 애가 헤드가 어떤 값을 가지고 있었음.

그럼 지운 뒤 호출자에서 헤드를 NULL로 대입해줘서 더 이상 사용 안한 다는 걸 표현하는 게 좀 더 안전하다.

그래서 코드 위에건 destory() 호출 후 헤드에 NULL을 대입하는 구문도 있었다.

연결 리스트: 삽입하기 예

맨 앞에 삽입하는 코드

new_node->next head의 주소는 NULL이라 가정하고 보자 연결리스트라 헤드는 널에서 시작

그리고 새 노드 만듬. 동적할당 node_t만큼의 크기로 만든다.

임시적으로 400이라는 주소에 만든다. 3을 대입하고 포인터로 new_node->next로 다음을 가리킨다.

최종형태

3,5,2,0 순으로 삽입했는데 헤드 위치에 삽입 했기 떄문에.

근데 왜 insert_front()시 이중 포인터를 넣어줬나? 호출시 헤드를 그냥 대입 안해주고 그 헤드의 주소를 넣었나?

헤드도 이미 포인터인데 걔를 왜 주소에 넣었냐는 소리.

만약 이중포인터가 아닌 일중 포인터면 head의 포인터 값 복사해감. 즉 NULL을 복사해가는 것.

그럼 head는 원래 있고 메인함수에. 얘가 가리키고 있던 애를 phead로 복사한 것.

phead는 원래 널이였다가 새로운 요소를 대입하면서 다음을 가리키게 됨. 새 노드를 대입하면서(insert) 다음을 가리켜 감.

그리고 함수 돌면 사라짐.

그리고 헤드는 널인채로 남고 malloc한 것들은 free로 사라짐. 그럼 헤드가 다음 새노드를 못 가리키게 되고 메모리 누수가 발생

그래서 원본을 바꾸라면 값에 의한 복사가 아닌 참조에 의한 복사해야 하므로 이중 포인터.

일중 포인터는 값에 의한 복사라 값을 못 바꾸게 됨.

연결리스트 오름차순 삽입도 유사하다.

연결 리스트: 노드 삭제

삭제하는 코드

head는 다음 노드를 가리키고 있어서 NULL이 아님. 어떤 주소를 가리키고 있음.

그 뒤 while문으로 들어간다. 이게 pp로 간다 그리고 이게 가리키는 것의 값이 똑같은지 본다.

이 pp가 pp에 가고 tmp라는 변수에 주소를 저장한다.

head가 가리키는 거나 tmp가 가리키는 거나 똑같이 되는 것.

이제는 헤드가 2가 아닌 3을 가리키게 됨.

pp가 화살표 따라서 역참조 한다. 화살표 따라가고 next를 가져옴. 그 값을 헤드에 대입해주고, 결과적으로 전에 가리키던게 head가 가리키게 됨. 전에 가리키는 것은 끊어지게 된다.

중간 하나만 지우고 break 후 나오면 됨.

맨 뒤를 지울 떄도 마찬가지

그 전에 tmp만들어서 5를 기억한다. 왜냐면 이걸 기억 안 해두면 못 지우기 떄문.

지울 거니까 밑으로 빼주고 pp로 가서 (화살표 따라가서)지운 후 널이 되버리고 그떄 끊어짐. 이떄 tmp가 없으면 주소가 없으니까 못 지움.

pp가 가리키는 곳을 들어간다, 화살표 따라간다 등을 잘 알아두자.

연결 리스트의 용도

• 스택/큐와 같은 특성(삽입/삭제 방향) 떄문에 자주 쓰는 자료구조는 아님.
• 오히려 길이를 자유롭게 늘이거나 줄이기 떄문에 배열의 한계를 넘으려고 만든 자료구조
• 즉, 최대길이를 미리 특정할 수 없고 삽입/삭제가 빈번할 시 사용

• 오늘날 어플리케이션 프로그램에서 사용빈도는 많이 줄음
• 기본적으로 동적할당 배열을 더 흔히 사용

  • 캐시메모리에 들어갈 정도로 조그마하면 배열 쓰는게 좋긴 함.

  • C#에서 List도 연결리스트가 아니라 동적 할당 배열임
  • 최신 하드웨어 특징 상 배열이 보장하는 훌륭한 메모리 지역성(인접한 메모리를 사용)이 성능에 유리한 경우가 많기 때문
• 하지만 커널 모드 프로그래밍(예: 드라이버)에서는 여전히 많이 사용
  • 커널은 굉장히 빨라야함.
  • 배열은 땅기고 밀고 이러는게 굉장히 번거로움
  • 링크드리스트는 메모리 충분히 잡아두고 이건 잠시 뺴두고 쓸떄 가져오고 이러기가 가능

  • 어디에서 가져오든 다음 포인터 쓰다가 반납시 해제가 아닌 따로 관리해서 다음꺼 포인터 연결하다가 안쓰면 포인터 끊고 이럼. 이게 메모리풀

  • 동적 메모리 할당 안하고 자기 메모리 안에서 재빠르게 사용할 노드 뺴고 넣고 이러는 건 배열보다 빠르기 떄문.

  • 메모리 지역성을 해치지 않으면서도, 충분히 큰 메모리(ex: 4kb)를 미리 할당
  • 필요에 따라 그 메모리를 쪼개 연결리스트의 노드로 사용(예: 메모리풀)
• 참고로 배열다음으로 많이 사용하는 자료형은 해시맵.

연결리스트에서 진화한 것들

• 단일 연결리스트
  • 우리가 살펴본 연결리스트의 형태
  • 다음 노드를 가리키는 포인터만 저장
• 그 전의 노드를 가리키는 포인터도 저장하는 이중 연결리스트도 있다.
• 이중 연결리스트는 보통 head외에 tail 포인터 변수도 가지고 있다.

해시 테이블

• 자료구조 중 가장 중요한 둘 중 하나(하나는 배열, 하나는 해시테이블)

• 여태 자료형과 달리 해시테이블은 잘 사용하면 컴퓨터 공학에서 사용할 수 있는 곳이 매우 많다. 그래서 주니어 개발자들 뽑을 때 해시테이블을 잘 알고 있냐. 실제 구현할 수 있냐로 기본기를 판단하기도 한다.

• 다른언어에선 직접 쓸 일은 없다. 그래도 직접 만들수 있어야만 도움이 된다

배열이 O(n)인 이유나 스택에서도 검색이 O(n)일수 밖에 없는 이유를 알 수 있어야 한다.

삽입삭체는 정해진 위치에서 하니까 O(1)

큐도 마찬가지였고 스택과 큐는 속도 향상보다 데이터를 어떻게 모양을 잡아두느냐 그것에 따른 유용한 용도들, 알고리즘 같은데, 사용할 수 있는게 보임

연결리스트는 중간중간 필요에 따라 노드를 만들었으므로 동적 할당 같은게 많이 필요함.

그래서 삽입과 삭제 위치를 알면 O(1)으로 가능한 특별한 것.

• 근데 해시테이블은 동떨어져 있음.

O(1)인데 최악은 O(n) 최악으로 가는 경우는 별로 없어서 보통으로 생각하긴 함

O(1)이 가능하려면 어떤 메모리 주소에 어떤 데이터가 저장되어 있는지 한방에 알 수 있어야 한다

무작위로 뽑은 10개를 저장하는 법

• 가장 흔하게 했던 건 크기 10인 배열에 차례로 저장시 O(n)으로 가능

이걸 O(1)으로 알 수 있을까(해시테이블을 모른다는 가정 하에)

방법1 . 입력의 최대값을 배열 크기로

• 가장 단순무식한 방법

1 . 입력의 최대값 만큼 긴 배열을 만듬

2 . 배열[입력값]에 값이 있으면1, 없으면 0을 저장

• 즉, 이 경우는 입력값이 배열의 색인

방법 1의 문제

• 입력값이 엄청 크다면?
  • 무작위로 뽑은게 23913456

• 배열의 크기를 무한히 늘릴수도 없다.

  • 2의 32승이면 4기가
  • 비효율의 극치

해시테이블의 크기는 2배 이상인 소수로

• 입력값이 10개면 배열이 좋다.

• 그러나 엄청나게 큰 입력값이면?

  • 크기만큼 배열값 잡으면 제대로 작동 안하고 0~끝까지 안 사용하는 데이터도 많다.
• 즉, 자료(입력)->색인(출력)으로 만드는 함수
• 단 출력값을 찾을 때 반복문 없이 O(1)이어야 한다

방법2의 문제

• 동일한 색인이 들어가는 데이터들이 생김
• 배열의 크기를 충분히 잡고 10이 아닌 20으로 나누면 겹칠 확률이 줄어둠

배열의 크기를 두배로

• 겹치는 색인 아까보다 덜 생기나, 여전히 존재

방법 3의 보완: 가장 좋은 방법 -> 소수도 사용

• 흔히 다음과 같이 하는게 좋다고 말함

1 . 배열의 크기는 최소 2배

2 . 크기에는 소수(prime number)사용

• 소수로 나눠야 동일한 색인이 안 나올 가능성이 높다.

  • 소수를 사용하는 이유는 배열의 크기만큼 나누기를 함. 그러면 어떤수로 나눠야 중복이 나올 가능성이 가장 적게 만들어 주는게 소수

  • 자연에서도 마찬가지 이유 소수가 많이 발견된다.

• 그래도 중복이 아예 없을 수는 없다.

• 그래서 색인시 중복을 줄이고 또 다른 해법을 찾아야 하는데 이 중복 색인을 해결하기 위해서는 뭘 해야하나.

중복 색인 문제의 해결

• 중복일 떄는 어떻게 하나? 덮어쓰면 안 되는데

중복 색인 문제를 해결하는 법

• 나머지 연산으로 구한 색인 위치 이후에 빈 공간을 찾아 저장
• 즉, 색인을 1씩 증가해가며 빈 색인 위치를 찾아 거기에 저장
• 따라서, 더 이상 불 값(1 또는 0)이 아니라 실제 값을 저장해야 한다.

첫번쨰 값, 두번쨰 값 3번쨰값까지 넣었는데 232에서 색인 1에 이미 저장되어있다 그러면 뒤로 가서 저장(차있다면 빈 공간까지 찾아서 저장. 끝까지 가도 없으면 맨 앞으로 돌아와서 다시 탐색)

근데 위 방법은 어느칸이 비어있다는 걸 알아야 한다. 그래서 어떤 칸이 비어있는지 어떻게 아나? 널을 넣어야 한다고 하면 값형, 포인터형 개념 안 잡힌 것.

정수 저장하는데 정수 없다고 널 넣으면 기본기가 없는 것.

정수이기 떄문에 널 못넣는다.

가장 확실한 방법은 똑같은 형태의 배열 만듬. 어떤거 저장했을떄 1, 아니면 0의 플래그 배열 만든다.

두번쨰 방법은 특정한 방법 저장해서 비어있다는 사실을 표시.

널 대신에 배열에서 절대 볼거같지 않은 수 저장. int_min이나 int_max

하나하나 밀면서 int_min이면 비어있다 이런식으로 진행 가능

입력값을 배열에 넣는법

• 배열에서 비어있는 위치를 알아야 함
• 빈 색인 위치에는 INT_MIN이 들어있음
  • 편의상 아래 그림에선 공백으로 표시

위 코드는 해시테이블 안 지워서 도는 것. 그런 전제가 있다는 가정하에 실행되는 것

이 색인부터 시작해서 데이터를 넣겠다. 값이 비면 넣고 어떤값이 들어가 있으면 다음으로

이게 해시테이블

• 위의 예시가 초간단 해시테이블
• 색인 중복이 없으면, 읽기/쓰기 전부 다 O(1)
• 색인 중복이 있으면 최악의 경우 O(N)

또 다른 방법: 연결 리스트를 사용

• 배열 안의 각 요소에 연결리스트를 저장

• 여전히 색인이 겹치는 경우는 있다

  • 그래도 O(N)이 되는 경우가 앞의 방법보다 적다.
  • O표기상 여전히 O(N)
  • 정말 최악은 O(N)

해시란 무엇인가?

• 왜 해시테이블이라 하는거?
  • 해시값을 쓰기 떄문
• 해시 값은 뭔가?

해시값

• 어떤 데이터를 해시함수에 넣어서 나온 결과

해시함수

• 임의의 크기를 가진 데이터를 ‘고정크기’의 값에 대응하게 하는 함수

입력값 있으면 언제나 그 출력에 대응(똑같이) 입력값의 범위는 제한 없음. 입력값 작을수도 있고, 클 수도 있고

해시함수

• 함수니까 입력값이 같으면 출력값은 언제나 같다

• 입력값이 달라도 출력값이 같을 수 있다.
  • 반대로 그 반대의 경우는 성립 안됨.

해시 충돌(hash collision)

• 위 예시 처럼 입력값이 다른데 출력값이 같은 경우를 말함

• 물론 이런일이 없어야 더 좋다

• 범위가 큰 다른 값을 범위가 좀더 작은 값으로 바꾸는 것.
• 이 둘이 다를 때는 다른값이 나오는게 좋고 해시충돌이 적을 수록 좋다.

• 따라서 출력값으로부터 입력값을 찾을 수 있다는 보장이 없다.

  • 매핑: 어떤것 하나를 다른 것 하나에 대응시킨다.(지도같은 개념. 대응 시키는데 1:1대응만 있는거도 아님)

그래서 1이 나왔는데 이 1에 대응하는 입력값을 못 찾을 수도 있다.

이러한 특성 떄문에 보안에 많이 사용. 보안에서는 입력값 다시 찾는게 정말 어려움.

위에서의 %23이런게 해시함수인가?

• 해시함수일수도 아닐수도 있다.

• 그러나 반드시 그렇지는 않음.

좀 더 자세히 설명한 해시값

• 어떤 데이터를 대표하는 값 하나를 내놓으라고 함
• 이렇게 해서 받은 값이 해시값
  • 마치 대한민국의 주민번호같은 존재
  • 사람은 수가 아니지만 주민번호가 그 사람을 대표하는 수
  • 그래서 영어에서는 ID라고 한다.
• 위의 예에선 입력값 그 자체를 해서 해시값이라 볼 수도 있다.
• 그 해시값을 정해진 배열안에 넣으려 %연산 한 것.

정수 하나하나가 데이터의 정체성을 의미하고 그 하나하나가 고유하고 유니크함. 그 자체가 완벽한 해시값이라 할 수 있다.

원칙상 얘들이 문제 없을 수도 있다.

그럼 지금 본건 해시테이블이 아님.

근데 정수값의 경우 두 값이 다르면 ID도 같음 값이 다르면 ID도 다름

그래서 정수값 = ID = 해시 비슷한 아이

그러면 색인으로 쉽게 변환할 수 없는 데이터를 해시테이블에 저장하자

그러면 해시테이블에 저장하기 위해 어떤 연산하는지 구분 잘 됨.

예를들면 문자열 같이 크기를 정할수 없는 데이터.(구조체마냥 데이터 크기 안정해짐). 또는 바이트가 줄줄이 있는거. 아니면 바이트 배열

해시테이블에 문자열 저장하기

• 우리가 할 일: 문자열을 배열 색인으로 전환
• 아까 사용한 연산자 %는 문자열에 사용 불가
• 문자열을 정수로 변환하는 해시 함수가 있어야 한다.

29짜리 버킷이 있으면 그 해시테이블 안에 들어가는 요소수가 있을시, 0부터 29사이(29는 포함 안 하고) 색인을 구하는게 목적.

근데 정수 필요한데 문자열이 5일수도, 5만일수도 있는데? 32비트로 딱 변환하는 함수가 있으면 좋겠다. 그럼 이게 문자열을 길이가 특정할 수 없는 문자열을 딱 길이가 정해진 4바이트, 32비트로 정해진 INT형으로 바꾸고 그 숫자가 나왔다면 어떤 버킷에 들어가는지는 %29연산을 통해 알 수 있다.

• 이게 흔히 말하는 해시함수

해시테이블에 문자열 저장하기-2

• 문자열의 각 요소는 아스키코드 = 정수값
• 정수값이 줄줄이 서 있는걸 잘 합치면 될듯하다

잘 쓰이지 않는 해시함수의 예

• 해시충돌이 빈번해 잘 쓰이지 않음

위의 예를 들어보면 각 알파벳들의 해시코드다

이 방식으로 문자열을 정수로 변환한다.

해시값이 나왔으니 이제 진짜 저장

• 예시 코드 자체가 어떤 값을 더하는 것은 맞다. 여기서 해시 값을 구해야 하는데 그 해시를 구할 수 있는 함수의 포인터를 전달해주면 된다.

• hash_func이라는 함수 있고 이 함수는 문자열 하나 받아서 int를 반환하는 함수
• 그럼 이 int에서 어디 색인위치에 들어가야하는지 나머지연산 해서 저장.
• 해시값에서 해시 색인 구하고, 나머지 연산으로 값 저장.

하지만 O(문자열길이)

• O(1)가 아님
• 해시 함수가 문자열길이만큼 반복 도니 O(문자열 길이)
• 문자열 길이만큼 반복문 도는데 50000길이면 그만큼 돈다.
• 문자열 길이따라 O(n)이 됨
• 근데 20개 길이 정해져있는데 이 경우 20번 이하로 돔 . 이떄는O(n)으로 보긴 어려움

정말 O(1)로 만들고 싶다면?

• 해시함수 한번만 호출하고 그 결과를 기억해둠

• 필요할 때마다 이 변수로 해시 테이블 함수호출

• 위 과정 이후 hash_id로부터 저장할 위치 색인O(1)로 구하기 가능

지금까지 본건 엄밀히 말하면 해시 세트

• 즉, 집합내 어떤 데이터를 중복 없이 저장한게 전부
• 저장할 위치 찾으려 해시함수 쓴것 뿐

• O상(빅오상) 좋은건 연결리스트. 만약 티모 2번 나와도 1번만 저장하고 윤호가 2번나와도 1번만 저장
• 원래 넣으려는 데이터 그냥 넣은 것 뿐. 해시세트라고 한다.
• 해시세트는 저장한 것의 중복이 없다. 근데 저장하는 위치 찾으려고 hash_id사용해서 찾는거일 뿐.
• 일반적으로 해시테이블 할 떄는 해시맵을 보통 의미

해시맵

일반적인 해시테이블의 형태

• 어떤 키에 대응하는 어떤 값을 같이 저장
• 이런 형태를 보통 해시테이블(엄밀히 말하면 해시맵이라 함)이라 한다
  • C#이나 파이썬 같은 딕셔너리가 바로 이것(1:1대응형태)

• 키 : 데이터의 위치를 의미하는 데이터
  • 꼭 정수가 아니어도 됨. 문자열도 가능. 구조체도 가능
• 값 : 실제 저장하는 데이터
  • 키를 가지고 그 위치에 가면 데이터가 나온다.

이 해시테이블에도 충돌이 발생한다.

• 한가지도 아니고 두가지 경우에나 발생한다.

  • 해시충돌 : 키가 다른데 같은 해시값이 나옴
  • 색인충돌 : 해시값이 다른데 같은 색인이 나옴

• 두번쨰는 이미 해결했었다

해시충돌 문제를 해결해야 하나?

• 해시충돌 문제는 사실 해결 안해도 된다.

• 색인 충돌 문제 해법으로 같이 풀림.

해시충돌을 방지할 수 있다면?

• char*를 복사해서 키로 저장할 이유가 없다

• 해시값인 정수형(int)만 저장해도 된다.

• char* 저장하려고 동적 메모리 할당 안해도 된다.
  • 동적 메모리 할당은 느림. 안할수 있다면 좋다.

훌륭한 해시함수란

• 어떠한 경우에도 고정된 크기의 값으로 변환 가능

  • 어떤 자료형이든, 데이터 길이에 상관 없이

• 해시 충돌이 거의 없음(이게 훌륭하냐 아니냐를 결정)

• 따라서 충돌이 덜나는 해시함수가 좋다.

정말 충돌이 안나는 해시함수가 있나

• 아주 덜 나는 함수는 있다.

완전히 충돌을 없앨수는 없나?

• 기술적으로는 안 됨
• 허나 특정 조건 하에서는 해시충돌을 확실히 방지 가능
• 그런 조건이 생각보다 많다.
• 이게 가능하면 키 배열에 문자열 대신 정수만 저장해도 됨
  • char * 동적 메모리 할당이 사라짐
  • 해시테이블에 추가하는 함수를 호출 시 키 대신 해시값을 바로 사용.

해시총돌을 완벽히 방지할 수 있는 조건이란

• 고성능을 요하는 업계에서 많이 씀
  • ex:게임 개발

1 . 실행 중 해시테이블에 저장될 수 있는 데이터를 모두 알고 있음

• 예: 미리 만든 데이터 파일 읽기
• 유저로 부터 받는 입력이 아니라는 얘기

2 . 개발 도중 충돌이 없는 걸 확인하고 보장 가능

키 저장 단계를 없애도 됨.

다른 자료형은?

• 그냥 거저 먹으면 됨

• 문자열은 char*
• 어떤 데이터도 char배열로 표현 가능
  • 즉 가장 범용적인 데이터
• 아래와 같은 함수만 있으면 가능

• 단 저장하려는 데이터에 걸맞는 해시함수 찾아 써야됨

각 자료구조 별 써야할 경우

• 배열

  • 가장 간단함
  • 캐시 메모리 덕에 O표기법에 상관없이 성능이 가장 빠른 경우가 많다.
• 연결 리스트
  • 빈번한 데이터 삽입 또는 삭제

• 다음과 같은 경우는 해시 기반 자료구조들

  • 데이터 양이 많은데 검색을 자주 해야할 때
  • 배열에 넣기 힘든 데이터(ex. 연속적,규칙적인 색인이 나올 수 없을 떄)

결국 해시 테이블은 정형화 되지 않은 데이터를 정형화 되게 바꾸는 것. 자바나 다른 언어의 해시맵을 생각해보자. 다른 언어는 이미 해시맵이든 딕셔너리든 라이브러리로 주지만 직접 구현 안해보면 내부 동작을 모르게 된다. 해시라는 개념 배울떄 해시함수 써서 만들어보고 범위 특정할 수 없는 값을 (정수를) 작은 배열에 넣을 떄 그 방식을 BUCKET이라 했고 거기서 쓰는 방식이 나중에 다양한 곳에서 쓰인다. 아주 단순한 정수뿐 아니라 문자열 같은 경우도 (범위 알 수 없는) 많이 씀.그리고 해시테이블이 보장하는 O(1) 검색,탐색,삽입시간 그것 떄문에 해시테이블 쓰기도 한다.