자료구조 를 마치며

1.해쉬테이블 : 배열에서 조회의 시간복잡도가 상수인것을 이용하여 입력된 값을 조회할수있게 인덱스로 변환을 해준다 그역할을 해주는게 해쉬함수다 해쉬함수를 통해서 나온 인덱스에 밸류를 저장한다.

 

그러나 해쉬함수를 통해배출된 인덱스는 입력값은 반드시 같은 출력값으로 나오지만 출력값을 통해 입력값이 달라질수 있고 다른 입력값역시 같은 인덱스를 배출할수 있게 된다. 따라서 충돌이 일어나게 될 가능성이 있다. 

 

그러한 이유에서 해당인덱스에 바로 저장하는것이 아니라 해당인덱스는 튜플을 가리킨다. 재수가없으면 이경우에서 시간복잡도가 올라갈수 있게된다. 왜냐하면 여기서는 인덱스로 조회하는게 아니라 튜플들을 다 조회 해봐야하기 때문이다.

 

그러한 경우를 최소화 하기위해 배열의크기(bucket num) 를 조정해준다. 25% 75% 사이에 위치할때 효율이 높다.

 

1.해쉬테이블 구현시 어려웠던점 : 처음에 수도코드를 쓰면서 set함수를 insert 용으로 쓰고 get을 retrieve 로 써야겟다고 생각을 해놨던게 발목을 잡았다. get을 이용해서 꼭 값을 얻지 않더라도 조회 용으로 써야된다는 생각이 너무 늦었다.

 

리사이즈를 하는과정에서 사이즈만 바꿔주고 기존에 정렬된 내용을 재배치 해줘야된다는 점을 생각하지 못했고 구현을 어떻게 해야하는지 어려웠다.

 

2.linked list : 링크된다는 표현이 쫌 받아들이기 힘들었다. 아니 소속된거면 소속된거지 연결됬다는게 뭔말인가 싶었다. 지금도 썩 와닿지는 않는다 어쨋든 linklist 는 값이 있고 다음걸가르키는 것도 있다 그런식으로 연결이 되어있는데 이러한 특성이로 인해 추가삭제가 배열보다 용이하다 그러나 조회는 불편하다.

 

linkedlist 어려웟던점 : 연결을 속에 넣으면서 하다보니까 생각하기 복잡했다. 근데 다시 얘기하는거 들어보니까 뭔가 다시해보고싶다.ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 일단 this 가 더헤깔려지는 계기가 됬다 문제가 안풀리면 이상한데 의심이 가기시작한다. 후 덕분에 공부를 더해봣다.

그리고 참조형데이터 타입의 바라보는 개념이 헤깔리다는 걸 알았고 그 사용성도 조금더 알게됬다.

 

3.stack & queue : 스택은 접시 큐는 줄서있는거(대기열)

 

4.자료구조 구현하면서 느낀점 : 구관이 명관이라고 코플릿풀때는 어려워도 푸는 맛이 있는데 이거는 그냥 짜증남 재미도 그닥 좋게 생각하면 내가 가지고있던 지식에 의심을 해보는 계기?? 좀더 디테일하게 작용되는걸 생각할수있었던점 이 좋았다. 코플릿은 답을 자알 도출해내자는 느낌이였다면 이건 예외적인 경우가 안나오면서 내가생각한대로 작동하도록 하는거?

 

5.그래프 : 행렬식으로 일단 있는거 다 가져다가 연결 미연결 확인  // 연결식은 연결된거만 체크 

행렬식 장점 : 구현 쉬움 단점 시간복잡도 가 연결식보다 높음 //연결식 장단점 조회는 좋은데 추가삭제가 별로임

구현시 어려웠던점 ? ::  삭제할때 ? 있는지 확인을 하고 지우는 과정이 있었는데 확인 안하고 지울라고만 하니까 언디파인드에따가 배열매소드 갖다대니까 계속 안된던게 있었음.

 

6.트리

이진트리/ segment tree

segment tree : 합이뭐라 하는데 잘모르겟음 

이진트리 : 왼쪽엔 작은거 오른쪽에는 큰거 

재귀적으로 생각해야됨 .... 전위순회 중외순회 후위순회 ?? 더공부해야됨

개념이랑 구현은 쉬웠는데 막상 활용 할때는 이해가 안가는게 많은듯