1. 알고리즘(Algorithm)
1️⃣ 알고리즘이란?
어떤 문제를 해결하기 위한 명확하고 유한한 단계들의 집합
2️⃣ 알고리즘의 조건
- 입력(Input)이 있다
- 출력(Output)이 있다
- 단계가 명확하다
- 반드시 끝난다
3️⃣ 자주 쓰는 알고리즘 종류
1) 기본
- 최대/최소
- 누적 합
- 카운팅
- 조건 분기
2) 정렬
- 버블 정렬
- 선택 정렬
- 삽입 정렬
Arrays.sort()
3) 탐색
- 선형 탐색
- 이진 탐색
4) 자료구조 기반
- 스택
- 큐
- 해시(Map)
2. 버블 정렬(Bubble Sort)
1️⃣ 버블 정렬이란?
가장 단순한 정렬 알고리즘 중 하나
옆에 있는 두 값을 비교해서 필요하면 서로 교환(swap) 하며 정렬하는 방식
값들이 마치 거품이 위로 올라가듯이 가장 큰 값(또는 작은 값)이 단계적으로 끝쪽으로 이동한다 해서 ‘버블(Bubble)’이라는 이름이 붙음
2️⃣ 순서
- 리스트의 처음부터 끝까지 차례로 보면서
- 현재 값 > 다음 값이면 두 값을 교환한다.
- 한 바퀴 돌면 가장 큰 값이 맨 끝으로 "밀려난다".
- 이 과정을 리스트 길이만큼 반복하면 정렬 완료!
3️⃣ 실습
‘Practice > 7. (알고리즘) 크기 오름차순 정렬(Sort)’ 참고
package algo;
public class ChangeData3Me23 {
public static void main(String[] args) {
int[] arr = {7,6,5,4,3,2,1};
int temp;
int row1 = arr.length-1;
int row2 = arr.length-1;
int x;
int y;
for (int k = 0; k < row2; k++) {
x = 0;
y = 1;
for (int i = 0; i < row1; i++) {
if (arr[x] > arr[y]){
temp = arr[y];
arr[y] = arr[x];
arr[x] = temp;
}
x++;
y++;
}
row1--;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
}
4️⃣ 필기 정리
3. 바이너리 서치(Binary Search)
1️⃣ 바이너리 서치란?
정렬된 데이터에서 원하는 값을 매우 빠르게 찾는 알고리즘
리스트가 오름차순(또는 내림차순)으로 정렬되어 있다는 전제 조건이 필요
2️⃣ 순서
Arrays.sort("배열 변수 이름");로 정렬 먼저!
- *가운데 값(mid)**을 본다.
- 찾는 값(target)이
- 가운데 값보다 작으면 → 왼쪽 절반에서 다시 탐색
- 가운데 값보다 크면 → 오른쪽 절반에서 다시 탐색
- 딱 맞으면 탐색 종료!
→ 이 과정을 반씩 줄여가면서 반복하기 때문에 매우 빠름
3️⃣ 시간복잡도
O(log n)
→ 데이터가 2배로 늘어도 탐색 횟수는 조금밖에 늘지 않음
4️⃣ 실습
‘Practice > 12. (알고리즘) 바이너리 서치(Binary Search)’ 참고
package algo;
import java.util.Arrays;
public class BSearch06 {
public static void main(String[] args) {
int[] arr = {0, 1, 2, 9, 8, 7, 6, 5, 4, 3, 10}; // 11개 log11 => 3~4회 안에 끝남
Arrays.sort(arr); // {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
int n = 1;
int target = 6;
int startIndex = 0;
int endIndex = arr.length-1;
int mid = 0;
while (true){
mid = (endIndex-startIndex)/2 + startIndex;
if(target == arr[mid]){
System.out.println(target + "을 찾았습니다(" + n + "라운드): " + arr[mid]);
break;
}
if(target < arr[mid]){
endIndex = mid-1;
}
if(target > arr[mid]){
startIndex = mid+1;
}
n++;
}
}
}
5️⃣ 필기 정리
Share article