알고리즘

[알고리즘] 정렬 - 버블 정렬(Bubble Sort) (자바/Java)

목차 버블 정렬 개념 인접한 두 개의 원소를 비교하며 정렬하는 알고리즘 정렬 과정 배열이 {30, 15, 2, 8, 21, 7}일 때를 가정한다. 원소는 자신의 오른쪽 값과 비교하기 때문에, 첫 사이클에서 비교할 마지막 index는 n-2이다. n-1(마지막 원소)와 비교를 하면 한 사이클이 끝나기 때문이다. 그렇게 한 사이클이 지나면 가장 큰 값이 배열의 오른쪽에 위치하여 다음 사이클에서는 비교 대상에서 제외된다. 두 번째는 30을 제외하고 다섯개의 원소만 비교하며 같은 과정을 반복한다. 이 사이클이 끝나면 두 번째로 큰 원소인 21이 자신의 위치를 찾아간다. 이렇게 반복하다보면 i가 1일때, 두 번째로 작은 원소인 7이 정렬되고, 자동으로 가장 작은 원소인 2는 비교 대상이 없기 때문에 모든 정렬이 ..

[백준] 1929 - 소수 구하기 (자바/Java): 에라토스테네스의 체

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 앞의 문제들처럼 풀었다가 시간 초과가 났다. 에라토스테네스의 체를 사용하는 문제였다. 에라토스테네스의 체는 소수를 구하는 알고리즘으로, 2부터 자기 자신을 제외한 자신의 배수들을 하나씩 지워나가는 알고리즘이다. 이때 끝까지 남아있는 수들이 소수에 해당한다. 그래서 먼저 배열을 선언하여 각 값을 초기화하였다. 이때 index를 그 값으로 사용하기 위해 N+1 크기의 배열을 선언하였다. 그리고 배열을 돌며 값이 0인 경우..