본문 바로가기
728x90

[프로그래밍 공부]/Algorithm18

[Algorithm] 해시 테이블의 크기를 소수(Prime Number)로 해야하는 이유 https://stackoverflow.com/questions/3980117/hash-table-why-size-should-be-prime Hash table: why size should be prime? Possible Duplicate: Why should hash functions use a prime number modulus? Why is it necessary for a hash table's (the data structure) size to be a prime? From what I understand, it assures a ... stackoverflow.com 소수 : 1과 자기 자신으로만 나눌 수 있는 1보다 큰 양수 키 값이 하나의 값에 모이는 것을 줄여 더욱 균일한 분산을 .. [프로그래밍 공부]/Algorithm 2022. 1. 22.
[Algorithm] A* 길찾기 알고리즘 구현 미로에서의 길 찾기 벽 짚고 따라가기는 방법을 사용한다. 오른쪽 또는 왼쪽의 노드가 벽인지 판단하고 벽이라면 한칸 이동하는 방법을 사용한다. 그렇다면 결국에는 출구에 도착한다( 미로에 경우 ) 목적지에 도착은 하지만 최단경로는 찾을 수 없다. 최단경로 찾기 - 너비 우선 탐색 1. 시작 칸을 큐에 추가한다. 2. 시작 칸에 표시를 한다(방문했다는 증거) 3. 큐에서 맨 앞 노드를 뽑아낸다. 4. 현재 칸이 목표이면 알고리즘 종료. 5. 현재 칸의 자식들 중에 방문표시가 없으면 그 칸들의 이전 포인터를 현재포인터로 설정하고 큐에 추가한다. 6. 알고리즘이 종료될 때 까지 3~5 반복한다. 문제점 대각선이동과 수평이동의 크기가 같다고 판정하기 때문에 대각이동을 많이 하게 된다. 그렇게 되면 실제 거리를 재었.. [프로그래밍 공부]/Algorithm 2022. 1. 22.
[Algorithm] 재귀를 이용하여 하노이의 탑 해결하기 재귀( recursion )란? 어떠한 함수가 내부에서 자기 자신을 호출하는 것 하노이의 탑 재귀함수를 사용하여 하노이의 탑 문제를 해결하는 코드를 만들어보자. Hanoi 함수는 개수가 2개일 때를 생각하고 만들면 굉장히 간단하다. n 이 2일 때를 가정하면 2번째 돌을 바닥에 깔기 위해서는 자신의 위에 있는 돌을 전부 오픈된 공간으로 보내야한다. 따라서 1번째 돌을 옮겨야 하는데 결국 첫번째 돌은 n-1 번째 돌이다. 즉 n-1번째의 돌을 _open으로 보내는 것을 먼저하고( 함수 1번째 라인) 2번째 위치를 바꾼다( 함수 2번째 라인 ) 그리고 다시 n-1의 위치를 _dest로 옮겨야 하는데 n-1의 돌은 현재 _open 위치에 있다. 따라서 출발지점은 _open이 되며 목적지는 _dest이고 빈공간.. [프로그래밍 공부]/Algorithm 2022. 1. 22.
[Algorithm] Selection Sort : 선택 정렬, 선택 소트 ( 코드 포함 ) 배열의 가장 큰 원소를 찾아 배열의맨 끝자리에 있는 원소와 자리를 바꾼다. 맨 마지막 원소를 제외한 원소를 다시 찾는다. 이 작업을 반복하는 것이 선택정렬이다. 선택정렬의 수행시간(시간복잡도)은 어떠한 경우에도 O(n²) 이다. 매우 느리다. n번 반복하는 for문을 두번 반복하게 되는데 이는 n² 번 자료 확인을 하게 되는 것이다. 또한 모든 경우에 시간복잡도는 n²이 된다. 코드 정렬된 것을 볼 수 있다. [프로그래밍 공부]/Algorithm 2022. 1. 22.
[Algorithm] Bubble Sort : 버블 정렬, 버블 소트 ( 코드 포함 ) 선택정렬과 마찬가지로 가장 큰 원소를 끝의 자리로 옮기는 작업을 반복하는 정렬이다. 단, 끝의 자리로 보내는 방법이 다르다. 비교하면서 더 큰 숫자를 오른쪽으로 계속 보내게 되는데 이 결과 가장 큰 수가 가장 오른쪽에 간다. 버블정렬의 수행시간(시간복잡도)은 O(n²)이다. 따라서 숫자가 적을 때만 사용하자. [프로그래밍 공부]/Algorithm 2022. 1. 22.
[Algorithm] Insert Sort : 삽입정렬, 삽입소트 ( 코드 포함 ) 1개 짜리 배열에서부터 정렬을 시작한다. 1개짜리 배열을 정렬하고 2개짜리 배열을 정렬한다. n개까지 반복하는데 정렬하는 기준은 i 번째까지 정렬되어있다면 i+1 번째를 자신이 들어가야할 위치에 넣기까지 계속 뒤로 한칸씩 넘긴다. 삽입 정렬의 시간복잡도는 O(n²)이지만 배열의 정렬이 대부분 되어있다면 매우 빠른 속도로 정렬이 될 수도 있다 [프로그래밍 공부]/Algorithm 2022. 1. 22.
[Algorithm] Merge Sort : 병합 정렬, 병합 소트 ( 코드 포함 ) 입력된 배열의 중간지점을 찾은 뒤 반으로 나눈다. 그리고 나눈 전반부와 후반부를 각각 독립적으로 정렬한다 ( 재귀적으로 다시 반으로 정렬 ) 마지막으로 전반부와 후반부를 병합한다. 병합정렬의 수행시간은 평균 O(n*log n)이고 최악의 경우에도 O(n * log n) 이다. 코드 이전까지 정렬함수와 다르게 정렬하고자 하는 부분의 시작인덱스와 끝 인덱스를 넣는다. 재귀적으로 되어있는데 merge는 분열되어 각각 정렬된 배열을 하나로 합치는 역할을 한다. merge함수 결과 [프로그래밍 공부]/Algorithm 2022. 1. 22.
[Algorithm] Heap Sort : 힙 정렬, 힙 소트 ( 코드 포함 ) 힙 소트는 힙이라는 자료구조를 이용하여 정렬하는 방식이다. 힙은 '각 노드의 값은 자신의 자식 노드의 값보다 항상 작다' 를 만족하는 자료구조이다. 따라서 힙의 머리부분은 항상 제일 작다. 정렬을 위해서 궂이 리스트를 이용하여 힙을 만들 필요는 없고 배열로 만들면 된다. 주어진 배열을 힙으로 만든 뒤 가장 작은 값을 차례로 줄여 힙의 크기를 감소하는 방법을 사용한다. 힙 배열에서 a[k]의 자식의 위치는 a[k]와 a[k+1]이다. k가 왼쪽, k+1이 오른쪽이다. a[k]의 부모노드는 a[k/2]이다. 먼저 결과 샷 템플릿을 이용하여 범용성을 구현하기엔 너무 귀찮고 어디서 재활용할 것도 아니기 때문에(퀵소트 *를 이미 템플릿으로 짜놔서 그거 쓸래..) 그냥 int 배열을 인자로 받는 힙 정렬을 구현하였.. [프로그래밍 공부]/Algorithm 2022. 1. 22.
728x90

티스토리툴바