CS/알고리즘

병합정렬병합정렬 설명폰 노이만이 고안한 분할 정복알고리즘을 사용한 정렬 방법 중 하나이다.전반적인 성능은 퀵정렬보다 떨어지지만 데이터의 상태에 영향을 받지 않는 stable한 정렬이다.배열의 길이가 1이 될 때까지 쪼개고 (분할) 순서에 맞게 합친다 (정복, 병합)퀵정렬 보다 성능이 떨어지는 이유는?같은 시간복잡도 O(nlogn)을 가지지만 비교 하고 싶은 데이터의 크기만큼의 메모리를 할당해야한다. 반면 퀵정렬은 본인 배열의 메모리 안에서 값을 바꾸기 때문에 cpu 캐시 메모리를 더 효율적으로 사용할 수 있다.stable의 의미는?만일 A[20]=100, A[30]=100 일 때 퀵이나 힙정렬 같은 경우 서로의 위치가 바뀔 수 있지만, 병합정렬 같은 경우는 값이 같으면 연산을 하지 않기 때문에 메모리의 ..

개요알고리즘 글을 작성 하기에 앞서, 사실 요즘 워낙 좋은 세상이여서 GPT를 사용하면 대략적인 알고리즘을 해결할 수 있고, 특히 Spring을 활용한 다양한 프로젝트에서 생성형 ai를 많이 사용하는 바, 이러한 알고리즘 풀이가 크게 도움이 될까 생각이 든다.그러나 나의 굳어버린 뇌를 활성화 하기 위해 GPT에 의존하지 않고 알고리즘을 하나씩 풀어보고, 무엇보다 어려운 수학문제를 푸는 재미와 어떻게 이런 생각을 했지라는 감탄을 얻기 위해 알고리즘 문제를 하나씩 풀어나가겠다.그 처음문제가 바로 주어진 숫자 범위 내 소수 구하기 이다.소수란?소수란 1과 자기자신만으로 나눠지는 수다. 2, 3의 약수는 1과 자기 자신뿐으로 소수가 될 수 있고, 4의 약수는 1, 2, 4이므로 소수가 아니다. 1 또한 소수가 ..