ㅇ 정렬이란? 데이터를 정해진 기준에 따라 배치해 의미 있는 구조로 재설정하는 것이다. 즉, 내림차 순이나 오름차 순으로 다시 배치하는 것이다. ㅇ 정렬의 종류 ① 버블 정렬(Bubble Sort) : 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 ② 선택 정렬(Selection Sort) : 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 ③ 삽입 정렬(Insertion Sort) : 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 ④ 퀵 정렬(Quick Sort) : pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 ⑤ 병합 정렬(Merge Sort) : 이미 정렬된 부분 집합들을 효율적으로 병합해 ..
https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net ㅇ 문제 입력한 수를 만족하는 소수의 합을 구하는 문제이다. 소수를 찾아야 하니 에라토스테네스의 체를 이용해여 접근한다. ◆ 핵심 아이디어 1. 입력값까지의 소수를 구해야 한다. 2. 입력값의 소수의 합을 출력한다. 3. 소수의 합(골드바흐 파티션)이 여러 개일 경우, 두 소수의 차이가 가장 적은 것을 출력한다. 4. 소수는 작은 것부터 출력한다. ◆ 에라토스테네스의 체 htt..
ㅇ 소수란? 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 예를 들어 10보다 작은 소수는 2, 3, 5, 7이 있다. ㅇ 소수 찾기 소수를 찾는 방법은 총 3가지가 있다. 1. N을 N보다 작은 자연수로 모두 나누기 2. N의 제곱근보다 작은 자연수로 모두 나누기 3. 에라토스테네스의 체 이용하기 ㅇ N보다 작은 자연수로 나누기 첫번째 방법은 매우 간단하면서 기초적인 방법이다. N보다 작은 수로 모두 나누어 만약 나누어 떨어지는 것이 없다면 N은 소수일 것이다. 예를 들어보자. 만약 6이 주어졌을 때 1보다 크고 6보다 작은 수, 2, 3, 4, 5로 모두 나누어보자. 6 / 2 = 3 6 / 3 = 2 6 / 4 = 1 ... 2 6 / 5 = 1 ... 1 6은 2와 3으로 나누어 떨어..
ㅇ 알고리즘이란? 컴퓨터가 특정 문제를 해결하는 방식이다. 물론 특정 문제를 해결하는 방식이 많이 있지만, 그중에서도 효율적인 방식을 찾는 것이 중요하다. 이러한 효율적인 알고리즘을 찾는 기준은 시간복잡도이다. ㅇ 시간복잡도란? 알고리즘의 시간 복잡도는 성능을 나타내는 척도 중 하나로 알고리즘의 수행 시간을 나타낸다. 즉, 프로그램이 얼마나 많은 시간이 걸리는지를 나타내는 것이다. 다시 말하면, 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주한다. 시간복잡도가 큰 알고리즘은 작은 데이터에서도 느리게 동작하는 반면, 시간복잡도가 작은 알고리즘은 빠르게 동작한다. ㅇ 시간복잡도 유형 이러한 시간복잡도를 정의하는 3가지 유형이 있다. ①..
