컴퓨터 과학(CS)/알고리즘8 해시 알고리즘(hash algorithm) 해시 함수, 해시 알고리즘 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 여러가지 해시 알고리즘이 있는데 대표적으로 SHA 시리즈와 MD5가 있다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 해시라고 한다. 해시의 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다. 해시 테이블 해시함수를 사용하여 키를 해시 값으로 변환하고, 이 해시 값을 색인(index)으로 삼아 키와 데이터(value)를 저장하는 자료구조를 말한다. 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다. 해시 충돌(Hash Collision) 해시 충돌이란 해시 함수가 서로 다른 두 개.. 2022. 3. 2. 합병 정렬(merge sort) 모두를 위한 컴퓨터 과학(데이비드말란 교수님) 강의 1.1. 합병 정렬 합병 정렬(병합 정렬)은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가는 정렬을 하는 방식이다. 분할 정복(divide and conquer) 알고리즘의 하나로 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다 1.2. 합병 정렬 구현 1) 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. n개의 원소가 있을 때 배열을 계속해서 반으로 나누기 때문에 호출되는 함수의 개수는 log N개 2) 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 다시 분할한다. 3) 결합(Combine): 정렬.. 2022. 1. 12. 재귀(Recursion)와 스택(stack)영역 다른 알고리즘과는 다르게 제목에 재귀와 함께 스택 영역을 적어놓은 이유가 있다. 재귀 함수를 호출하는 것과 메모리 스택 영역의 연관성은 마지막 부분에 정리하겠다. 1.1 재귀(Recursion) * 위키피디아 정의 컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 프로그래밍에서는 함수가 자기 자신의 함수를 호출하도록 구현한다. 보통 알고리즘을 구현할 때, 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 더 직관적이고 이해하기 쉬운 경우가 많다. 재귀는 마치.. 무의식 속의 무의식으로 들어갔다가 결국 현실로 되돌아오는 인셉션과 비슷하다. 용어만으로는 헷갈리니 파이썬 코드로 알아보자. def recursion(): print("난 재귀 함수야") recursion() .. 2022. 1. 9. 버블 정렬(bubble sort) 참고: 누구나 자료 구조와 알고리즘(개정2판) 4장, 모두를 위한 컴퓨터 과학(데이비드말란 교수님) 강의 정렬 알고리즘 시각화 사이트 https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html 4.1. 버블 정렬 이번 4장에서는 현실적인 문제를 푸는 코드를 작성해보고, 빅 오를 사용해 작성한 알고리즘을 평가해보겠다. 정렬 알고리즘은 컴퓨터 과학 분야에서 폭넓게 연구된 주제이며, 이러한 알고리즘은 모두 다음 문제를 해결한다. 정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까? 4장과 5장에서는 이런 정렬 알고리즘을 많이 다룰 것이다. 매우 기본적인 정렬 알고리즘인 버블 정렬부터 알아본다. 버블 정렬은 두 인접한 원소의 대소.. 2022. 1. 9. 선택 정렬(selection sort) 참고: 누구나 자료 구조와 알고리즘 2장, 모두를 위한 컴퓨터 과학(하버드 데이비드말란 교수님) 강의 1.1. 선택 정렬 정렬을 위한 알고리즘 중 선택 정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 선택해놓은 다음, 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다. 선택 정렬은 버블 정렬처럼 쌍을 이뤄 앞/뒤 순서를 교환하지 않는다. 매번 가장 작은 값을 선택해놓는 것이 목표다. 즉, 반복할 때마다 가장 작은 수를 선택하는 것이다. 버블 정렬은 인접한 두 원소를 비교할 때마다 교환이 발생하지만, 선택 정렬은 교환 횟수를 최소화한다. 1.2. 선택 정렬 구현 1부터 N개의 원소가 있다고 하자. (인덱스 번호로는 0번째부터 N-1번째에 원소가 있는 것) for .. 2022. 1. 8. 빅 오 표기법 참고: 누구나 자료 구조와 알고리즘(개정2판) 3장 3.1. 빅 오 표기법: 원소가 N개일 때 몇 단계가 필요할까? 에 대한 답 1장과 2장에서는 알고리즘의 효율성을 결정하는 주된 요인이 알고리즘 수행에 필요한 단계 수임을 밝혔다. 그러나 어떤 알고리즘은 '7단계의 알고리즘' '120단계의 알고리즘'으로 표시하기엔 장황하므로 알고리즘의 시간 복잡도(효율성)를 일관되고 정량화하여 나타내기 위한 방법으로 빅 오 표기법을 사용하게 되었다. 앞에서 배운 선형 검색을 빅 오 표기법으로 표현해보자. 배열에 원소가 N개가 있을 때, 선형 검색에서 최악의 경우 배열의 원소 수만큼의 단계가 필요했다. 빅 오 표기법으로 '빅 오 N', '차수 N' , '오 N' 이라 표현한다. O(N) O(N)은 알고리즘에 N단계가 필요.. 2021. 12. 28. 선형 검색, 이진 검색 참고: 누구나 자료 구조와 알고리즘 2장, 모두를 위한 컴퓨터 과학(데이비드말란 교수님) 강의 1장에서는 배열이나 집합처럼 매우 유사해 보이는 두 자료 구조라도 효율성이 크게 다를 수 있음을 보았다. 2장에서는 어떤 자료 구조를 이미 결정했더라도 효율성에 영향을 미칠 수 있는 알고리즘에 대해 살펴본다. 알고리즘이란 단순히 어떤 문제를 풀어내기 위한 명령어 집합이다. 새 알고리즘을 분석하기 위해 자료 구조 하나를 살펴보자. 2.1. 정렬된 배열 정렬된 배열(ordered array)은 값이 항상 순서대로 있어야 한다. 일반 배열이 [8, 17, 3, 202] 일 때, 정렬된 배열은 [3, 17, 80, 202]라 할 수 있다. 정렬된 배열의 강력함은 검색 연산에서 드러난다. 전형적인 배열의 특정 값을 찾으.. 2021. 12. 27. 누구나 자료 구조와 알고리즘(개정2판) 1장 1. 자료 구조가 중요한 까닭 자료 구조: 자료를 조직하고 저장하는 방법이다. 자료(데이터)를 어떻게 조직하느냐에 따라 프로그램의 실행 속도는 천차만별로 달라질 수 있다. ex. 책장에 책을 어떻게 진열할 것인가? 연도 순, 알파벳 순, 가로 정렬 등등 자료 구조와 다르게, 알고리즘은 원하는 책을 어떤 방법으로 찾을 것인가? 1.2. 배열 번호(인덱스)와 번호에 대응하는 값들로 이루어진 자료 구조를 나타낸다. 인덱스가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다. 자료 구조에 사용되는 4가지 기본 연산이 있다. 읽기: 자료 구조 내 특정 위치를 찾아보는 것. 배열에서는 특정 인덱스의 값을 찾아보는 것을 뜻한다. 검색: 자료 구조 내 특정 값을 찾는 것. '사과'가 과일 목록에 있는지.. 2021. 12. 27. 이전 1 다음
