🤖 옌지니어의 IT 기록 🤖

해시란?
해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조

해시의 특징

• 단방향 동작 (키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾기 불가능)
• 키 자체가 인덱스이므로 값을 찾기 위한 탐색 불필요
• 값을 인덱스로 활용하기 위해 적절한 변환과정 필요

해시의 동작방식

해시 테이블(hash table) : 키와 대응한 값이 저장되어 있는 공간

버킷(bucket) : 해시 테이블의 각 데이터

해시의 특성을 활용하는 분야

단방향으로만 검색이 가능한 대신 빠르게 원하는 값 검색 (데이터를 저장하고 검색하는 경우 / 보안이 필요한 경우에 활용)

• 비밀번호 관리 : 비밀번호를 그대로 노출해 저장하는 것은 위험하므로 해싱한 비밀번호 저장
• 데이터베이스 인덱싱 : 데이터베이스에 저장된 데이터를 효율적으로 검색
• 블록체인 : 각 블록은 이전 블록의 해시값을 포함하며 이를 통해 데이터 무결성 확인

해시함수를 구현할 때 고려할 내용

• 해시 함수가 변환한 값은 인덱스로 활용해야하므로 해시 테이블의 크기를 넘으면 안된다.
• 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다.
  (충돌 : 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미)

자주 사용하는 해시함수

1) 나눗셈법 (division method)

• x = 키 / m = 소수 
• 키를 소수로 나눈 나머지를 인덱스로 사용 (충돌을 줄이기 위해 소수 사용)
• 나머지를 취하는 연산을 모듈러 연산이라고 하며 연산자로 % 사용
• m을 모듈러 연산했을 때 나올 수 있는 값은 0~(m-1)이므로 해시 테이블의 크기는 m (큰 소수를 찾기 어려운 문제)

2) 곱셈법 (multiplication method)

• m = 최대 버킷의 개수 / A = 황금비 (수학적으로 임의의 길이를 나누었을 때 전체:긴 부분 = 긴 부분:짧은 부분인 비율)
• 곱셈법을 계산하는 방식
  • 키에 황금비 곱하기
  • 위에서 구한 값의 모듈러 1 취하기 (정수 부분을 버리고 소수 부분 취하기)
  • 위에서 구한 값을 가지고 실제 해시 테이블에 매핑

문자열 해싱

• 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱
• 해시 함수를 적용한 값이 해시 테이블 크기에 비해 너무 클 경우 수정 작업 필요
  → 덧셈을 전부 한 다음 모듈러 연산을 하는 대신 중간중간 모듈러 연산을 해 더한값을 모듈러 연산

충돌 처리

충돌(collision) : 서로 다른 키에 대해 해시 함수의 결과값이 같은 것 (하나의 버킷에 2개의 값을 넣dj 충돌 처리가 필요)

1) 체이닝으로 처리하기

체이닝 : 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터 연결

• 해시 테이블 공간 활용성이 떨어진다. (충돌이 많아지면 링크드리스트의 길이가 길어져 해시 테이블 공간 사용도↓)
• 검색 성능이 떨어진다. (충돌이 많으면 링크드리스트 자체의 한계로 검색 성능 저하)

2) 개방 주소법으로 처리하기

개방 주소법(open addressing) : 빈 버킷을 찾아 충돌값을 삽입 → 해시 테이블을 최대한 활용하므로 효율적 메모리 사용

• 선형 탐사 방식 (linear probing) 
  • 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동
  • 해시 충돌이 발생한 값끼리 모이는 영역이 생겨 클러스터 형성 (이러한 군집이 생기면 해시값이 겹칠 확률 증가)
• 이중 해싱 방식
  • 해시 함수를 2개 사용
  • 두 번째 해시함수는 첫 번째 해시함수로 충돌이 발생하면 해당 위치 기준 어떻게 위치를 정할지 결정하는 역할
  • 선형 탐사와 비슷하게 더하는 방식이지만 주어지는 키마다 점프하는 위치를 다르게 해서 클러스터 형성 감소

해시 문제의 핵심은 키와 값을 매핑하는 과정 !!

※ 참고 자료 ※

https://wikidocs.net/221191

큐(Queue)란?

먼저 들어간 데이터가 먼저 나오는 자료구조

• FIFO(First In First Out) : 선입선출
• push : 큐에 삽입하는 연산 / pop : 큐에서 꺼내는 연산

큐의 동작원리

큐의 특성을 활용하는 분야

여러 이벤트가 발생했을 때 발생한 순서대로 처리하는 작업

• 작업 대기열 : 네트워크 통신 시 다수의 클라이언트에서 서버에 작업을 요청하면 들어온 순서대로 작업 처리
• 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자 이벤트(키보드/마우스) 처리

