크래프톤 정글 7기 8,9일차 / 정렬 방법 / 해시 충돌

처음에는 시간이 느리게 간 것 같은데, 어느새 정글에 온지 8일차이다. 

대부분 사람들의 얼굴을 이제는 기억하고 친해지기 시작했다. 

 

오늘은 알고리즘 문제를 3문제 정도 풀고,

내일 있을 Quick sort 시험에 대해 준비하였다. 

 

교재를 통해  Quick sort를 공부하면서 정글러와 이야기를 나누었다. 

훨씬 더 간단한 코드가 있는데, 도대체 왜 이렇게 쓴 것인지. 

 

간단한 코드를 통해서도 충분히 Quick sort를 알 수 있었고, 

굳이 교과서대로 할 필요성도 못 느꼈다. 

 

이와 관련해서, 현직 일을 하다오신 다른 정글러 형님에게 여쭤보았고, 

이것들을 컴퓨터 시스템 측면으로 설명을 해주셨다. 

" 단순히 이럴 것 같기 때문에가 아니라, 이런 구조 때문에 이렇다 ! "

이런 얘기를 듣고 CS의 중요성을 또 한번 절실해 깨달았다. 

 

이제 정글 8일차이고 어느 정도 적응이 된 상태이자, 

또한 위험한 상태일수도 있겠다는 생각이 든다. 

지금 이 상황들에 익숙해져서 간절함,긴장감도 사라질 수 있겠다는 생각이 든다. 

 

내가 정글에 와서 이루고 싶은게 뭘까 ? 

내가 이루고 싶은거는 진짜 개발자이다. 

단순히 몇개의 기술 스택만 아는것이 아니라, 

그 원리까지 깊게 이해하고 컴퓨터적 사고를 하고 싶다. 

그리고 이게 정글의 목표일거라 생각한다. 

 

그래서 이와 관련해서 나와 마음이 맞는 정글러와 이야기를 나눠보았고, 

그 정글러도 나와 같은 마음을 가지고 있었다. 

 

그래서 !!  (물론 알고리즘도 중요하지만) 

좀 더 CS 적으로 공부를 해볼 예정이다. 

아직 어떻게 어떤식으로 해야할지는 잘 모르겠다. 

무작정 읽어야 할지, 다른 유튜브 강의를 보아야 할지...

 

하지만  "Computer System a Programmer's Perspective"

이 책 만큼은 꼭 간절하게 다 읽고 이해하고 싶다. 

 

아래 멘트는 정글러 형님이 해주신 말이다. 

" 면접에서 칠판 손으로 지우면 면접관들이 좋아한다 " 

큰 의미를 두지 않고 그냥 하신 말인거 같은데 ,

나에게는 크게 다가왔다.

 

정글러 형님이 설명해주실때

정말로 컴퓨터에대해 애착이 느껴졌고, 진심이 느껴졌다. 

나도 그렇게 성장하고 싶다 . 

 

9일차에는 쪽지 시험이 있었다. 

오전에 블로그 쓰는 척 끄적이다 시간을 버린 것 같다...

확실히 계획 없이 스터디를 하니까 효율성이 많이 떨어진다. 

무작정 앉아있는 시간을 늘리는 것 보다 집중하는 시간을 늘려보자. 

 

그래서 9일 차에 뭘 했냐 ...? 

알고리즘 문제 한개 풀고 컴퓨터 시스템 좀 끄적이고 ....

알고리즘 문제 1개 푼 것이 전부이다. 

진짜 이렇게 살면 안되겠다는 생각이 든다... 

 

내일부터는 공부 전 시간을 재고, 

졸리면 차라리 잠을 자고 온전히 집중 할 수 있는 시간을 늘려보자. 

---

정렬 알고리즘 내용이 좀 길어져서 CS 카테고리에 따로 업로드 했다. 

 

정렬 알고리즘 (삽입,선택,버블,셸,퀵,힙,병합 정렬)

 

---

다음은 1주차 퀴즈 문제 기억에 남는 것들 중 하나이다. 

 

Q. 해시 충돌은 무엇이며, 그것이 발생하는 원인과 해결하기 위한 다양한 방법들 중, 체이닝을 설명하시오. 

 

 

해시는 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑한다.

 

해시 함수는 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다.

해시 테이블은 키와 값을 매핑해둔 데이터 구조이다. key 값을 활용하여 index로 사용한다. 

 

해시를 사용하는 이유는 시간복잡도가 O(1)이기 때문에 사용한다. 

 

해시 충돌 :

해시 테이블 크기보다키의 갯수가 더 많기 때문에 두 개의 키가 동일한 slot에 hashing 될 수 있는데

이를 해시 충돌이라고 한다.

 

해시 충돌 해결:

충동을해결하기 위한 Chaning과 Open Addressing 방법이 있다. 

 

- Chaning 방법:

충돌 시 연결 리스트에 추가하는 방식이다.

 

중복된 해시 값이 있는 경우, 해당 슬롯을 연결 리스트로 저장한다.  

하지만 이 방법은 연결 리스트로 인해 최악의 경우 수행 시간이 O(n)이 된다.

이미 저장하고 있는 데이터가 존재한다면 마치 LinkedList 구조와 같이 bucket에

새로운 노드를 연결해서 기존의 데이터가 추가, 저장되는 형태

 

- Open Addresiing 방법:

충돌 발생 시 해시함수로 얻은 주소가 아닌 다른 주소 공간(다른 버킷) 데이터를 저장한다.

Open Addresiing은 충돌을 피하기 위한 다른 방법으로 key를 해시 테이블에 직접 저장한다. 

해당 방법의 장점은 포인트를 사용하지 않아도 되어 간편하고 검색도 미세하게 빨라진다.