해시 테이블부터는 일시정지 버튼 계속 누르고 생각 많이 했다. 이해가 적어도 어느 정도는 될 때까지 생각하고 답을 찾고 넘어왔다. 그래서 총 20분 정도 되는 영상을 3시간을 보았다.
.... :)
모레 면접볼 때까지는 이제 알고리즘 공부는 스탑하고 대신 면접 끝나면 지금 듣는 강의 바로 다 듣고(자바-알고리즘) 그 다음에는 자바스크립트로 구현하는 알고리즘 강의도 듣고자 한다.
어제 빅테크에서 일하는 개발자의 vlog를 보다가 학교에서 수강했던 cs 강의 목록을 보여줬는데 자기한테 제일 도움됐던 강의가 dsa 관련 강의라고 했다. 왜냐면 "it taught me how to leetcode and helped me land in silicon valley" lol
결국 릿코드로 귀결되는 이 여정,,
Hash Table
import java.util.ArrayList;
public class HashTable {
private int size = 7;
// HT는 a prime number of addresses를 가질 때
// fewer collisions를 가진다. - 소수 개의 주소값
private Node[] dataMap;
// when we set something type 'Node', it is a pointer to a node.
// thus this is an array of pointers to nodes.
public HashTable() {
dataMap = new Node[size];
// HashTable 객체를 생성하면 자동적으로 7개의 테이블이 생긴다 [0-6]
}
// LL에서 썼던 Node 클래스와는 구조가 다르다
class Node {
private String key;
private int value;
private Node next;
public Node(String key, int value) {
this.key = key;
this.value = value;
}
}
private int hash(String key) {
int hash = 0;
char[] keyChars = key.toCharArray();
for(int i = 0; i < keyChars.length; i++) {
int asciiValue = keyChars[i];
hash = (hash + asciiValue * 23) % dataMap.length;
// 왜 23 multiply로 hash값 내는 로직을 만들었을까?
// 소수이기 때문이다. 소수를 곱해 값을 얻으면 결과가 more random하다.
// dataMap.length = 7
// %는 우리에게 remainder를 준다 -> 1~6사이의 결과값을 얻을 것이다
// 이 알고리즘에서 해시값은 주소값이고 우리는 지금 7개의 테이블을 갖고 있다
// 키값쌍을 가진 노드가 해시값에 따라 테이블의 어떤 인덱스에 배정될 것이다
}
return hash;
}
public void set(String key, int value) {
int index = hash(key);
Node newNode = new Node(key, value);
if(dataMap[index] == null) { // 비어있는 인덱스라면 그냥 바로 노드 갖다 붙이면 된다
dataMap[index] = newNode;
} else { // 이미 그 인덱스의 테이블에 존재하고 있는 노드가 있다면
Node temp = dataMap[index];
// 그 인덱스의 테이블에 있는 노드 LL을 iterate할 변수를 만듦
// dataMap[index]는 첫 번째 노드를 포인팅하는 노드다.
// temp = head 와 같은 로직이다
while(temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
}
public int get(String key) {
int index = hash(key);
Node temp = dataMap[index];
// iterate할 변수, temp=head 작업
while (temp != null) {
// 찾는 게 있으면 key에 대한 value 값 반환
if(temp.key == key) return temp.value;
temp = temp.next;
}
return 0;
// 찾는 게 없으면 0을 반환
// 그 인덱스의 테이블이 비어있었다면 temp=null
// while 루프 실행조차 안 하고 바로 0 리턴
}
public ArrayList keys() {
// 테이블 안의 모든 key를 꺼내서 다시 ArrayList로 반환하는 메서
ArrayList<String> allKeys = new ArrayList<>();
// 1. 우선 테이블을 인덱스 순서대로 탐색한다 : for loop
for (int i = 0; i < dataMap.length; i++) {
Node temp = dataMap[i];
// 해당 인덱스의 테이블에 있는 노드 LL을 탐색할 변수
// temp = head 작업
while (temp != null) {
// 그 인덱스 안에는 몇 개의 노드가 있는지 모름 : while loop
allKeys.add(temp.key);
temp = temp.next;
}
}
return allKeys;
}
public void printTable() {
for (int i = 0; i < dataMap.length; i++) {
System.out.println(i + " : ");
Node temp = dataMap[i];
while (temp != null) {
System.out.println(" {" + temp.key + "=" + temp.value + "}");
temp = temp.next;
}
}
}
}
같은 값 찾기
Nested For Loop : O(n^2)
- Simple. But inefficient.
public boolean itemInCommon_nestedFor(int[] array1, int[] array2) {
for (int i : array1) {
for (int j : array2) {
if(i == j) return true;
}
}
// int i와 int j는 배열 안의 아이템
return false;
}
HashMap with Two For Loops : O(n)
- Technically, it's O(2n) but we see it as an O(n).
- Much more efficient than the nested for loop.
public boolean itemsInCommon_HashMap(int[] array1, int[] array2) {
HashMap <Integer, Boolean> hm = new HashMap<>();
for (int i : array1) {
hm.put(i, true);
}
for (int j : array2) {
if (hm.get(j) != null) return true;
// 앞선 for문에서 put을 통해 hashmap에 들어가지 않은 숫자는
// 즉 1,3,5를 제외한 모든 숫자는
// hm.get(x)에서 null 값을 반환한다
}
return false;
}
Working Abroad ...