큐의 ADT (Abstract Data Type)

• 스택과 유사하지만 스택의 top → 큐의 front(앞) / rear(뒤)
  • 큐는 앞에서 데이터를 빼고 뒤에서 넣으므로 앞뒤 최종위치 저장 필요

큐의 세부동작

큐 구현하기

1) 리스트를 활용하는 방식

• push : append( )
• pop : pop( )
  •  첫 번째 데이터를 제거해야 하므로 pop(0) 사용

queue = []

# 큐에 데이터 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거
first_item = queue.pop(0)
print(first_item)

# 큐에 데이터 추가
queue.append(4)
queue.append(5)

# 큐의 맨 앞 데이터 제거
first_item = queue.pop(0)
print(first_item)

2) 덱을 활용하는 방식

• DEQ(Double Ended Queue)
• 양 끝에서 삽입이나 삭제할 수 있는 큐를 구현한 것

from collections import deque

queue = deque()

# 큐에 데이터 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거
first_item = queue.popleft()
print(first_item)

# 큐에 데이터 추가
queue.append(4)
queue.append(5)

# 큐의 맨 앞 데이터 제거
first_item = queue.popleft()
print(first_item)

※ 참고 자료 ※

https://wikidocs.net/221191

스택(Stack)이란?

먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조

• FILO(First In Last Out) : 먼저 들어간 것이 마지막에 나오는 규칙
• push : 스택에 삽입하는 연산 / pop : 스택에서 꺼내는 연산

스택의 동작원리

스택의 ADT (Abstract Data Type)

추상 자료형이라는 뜻으로 인터페이스만 있고 실제로 구현은 되지않은 자료형

스택의 세부동작

스택 구현하기

stack = []          # 스택 리스트 초기화
max_size = 10       # 스택의 최대크기

# 스택이 가득찼는지 확인하는 함수
def isFull(stack):
    return len(stack) == max_size

# 스택이 비어있는지 확인하는 함수
def isEmpty(stack):
    return len(stack) == 0

# 스택에 데이터를 추가하는 함수
def push(stack, item):
    if isFull(stack):
        print("스택이 가득 찼습니다.")
    else:
        stack.append(item)
        print("데이터가 추가되었습니다.")

# 스택에서 데이터를 꺼내는 함수
def pop(stack):
    if isEmpty(stack):
        print("스택이 비어있습니다.")
        return None
    else:
        return stack.pop()

• 파이썬의 리스트는 크기를 동적으로 관리하므로 실제 코드에서 max_size, isFull(), isEmpty() 함수 구현 X
• push(), pop() 함수가 하는 일은 리스트의 메서드를 호출하는 것 뿐이므로 굳이 구현 X
• 위의 코드를 아래 코드로 바꾸어서 사용

stack = []

# 스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)

# 스택에서 데이터 꺼내기
top_element = stack.pop()	# top_element = 3
next_element = stack.pop()	# next_element = 2

# 스택의 크기 구하기
stack_size = len(stack)

→ 스택의 개념 자체는 어렵지 않지만 문제를 보고 스택을 떠올리기 위해 문제연습이 필요 !!

※ 참고 자료 ※

https://wikidocs.net/221191

배열

인덱스와 값을 일대일 대응해 관리하는 자료구조

• 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응
• 어떤 위치에 있는 데이터든 한 번에 접근 가능 → 임의 접근 (random access)

배열을 선언하는 방법

# 1. 일반적인 방법
arr = [0,0,0,0,0,0]
arr = [0] * 6

# 2. 리스트 생성자를 사용하는 방법
arr = list(range(6))			# [0,1,2,3,4,5]

# 3. 리스트 컴프리헨션을 활용하는 방법
arr = [0 for _ in range(6)]		# [0,0,0,0,0,0]

※ 파이썬의 경우 배열 대신 리스트를 사용 ※

배열과 차원

• 배열은 2차원, 3차원과 같이 다차원 배열로도 사용
• 컴퓨터 메모리 구조는 1차원이므로 다차원 배열도 1차원 공간에 저장
• 배열은 차원과 무관하게 메모리에 연속 할당

1차원 배열

• 가장 간단한 배열 형태
• 배열의 모습 = 메모리에 할당된 실제 배열의 모습

2차원 배열

• 1차원 배열을 확장한 것

# 2차원 배열을 리스트로 표현
arr = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

# 저장된 값 출력
print(arr[2][3])

# 저장된 값을 변경
arr[2][3] = 15

# 리스트 컴프리헨션을 활용
arr = [[i]*4 for i in range(3)]

배열 연산의 시간 복잡도

