HHyo814
발행일

[99클럽] 99클럽 코테 스터디 6일차 TIL + 문자열 / 해시

코딩테스트

[99클럽] 99클럽 코테 스터디 6일차 TIL + 문자열 / 해시

이 글은 네이버 블로그에 2025년 1월 20일에 올렸던 것을 그대로 옮겨온 것입니다.

  • 오늘의 학습 키워드

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

  • 오늘의 회고

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

  • 어떻게 해결했는지

  • 무엇을 새롭게 알았는지

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

해시에 대한 이해와 코딩 테스트 준비하기

코딩 테스트에서 '해시(Hash)'는 매우 중요한 개념 중 하나입니다. 해시를 잘 이해하고 활용하면 복잡한 문제도 효율적으로 해결할 수 있습니다. 이번 글에서는 해시의 기본 개념부터 코딩 테스트에서 자주 등장하는 문제 유형과 그 해결 방법까지 살펴보겠습니다.

1. 해시(Hash)란?

해시는 데이터를 고유한 키-값(key-value) 쌍으로 저장하는 자료구조입니다. 해시는 빠른 검색, 삽입, 삭제를 가능하게 하며, 일반적으로 평균 시간 복잡도가 O(1)입니다.

주요 특징:

  • 키를 기반으로 데이터를 검색: 배열이나 리스트처럼 인덱스를 사용하지 않고, 키를 이용해 데이터에 접근합니다.
  • 충돌(Collision) 처리: 서로 다른 키가 같은 해시 값을 가질 수 있기 때문에, 충돌을 처리하는 다양한 방법이 필요합니다.

해시 테이블의 구조:

  1. 해시 함수(Hash Function): 키를 해시 값으로 변환하는 함수입니다.
  2. 버킷(Bucket): 데이터를 저장하는 공간으로, 해시 값을 기반으로 데이터를 저장합니다.

2. 코딩 테스트에서 자주 사용하는 해시의 기능

(1) 빈도수 세기

  • 문자열이나 배열에서 각 요소의 빈도를 계산하는 데 유용합니다.

예제 문제: 주어진 문자열에서 가장 많이 등장하는 문자를 찾으세요.

function mostFrequentChar(str) { const charCount = {}; for (const char of str) { charCount[char] = (charCount[char] || 0) + 1; } let maxCount = 0; let maxChar = ''; for (const [char, count] of Object.entries(charCount)) { if (count > maxCount) { maxCount = count; maxChar = char; } } return maxChar; } console.log(mostFrequentChar("programming")); // "r"

(2) 중복 요소 찾기

  • 배열에서 중복된 요소를 찾는 데 자주 사용됩니다.

예제 문제: 배열에서 중복된 숫자를 모두 찾으세요.

function findDuplicates(arr) { const seen = new Set(); const duplicates = new Set(); for (const num of arr) { if (seen.has(num)) { duplicates.add(num); } else { seen.add(num); } } return Array.from(duplicates); } console.log(findDuplicates([1, 2, 3, 4, 3, 2, 5])); // [2, 3]

(3) 두 배열 비교

  • 두 배열에서 공통 요소를 찾거나, 차집합을 계산할 때 유용합니다.

예제 문제: 두 배열의 공통 요소를 찾으세요.

function findCommonElements(arr1, arr2) { const set1 = new Set(arr1); const result = []; for (const num of arr2) { if (set1.has(num)) { result.push(num); } } return result; } console.log(findCommonElements([1, 2, 3], [3, 4, 5])); // [3]

3. 충돌(Collision) 처리 방법

해시 테이블에서 충돌을 처리하기 위한 대표적인 방법은 다음과 같습니다:

(1) 체이닝(Chaining)

  • 동일한 해시 값을 가진 데이터를 연결 리스트로 저장합니다.

(2) 오픈 어드레싱(Open Addressing)

  • 충돌이 발생하면, 다른 빈 슬롯을 탐색하여 데이터를 저장합니다.
  • 선형 탐사(Linear Probing): 다음 슬롯을 순차적으로 탐색합니다.
  • 이차 탐사(Quadratic Probing): 일정한 간격으로 슬롯을 탐색합니다.
  • 이중 해싱(Double Hashing): 다른 해시 함수를 사용해 새로운 슬롯을 찾습니다.

4. 코딩 테스트에서 자주 나오는 문제 유형

(1) 애너그램(Anagram) 판단

  • 두 문자열이 애너그램 관계인지 확인하는 문제입니다.

function isAnagram(str1, str2) { if (str1.length !== str2.length) return false; const count = {}; for (const char of str1) { count[char] = (count[char] || 0) + 1; } for (const char of str2) { if (!count[char]) return false; count[char]--; } return true; } console.log(isAnagram("listen", "silent")); // true

(2) 서로 다른 부분 배열의 개수 찾기

  • 주어진 배열에서 모든 고유한 부분 배열(subarray)의 개수를 구하는 문제입니다.

(3) 해시맵을 사용한 최적화

  • 예를 들어, 두 숫자의 합으로 목표 값을 만드는 쌍을 찾는 문제(Two Sum) 등.

function twoSum(nums, target) { const map = new Map(); for (let i = 0; i < nums.length; i++) { const complement = target - nums[i]; if (map.has(complement)) { return [map.get(complement), i]; } map.set(nums[i], i); } return []; } console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

5. 효율적인 학습 방법

  • 기본 이론 학습: 해시의 동작 원리와 충돌 처리 방식을 이해하세요.
  • 자료구조 라이브러리 활용: JavaScript의 Map과 Set 같은 기본 제공 해시 구조를 적극적으로 사용하세요.
  • 문제 풀이 연습: 다양한 유형의 코딩 테스트 문제를 풀어 보며 응용력을 키우세요.

해시는 코딩 테스트에서 가장 기본적이면서도 강력한 도구입니다. 위의 개념과 예제를 충분히 익히고, 실제 문제를 통해 연습하면 해시를 완벽히 다룰 수 있을 것입니다!

비기너 할리갈리 https://www.acmicpc.net/problem/27160

미들러 DFS와 BFS https://www.acmicpc.net/problem/1260

챌린저 특정한 최단 경로https://www.acmicpc.net/problem/1504

스터디 문제 정리

https://school.programmers.co.kr/learn/courses/30/lessons/258709

https://school.programmers.co.kr/learn/courses/30/lessons/43238

https://school.programmers.co.kr/learn/courses/30/lessons/42577

https://www.acmicpc.net/problem/27160

const filePath = process.platform === "linux" ? 0 : "./input.txt";
let [N, ...arr] = require("fs").readFileSync(filePath).toString().trim().split("\n");

let dict = {}
arr.forEach(item => {
    const [fruit, num] = item.split(' ')

    if (dict.hasOwnProperty(fruit)){
        // console.log(dict)
        dict[fruit] = dict[fruit] + Number(num)
    }else{
        dict[fruit] = Number(num)
    }
    
})

if (Object.values(dict).includes(5)){
    console.log("YES")
}else{
    console.log("NO")
}

필수 해시태그: #99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL

image
← 글 목록으로