[99클럽 코테 스터디] 📝 Day2. 꾸준함

99클럽 코테 스터디 2일차 TIL + Hash

📍오늘의 학습 키워드

자료 구조, 문자열, 정렬, 해시를 사용한 집합과 맵 

📝 공부한 내용 본인의 언어로 정리하기

자료구조 Hash란

해시 자료 구조는 데이터의 빠른 검색, 삽입, 삭제를 위해 사용되는 데이터 구조입니다. 해시 테이블(Hash Table)이라고도 불리며, 키-값 쌍을 저장하는 데 사용됩니다. 해시 자료 구조의 핵심 개념은 해시 함수(Hash Function)입니다. 해시 함수는 임의의 크기를 가지는 데이터를 고정된 크기의 값으로 매핑하는 함수입니다.

주요 개념!

1. 해시 함수 (Hash Function):
   • 입력 데이터를 받아서 해시 코드를 생성합니다. 이 해시 코드는 데이터의 인덱스로 사용되어 해시 테이블에서 해당 데이터를 빠르게 찾을 수 있게 합니다.
   • 좋은 해시 함수는 입력 데이터의 분포를 고르게 하고 충돌을 최소화해야 합니다.
2. 해시 테이블 (Hash Table):
   • 해시 함수로 생성된 해시 코드를 인덱스로 사용하여 키-값 쌍을 저장하는 배열입니다.
   • 해시 테이블의 각 위치는 버킷(Bucket)이라고 불립니다.
3. 충돌 (Collision):
   • 서로 다른 두 키가 동일한 해시 코드를 생성할 때 발생합니다.
   • 충돌을 처리하기 위해 여러 가지 방법이 사용됩니다.

충돌 해결 기법

1. 체이닝 (Chaining):
   • 각 버킷을 연결 리스트로 관리하여 충돌이 발생하면 해당 버킷의 리스트에 데이터를 추가합니다.
2. 오픈 어드레싱 (Open Addressing):
   • 충돌이 발생하면 다른 빈 버킷을 찾아 데이터를 저장합니다.
   • 선형 탐사 (Linear Probing), 이차 탐사 (Quadratic Probing), 이중 해싱 (Double Hashing) 등의 방법이 있습니다.

장점

• 빠른 검색: 평균적으로 O(1) 시간 복잡도로 데이터 검색, 삽입, 삭제가 가능합니다.
• 유연성: 다양한 종류의 데이터를 키-값 쌍으로 저장할 수 있습니다.

단점

• 충돌 문제: 충돌이 발생하면 성능이 저하될 수 있습니다. 충돌 해결을 위한 추가 작업이 필요합니다.
• 공간 효율성: 해시 테이블의 크기를 적절히 설정하지 않으면 메모리 낭비가 발생할 수 있습니다.

* 자바의 HashMap

자바에서 해시 자료 구조를 구현한 대표적인 클래스는 HashMap입니다. HashMap은 키-값 쌍을 저장하며, 내부적으로 체이닝을 사용하여 충돌을 해결합니다.

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // HashMap 선언
        HashMap<String, Integer> map = new HashMap<>();

        // 데이터 추가
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("orange", 3);

        // 데이터 검색
        System.out.println("Value for key 'apple': " + map.get("apple"));

        // 데이터 삭제
        map.remove("banana");

        // 전체 데이터 출력
        for (String key : map.keySet()) {
            System.out.println(key + ": " + map.get(key));
        }
    }
}

 

이 예제에서 HashMap은 문자열을 키로, 정수를 값으로 저장하고 있습니다. 해시 함수를 사용하여 각 키를 해시 테이블의 인덱스로 매핑하고, 키-값 쌍을 저장 충돌이 발생하면 체이닝 기법을 사용하여 충돌을 해결

📖 오늘의 회고

📚 어떤 문제가 있었고, 나는 어떤 시도를 했는지

처음 풀이할때 문제가 있었다.

최대 접두사 길이를 계산하는 부분에서 잘못된 점이 있었던것이다.

문제는 동일한 단어를 반복해서 비교하기 때문에 발생했었던것 디버깅을 하여 원인을 알 수 있었고 이를 수정하여 최대 접두사 길이를 정확하게 계산하도록 수정했다. 

(디버깅은 소중해,,,🥹)

🤔 어떻게 해결했는지

• 블로그 글 참고! (링크 : https://develop-tracking.tistory.com/48)

🤓 무엇을 새롭게 알았는지

문제를 풀이하면서 두 가지 방식으로 진행했다. 

이중 루프를 사용하여 모든 단어 쌍을 비교하고 접두사 길이를 계산하는 방식과 이 클래스는 단어를 저장할 때 인덱스를 함께 저장하는 해시맵을 사용하여 입력된 순서를 기억하고, 이중 루프를 사용하여 모든 단어 쌍을 비교하는 방식 

사실상 로직에서 큰 차이는 없지만 속도 차이가 있었다. 그래서 개선을 해보고자 했는데 음.. 역시나 메모리초과 발생 

그래도 로직 차이점을 비교해가며 어떤 코드가 괜찮은 코드인지 고민해보는 시간을 가질 수 있어서 클린코드에 대해서 다시 한 번 느끼게 되었달까 (?) 

 

아래는 내가 여러번 시도한 흔적.. 

⏳내일 학습할 것은 무엇인지