• 배열은 임의 접근이라는 방법으로 모든 위치에 있는 데이터에 단 한 번에 접근 가능
• 데이터에 접근하기 위한 시간복잡도는 O(1)

배열에 데이터를 추가하는 경우

(1) 맨 뒤에 삽입할 경우

• 다른 데이터 위치에 영향 X
• 시간복잡도 = O(1)

(2) 맨 앞에 삽입할 경우

• 기존 데이터들을 뒤로 한 칸씩 미는 연산 필요
• 시간복잡도 = O(N)

(3) 중간에 삽입할 경우

• 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산 필요
• 시간복잡도 = O(N)

배열을 선택할 때 고려할 점

• 할당할 수 있는 메모리 크기 확인
  • 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당 실패
  • 보통 정수형 1차원 배열은 1000만개, 2차원 배열은 3000*3000 크기가 최대
• 중간에 데이터 삽입이 많은지 확인
  • 배열은 선형 자료구조이므로 빈번하게 삽입하면 시간 초과 발생

코딩테스트 문제를 풀기 위해 "가장 효율적으로 해결하는 알고리즘" 필요

→ 효율적으로 푸는 것은 제한 시간과 관련이 있으며 문제를 빠르게 푸는 알고리즘 선택

알고리즘 수행 시간을 측정하는 방법

1) 절대 시간 측정 : 말 그대로 시간 측정

2) 시간 복잡도 측정 : 알고리즘 시작 순간부터 결괏값이 나올 때까지의 연산 횟수 측정

• 입력 크기 : 입력 크기가 다양하며 이에 따라 결과가 달라지므로 N으로 일반화
• 측정 결과 : 최선(best) / 보통(normal) / 최악(worst)
• 표현 방식 : 점근 표기법으로 사용

시간 복잡도 (Time Complexity)

알고리즘의 성능을 나타내는 지표로 입력 크기에 대한 연산 횟수

ex) 1차원 배열 검색

• 값을 가장 빨리 찾는 경우 : 검색 시작 위치에 찾을 값이 바로 위치한 경우
• 값을 가장 늦게 찾는 경우 : 찾으려는 값이 없거나 가장 마지막에 위치한 경우

점근적 표기법

입력 크기에 따른 연산 횟수의 추이를 활용해 시간 복잡도 표현

• 빅오(Big-O, O) 표기법 : 최악일 때 연산횟수 (수행시간의 상한)   ★ 주로 사용 ★
  • 모든 케이스를 통과해야하므로 주로 최악의 경우인 빅오를 기준으로 계산 
• 빅오메가(Big-Omega, Ω) 표기법 : 최선일 때 연산횟수 (수행시간의 하한)
• 빅세타(Big Theta, Θ) 표기법 : 보통일 때 연산횟수 (수행시간의 상한과 하한)

빅오 표기법의 종류

1. O(1) : 상수

입력 데이터 크기에 상관없이 일정한 시간 소요

ex) 스택의 Push / Pop

2. O(log N) : 로그

입력 데이터의 크기가 커질수록 처리 시간 감소

ex) 이진트리 / 순기능으로 이루어지는 재귀

3. O(N) : 선형

입력 데이터의 크기에 비례해 처리 시간 증가 (N크기만큼 처리 시간 증가)

ex) for문

4. O(N log N) : 선형 로그

입력 데이터가 많아질수록 처리 시간이 로그의 배만큼 증가

ex) 퀵 정렬(Quick Sort) / 합병 정렬(Merge Sort) / 힙 정렬(Heap Sort)

5. O( N² ) : 다항

입력 데이터를 N만큼 반복하고 그 안에서도 N만큼 반복하여 처리 시간이 급수적으로 증가

ex) 삽입 정렬(Insertion Sort) / 버블 정렬(Bubble Sort) / 선택 정렬(Selection Sort) / 이중 for문

6. O( 2ⁿ ) : 지수

입력 데이터가 많아질수록 처리 시간이 기하급수적으로 증가

ex) 피보나치(Fibonacci) 수열

코딩 테스트를 준비하기 위해 알고리즘 공부가 필요하다. 관련 강의와 책을 찾아보면서 정리할 예정이고 그 전에 코딩 테스트를 효율적으로 준비하기 위한 방법들을 정리해보았다. ("코딩테스트 합격자되기 파이썬편" 참고)

코딩 테스트 공부방법

"아는 것과 모르는 것을 정확하게 구분하기"

1. 기록

- 어떤 알고리즘을 적용하려고 했는지

- 근거는 무엇인지

- 알고리즘을 어떻게 코드로 만드려고 했는지

2. 시험 보듯이 공부

- 주어진 시간을 효율적으로 사용

- 긴장감을 연습

