해시 충돌과 체이닝해시 충돌(Hash Collision)은 해시 테이블에서 두 개 이상의 서로 다른 키가 동일한 저장공간(인덱스)에 할당되는 현상이다. 해시 테이블에서는 주어진 키를 해시 함수를 통해 테이블의 인덱스로 변환하는데, 해시 함수의 특성상 입력 값의 범위를 제한된 인덱스 범위로 축소시키므로 서로 다른 키 값이 같은 해시 값을 가질 수 있게 된다. 그리고 이로 인해 충돌이 발생하게 된다. 체이닝(Chaining)은 해시 충돌 문제를 해결하기 위한 대표적인 방법 중 하나로, 해시 테이블의 각 인덱스에 연결 리스트(Linked List)를 두어 충돌이 발생한 여러 키-값 쌍을 함께 저장하는 방법이다. 체이닝을 사용하면 충돌이 발생하더라도 데이터의 손실 없이 여러 데이터를 동일한 인덱스에 저장할 수 ..

분할 정복 (Divide and Conquer) 개요분할 정복은 문제를 더 작은 하위 문제로 나누고 각각을 해결한 뒤 결과를 합쳐 원래 문제를 해결하는 알고리즘인데요. 문제를 자연스럽게 나눌 수 있거나, 하위 문제 간의 중복 계산이 없는 복잡한 문제를 효율적으로 해결하는 데 자주 사용됩니다.  분할 정복의 3단계분할 (Divide)해결할 문제를 동일하거나 유사한 형태의 더 작은 하위 문제(Subproblem)로 나누는 과정하위 문제는 원래 문제보다 크기가 작아야 하며, 더 이상 나눌 수 없을 때까지 분할해야 한다정복 (Conquer)나눠진 하위 문제를 개별적으로 해결하는 과정하위 문제의 크기가 충분히 작으면 직접 계산과 같은 직관적인 방식으로 해결한다결합 (Combine)하위 문제의 해결 결과를 합쳐 원..

이분 탐색 (Binary Search) 개요이분 탐색은 정렬된 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법인데요. 이분 탐색을 수행하기 위해서는 다음 두 가지 조건을 만족해야 합니다.주어진 배열이 반드시 정렬되어 있어야 한다.무한 루프에 빠지지 않게 중간값을 잘 정해야 한다. 이분 탐색의 활용이분 탐색을 진행하게 되면, 시작값과 끝값이 엇갈릴 때까지 배열의 중간값이 찾는 값과 맞는지 확인하게 됩니다. 이때 배열의 중간값이 찾는 값이라면 그 위치를 반환해줍니다. 그런데 같지 않고 배열의 중간값이 찾는 값보다 작다면 배열을 중간으로 나눴을 때의 오른쪽에 있다는 뜻이므로 시작값을 갱신해주고, 반대의 경우라면 끝값을 갱신해줍니다.# 특정..

재귀 함수재귀 함수의 장단점장점코드가 직관적이고 간결해 이해하기 쉽다.단점호출 시 추가적으로 메모리를 사용해 메모리 소비가 많고, 과도한 호출 시 스택 오버플로우가 발생할 수 있다.반복문에 비해 실행 속도가 느리다. 피보나치 수열 반환 함수1항부터 n항까지의 피보나치 수열 반환 함수를 반복문/재귀문으로 각각 만들어보기. n이 0~2에 대한 처리는 두 방식 모두 같았다. 다만 n이 3이상일 때 원래 수열을 가지고 계속 덧붙여가느냐(반복문), 직전 n-1에 대한 피보나치 수열을 새롭게 불러와 덧붙여 반환하느냐(재귀문)의 차이가 있었다.반복문으로 구현한 피보나치 수열 반환 함수def pivo(n): if n == 0: return [] elif n == 1: return [..

백트래킹으로 순열, 조합 구하기백트래킹은 탐색 과정에서 불필요한 경로를 미리 차단하여 효율적으로 해를 찾는 기법인데요. 이를 활용하면 순열과 조합을 생성할 때, 가능한 모든 경우를 탐색하면서도 불필요한 연산을 줄일 수 있습니다.  순열 (같은 수 중복 X)n, m = map(int, input().split())arr = [x for x in range(1, n+1)]result = [0] * mvisited = [False] * ndef func(k): if k == m: print(*result) return for i in range(n): if not visited[i]: visited[i] = True res..

정수론 개요정수론은 정수의 성질 또는 정수가 등장하는 경우들을 연구하는 학문으로, 수학 체계에서 원점이자 정점 그 자체라고 할 수 있는데요. 기초 수준에서는 정수 그 자체보다는 자연수, 그 중에서도 소수를 중점적으로 다룹니다. 소수 (Prime Number)1과 자기 자신으로만 나눠지는 수. 즉, 약수가 2개이며 2부터 N-1까지의 수로 나눠지지 않는 수를 말합니다.소수 판정법합성수(소수가 아닌 수)  N에서 1을 제외한 가장 작은 약수는 √N 이하라는. 그렇기 때문에 2부터 √N 이하의 자연수로 해당 수를 나눠보면 됩니다. 만약 도중에 나누어 떨어지게 되면 합성수, 아니라면 소수가 됩니다.# 소수 판별 함수def is_prime(number): if number == 1: return..

완전 탐색 (Brute Force) 개요완전 탐색은 가능한 모든 경우의 수를 탐색하여 정답을 찾아내는 알고리즘인데요. 직관적이고 단순하지만, 경우의 수가 많아지면 시간 효율이 나빠질 수 있습니다. 완전 탐색의 종류단순 브루트 포스 (Brute Force)가능한 모든 방법을 단순하게 시도하는 기법반복문과 조건문을 활용해 모든 경우를 하나씩 검사ex) 비밀번호를 0000~9999까지 하나씩 대입하여 찾는 방식백트래킹 (Backtracking)되돌아가면서 모든 경로를 탐색하는 기법.탐색 중 해당 경로가 조건에 맞지 않으면 탐색을 중단하고 되돌아가 다른 경로를 탐색한다.불필요한 탐색을 줄이기 때문에 단순 브루트 포스보다 효율적ex) N-Queen 문제, 미로 찾기순열 (Permutation)서로 다른 n개의 원..

정렬 알고리즘 개요정렬 알고리즘은 데이터를 특정 기준에 따라 순서대로 정렬하는 방법을 의미합니다. 정렬 알고리즘에는 다양한 정렬 방식이 존재하는데요. 시간 복잡도와 공간 복잡도, 사용 목적에 따라 각각의 알고리즘을 적절히 선택해야 합니다. 기본 정렬 알고리즘기본적인 정렬 알고리즘에는 대표적으로 버블 정렬, 선택 정렬, 삽입 정렬이 있는데요. 비교적 단순한 로직을 사용하며, 주로 작은 데이터 집합에서 사용됩니다. 세 방식 모두 시간 복잡도가 O(N2)인 정렬 방법입니다.버블 정렬 (Bubble Sort)인접한 두 요소를 비교해 더 큰 값을 오른쪽으로 이동시키며 정렬데이터가 거의 정렬된 경우 비교적 빠르게 동작하지만, 최악의 경우 O(N2)의 시간 복잡도를 가짐선택 정렬 (Selection Sort)주어진 ..