HHyo814
발행일

[ZBF] 6월 11일 코딩 테스트: 해시 알고리즘

코딩테스트

[ZBF] 6월 11일 코딩 테스트: 해시 알고리즘

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

해시 알고리즘이란 무엇인가?

해시 알고리즘은 데이터를 고정된 크기의 해시 값으로 변환하는 함수입니다. 해시 값은 일반적으로 짧고 고정된 길이의 문자열이나 숫자로 표현되며, 데이터의 고유한 식별자로 사용됩니다. 해시 알고리즘은 다양한 용도로 사용되며, 가장 일반적인 사용 사례는 데이터 검색, 데이터 무결성 검증, 암호화 등입니다.

해시 알고리즘의 주요 특징

  1. 고속성: 해시 함수는 입력 데이터를 빠르게 처리하여 해시 값을 생성합니다.
  2. 결정성: 동일한 입력은 항상 동일한 해시 값을 생성합니다.
  3. 충돌 회피: 서로 다른 입력이 동일한 해시 값을 생성할 확률이 매우 낮습니다.
  4. 균등 분포: 해시 값이 가능한 한 고르게 분포되도록 설계됩니다.

해시 알고리즘의 주요 용도

  1. 해시 테이블: 해시 알고리즘은 해시 테이블의 핵심 요소로, 빠른 데이터 검색과 저장을 가능하게 합니다. 해시 테이블은 키-값 쌍을 저장하는 자료구조로, 해시 함수를 사용하여 데이터를 저장할 위치를 결정합니다.
  2. 데이터 무결성: 데이터 전송이나 저장 시 데이터의 무결성을 검증하기 위해 해시 값을 사용합니다. 파일이나 메시지의 해시 값을 계산하여 전송하고, 수신 측에서 동일한 해시 값을 계산하여 일치하는지 확인함으로써 데이터의 변조 여부를 검사할 수 있습니다.
  3. 암호화: 암호화 해시 함수는 비밀번호 저장 및 검증, 디지털 서명 등 보안 관련 분야에서 사용됩니다. 암호화 해시 함수는 한 번 해시된 데이터를 원래 데이터로 되돌릴 수 없도록 설계됩니다.

대표적인 해시 알고리즘

  1. MD5: 한때 널리 사용되었지만, 현재는 충돌 문제로 인해 보안이 중요한 분야에서는 사용되지 않습니다.
  2. SHA-1: 비교적 안전한 해시 알고리즘이었지만, 현재는 SHA-2나 SHA-3과 같은 더 안전한 알고리즘으로 대체되고 있습니다.
  3. SHA-256: SHA-2 계열의 해시 알고리즘으로, 현재 많은 보안 시스템에서 사용됩니다.
  4. SHA-3: 최신 해시 알고리즘으로, SHA-2의 대안으로 사용되고 있습니다.

해시 알고리즘의 예제 코드 (JavaScript)

// SHA-256 해시 알고리즘을 사용하는 예제 코드
// npm 패키지 crypto-js를 사용하여 구현

// crypto-js 라이브러리 로드
const CryptoJS = require('crypto-js');

// 해시 생성 함수
function generateHash(input) {
    return CryptoJS.SHA256(input).toString(CryptoJS.enc.Hex);
}

// 테스트
const input = 'Hello, world!';
const hash = generateHash(input);

console.log(`Input: ${input}`);
console.log(`Hash: ${hash}`);

문제 1: 배열에서 두 수의 합 (Two Sum)

문제 설명: 정수 배열 nums와 정수 target이 주어졌을 때, 두 수의 합이 target이 되는 두 수의 인덱스를 반환하라.

function twoSum(nums, target) {
    let hashMap = {}; // 해시 맵 초기화
    
    for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i]; // 타겟에서 현재 수를 뺀 값
        
        if (hashMap.hasOwnProperty(complement)) {
            return [hashMap[complement], i]; // 두 수의 인덱스 반환
        }
        
        hashMap[nums[i]] = i; // 현재 수를 해시 맵에 추가
    }
    
    return []; // 두 수의 합이 없는 경우 빈 배열 반환
}

// 테스트
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

문제 2: 중복 문자 찾기 (Contains Duplicate)

문제 설명: 정수 배열 nums가 주어졌을 때, 배열에 중복된 원소가 있는지 확인하라

function containsDuplicate(nums) {
    let hashSet = new Set(); // 해시 셋 초기화
    
    for (let num of nums) {
        if (hashSet.has(num)) {
            return true; // 중복된 원소가 있는 경우 true 반환
        }
        hashSet.add(num); // 현재 원소를 해시 셋에 추가
    }
    
    return false; // 중복된 원소가 없는 경우 false 반환
}

// 테스트
console.log(containsDuplicate([1, 2, 3, 1])); // true
console.log(containsDuplicate([1, 2, 3, 4])); // false

문제 3: 배열의 유일한 원소 찾기 (Single Number)

문제 설명: 정수 배열 nums에서 각 원소는 두 번씩 나타나고, 한 원소는 한 번만 나타난다. 한 번만 나타나는 원소를 찾아라.

function singleNumber(nums) {
    let hashMap = {}; // 해시 맵 초기화
    
    for (let num of nums) {
        hashMap[num] = (hashMap[num] || 0) + 1; // 각 원소의 빈도 계산
    }
    
    for (let num in hashMap) {
        if (hashMap[num] === 1) {
            return parseInt(num); // 빈도가 1인 원소 반환
        }
    }
}

// 테스트
console.log(singleNumber([2, 2, 1])); // 1
console.log(singleNumber([4, 1, 2, 1, 2])); // 4

https://school.programmers.co.kr/learn/courses/30/parts/12077

  • 프로그래머스 스쿨 - 온라인 IT 특화 교육 전문 플랫폼 — 프로그래머스 스쿨은 IT 분야 교육 전반의 과정을 제공하는 온라인 교육 플랫폼입니다. 프로그래밍, 데이터, 인공지능 등의 학습부터 코딩 테스트, 과제 테스트 연습까지, 프로그래머스 스쿨과 함께 성장해 보세요!
← 글 목록으로