아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 해시 함수에서의 문자열 문자열 "this"를 해시로 나타내려면, 각 문자를 유니코드로 변환한 후 숫자들을 합하여 나타낼 수 있을 것이다. 그런데 이렇게 변환할 경우, this뿐만 아니라 hits, tish 등 다른 문자열도 같은 숫자로 표현되는 해시 충돌이 발생한다. 여기서 어떤 상수 g를 문자의 위치만큼 제곱한 뒤 그 수를 곱하여 해시충돌을 최소화 할 수 있다. 문자열의 길이가 아주 길다면 subString으로 더 작은 문자열만 사용하여 나타내면 된다. public int hashCode(String s) { // this int g = 31; int hast = 0; for(int i = s.length() -1; i >= 0; i--) // s..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 해시(Hash) 연결 리스트에서는 어떤 요소를 찾고자 할 때, 시작 지점에서부터 순차적으로 살펴봐야 했기에 시간 복잡도가 O(n)이었다. 해시는 데이터를 검색할 때 사용할 key와 key를 통해 찾을 수 있는 연관된 값 value를 갖고 있어, 키가 주어지면 바로 연관된 값을 찾을 수 있다. 따라서 일반적으로 검색의 시간 복잡도가 O(1)이다. 즉, 해시는 모든 요소를 살펴본 후 동일한 노드를 찾아야 하는 연결 리스트와 달리 데이터를 빠르게 추가하고 제거하며 빠른 검색이 가능한 데이터 구조이다. 해시 함수 (Hash Function) 해시 함수(hash function)은 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 배열 기본적인 배열에서 첫 부분을 제거하거나 추가하기 위해서는 요소들을 하나하나 뒤로 당겨주어야 하므로 시간복잡도가 O(n)이다. 스택과 큐를 하기에는 비효율적이므로 이러한 기본적인 배열은 거의 사용되지 않는다. 배열 addLast, removeLast 시간 복잡도: O(1) 배열 addFirst, removeFirst 시간 복잡도: O(n) 스택(stack) 스택은 LIFO(Last in, First out - 후입선출)의 방식으로, top으로 정한 한 곳을 통해서만 접근이 가능하다. 책과 물건을 아래서부터 위로 쌓아올려 꺼낼 때 위에서부터 들어내어 꺼내는 양상에 빗댈 수 있다. 배열로 스택을 구현하면 마지막 요소에 새롭게 추가하고 다시 제거하면 ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 이중 연결 리스트 단일 연결 리스트에 previous 포인터를 추가한, 양방향 연결 리스트이다. removeLast 메소드를 사용할 때, 시간 복잡도는 O(n)이다. 단일 연결 리스트는 tail 포인터가 있더라도 새롭게 tail로 바꾸어 줄 이전의 노드를 바로 찾을 수 없기 때문에 current, previous를 이용해 앞에서부터 마지막에서 두 번째 노드까지 이동하는 과정이 필요하기 때문이다. 반면 이중 연결 리스트는 (삽입, 제거 시) 시간 복잡도가 O(1)인데, tail 포인터가 가리키는 노드의 previous 포인터가 가리키는 노드(tail.previous)를 찾으면 되기 때문이다. 단, 노드를 추가하는 과정에서 next 포인터와 함께 pre..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. peek 메소드 peek 메소드는 연결 리스트의 특정 하나의 node를 살펴보는 메소드로, 추가하거나 제거하기 위함이 아닌 요소의 내용을 읽기 위함이다. peekFirst 첫 노드를 읽기 위한 peekFirst 메소드를 위해서는 단순히 head의 data를 살펴보면 된다. 따라서 head.data를 반환해준다. 이번 역시 경계 조건 1. 리스트가 비어있을 경우에 head가 null일 때 head.data를 반환하면 NullporintException이 발생하게 되므로 다른 메소드의 경우와 같이 null을 반환해준다. public E peekFirst(){ if(head==null) { return null; } return head.data; } p..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. removeFirst 메소드 연결 리스트의 첫 번째 node를 제거하기 위한 removeFirst 메소드를 만든다고 생각해보자. 첫 노드를 제거하기 위해서는, 그 노드를 가리키는 포인터가 없게해서 가비지 컬렉션이 일어나도록 하고 data에 저장된 객체를 반환해야 한다. 그러므로 우선 head 포인터가 두 번째 노드를 가리키게끔 만들기 위해 head = head.next; 를 해볼 수 있다. head = head.next; 이 때 앞에서 살펴본 자료구조에서 고려해야 하는 경계 조건을 만족하는지를 따져 보면, 경계 조건 1. 자료구조가 비어있는 경우(head = null; 일 경우) addLast에서 tmp가 null일 경우와 마찬가지로 head가 he..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 경계 조건 (Boundary Conditions) 어떤 자료구조든 아래와 같은 경계 조건에서 발생 가능한 문제를 항상 고려해야 한다. 자료구조가 비어있는 경우 자료구조에 하나의 요소만이 들어있을 때 자료구조의 시작에 삽입 / 삭제할 경우 자료구조의 끝에 삽입 / 삭제할 경우 자료구조의 중간 부분을 처리할 경우 AddFirst 메소드 아래와 같이 코드를 작성해 연결리스트 앞부분에 새로운 node를 추가할 수 있다. public void addFirst(E obj){ Node node = new Node(obj); // 1새로운 node 객체 생성 node.next = head; // 2 새 node의 next가 현재 head가 가리키고 있는 곳을 가리..