3. 짧은 시간으로 코딩테스트 통과는 불가능

- 최소 한 달에서 두 달 정도 집중해서 공부

4. 나만의 언어로 요약

- 이해한 뒤에 요약은 필수

- 제대로 이해했는지 확인하는 과정

문제를 분석하는 법

코딩 테스트 = 문제 풀이 능력을 확인하는 것

→ 문제 분석에 시간 투자 필요 (50%~60% 정도)

1. 문제를 쪼개서 분석

2. 제약 사항을 파악하고 테스트 케이스 추가
- 어떤 알고리즘을 사용할지 고민할 때 유용
- 추후 코드를 구현하는 단계에서 예외를 거르기 편리

3. 입력값을 분석
- 알고리즘의 시간 복잡도는 입력값이 결정
- 입력값의 크기를 확인하여 문제를 제한시간 내에 풀 수 있는지 확인

4. 핵심 키워드 파악

5. 데이터 흐름이나 구성 파악

의사코드로 설계하는 연습

의사코드란?

프로그램의 논리를 설명하고 알고리즘을 표현하기 위해 작성한 일종의 지침

의사코드의 원칙
1. 프로그래밍 언어로 작성하면 안된다.
2. 일반인도 이해할 수 있는 자연어로 작성해야 한다.
3. 일정한 형식이 없다. (자유롭게 작성)

의사코드를 작성하는 방법
1. 세부 구현이 아닌 동작 중심으로 작성
2. 문제 해결 순서로 작성
3. 충분히 테스트

※ 참고 자료 ※

https://wikidocs.net/221191

프로그래머스 Lv.2를 풀려고 하는데 난이도가 너무 어려워져 당황스러웠다. 친구가 알고리즘 공부부터 해야한다면서 코딩테스트 공부법 관련 자료를 보내줘서 나름대로 정리해서 공부해보려고 한다. 해야할 것이 너무 많은데 아무것도 안하고 있는 나...너무 대단하다...!!

1단계. 기본 문법 및 자료구조

어떤 언어로 코딩테스트를 볼 것인지 결정하고 기본적인 문법과 자료구조 공부

1) 프로그래밍 언어 선택

편하고 익숙한 프로그래밍 언어 선택하고 기본적인 문법 공부

2) 자료구조 공부

• 공부 순서
  • 배열 (Array)
  • 연결 리스트 (Linked List)
  • 스택 (Stack)
  • 큐 (Queue)
  • 해시 테이블 (Hash Table)
  • 트리 (Tree)
  • 힙 (Heap)
  • 그래프 (Graph)
• 공부 방법
  • 자료구조의 목적과 이론 이해 (책이나 강의 활용)
  • 자료구조의 구현 로직 따라하며 내부 작동원리 파악 (구글 검색)
  • 자료구조를 적용하여 문제 해결 (코딩 연습 사이트 이용)

2단계. 알고리즘 이론

문제를 풀기 위해 자주 사용되는 알고리즘 공부

1) 기본적인 개념 공부

• 이진 탐색 (Binary Search)
• 정렬 (Sorting)
• 완전 탐색 (Exhaustive Search)
• 재귀 (Recursion)
• 깊이 우선 탐색 (DFS)
• 너비 우선 탐색 (BFS)
• 동적 프로그래밍 (DP, Dynamic Programming)
• 백 트래킹 (Backtracking)

2) 빅오 표기법 (big-O notation) 마스터

• 하나의 문제를 해결하는 여러 방법의 효율성을 비교하기 위한 척도
• 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용

3단계. 알고리즘 문제 풀이

기본적인 이론을 공부하고 문제 풀이

1) 알고리즘 기출문제 플랫폼

• 국내
  • 백준 : https://www.acmicpc.net/problemset
  • 프로그래머스 : https://school.programmers.co.kr/learn/challenges
  • 코드업 : https://codeup.kr/problemset.php
• 해외
  • Hackerearth : https://www.hackerearth.com/practice/
  • Hackerrank : https://www.hackerrank.com/dashboard
  • Leetcode : https://leetcode.com/problemset/

2) 문제풀이 팁

• 간단한 문제부터 시작
• 시간을 정해놓고 시간이 지나도 못풀었을 경우 정답 확인
• 빅오 표기법으로 시간 및 공간복잡도 분석
• 풀고 난 후에는 다른 사람의 풀이 참고

※ Reference ※

코딩테스트 4단계 공부법 🌟

코딩테스트 준비(알고리즘 공부) 커리큘럼 🌟

→ 기본적인 단계 설정에 도움이 많이 된 블로그

자료구조를 공부하기 위한 5가지 단계

코딩테스트 대비를 위한 백준 문제 추천