🔷 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법, 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법
알고리즘 표현 방법
자연어
프로그래밍 언어
의사코드(Pesudocode)
순서도
좋은 알고리즘이란?
정확성
: 얼마나 정확하게 동작하는가작업량
: 얼마나 적은 연산으로 원하는 결과를 얻어내는가메모리 사용량
: 얼마나 적은 메모리를 사용하는가단순성
: 얼마나 단순한가최적성
: 더 이상 개선할 여지 없이 최적화 되었는가🔷 시간 복잡도
빅-오(O) 표기법
❗ 당장 APS를 시작하는 단계에서는 크게 중요하진 않다... 나중에 자세히 공부하기로.
🌟 SW 문제 풀기 5단계
1. 지문을 읽는다.
2. 문제를 이해한다.
3. 문제를 손으로 푼다.
4. 푼 걸 코딩한다.
5. 디버깅하고 검증한다.
🔷 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
🔷 선언
자료형
: 배열을 이루는 자료형이름
: 프로그램에서 사용할 배열의 이름길이
: 배열을 이루는 원소의 수🔷 접근
nums[0] = 10;
nums[idx] = 20;
🔷 순회
// 정방향 순회
// 1. 일반적인 for 문
for(int i=0; i < arr.length; i++) {
System.out.println(arr[i]);
}
// 2. foreach: 값을 복사해서 쓰는 것이므로 readonly
for(int i : arr) {
System.out.println(i);
}
// 역방향 순회
// 1. 마지막 인덱스부터 돌리는 for 문
for(int i = arr.length-1; i >= 0; i--) {
System.out.println(arr[i]);
}
// 2. 인덱스를 직접 조정하여 순회
int N = arr.length;
for(int i =0; i<N; i++) {
System.out.println(arr[N-i-1]);
}
// 어느 한 지점부터 양옆으로 순회
// while문
int start = 3;
int i = 1;
while(i > arr.length) {
// ...
}
🔷 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값 혹은 그 반대의 순서대로 재배열하는 것
키
: 자료를 정렬하는 기준이 되는 특정 값
대표적인 정렬 방식의 종류
버블 정렬(Bubble Sort)
선택 정렬(Selection Sort)
삽입 정렬(Insertion Sort)
카운팅 정렬(Counting Sort)
병합 정렬(Merge Sort)
퀵 정렬(Quick Sort)
🔷 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
🌟 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양 같다하여 버블 정렬이다. 시간 복잡도는 O(n^2)
int arr [] = {1, 6 ,3 ,21, 4444, 14, 17};
// 배열 길이-1만큼의 반복
for(int i = 0; i < arr.length-1 ; i++) {
// 인접한 요소를 하나씩 비교하면서 오름차순 정렬
for(int j =1; j < arr.length-i; j++) {
if(arr[j-1] > arr[j]) {
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
}
System.out.println(Arrays.toString(arr));