⚡ Array


📌 알고리즘(Algorithm)

🔷 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법, 주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법

  • 알고리즘 표현 방법

    1. 자연어
    2. 프로그래밍 언어
    3. 의사코드(Pesudocode)
    4. 순서도
  • 좋은 알고리즘이란?

    1. 정확성: 얼마나 정확하게 동작하는가
    2. 작업량: 얼마나 적은 연산으로 원하는 결과를 얻어내는가
    3. 메모리 사용량: 얼마나 적은 메모리를 사용하는가
    4. 단순성: 얼마나 단순한가
    5. 최적성: 더 이상 개선할 여지 없이 최적화 되었는가

🔷 시간 복잡도

  • 알고리즘의 작업량을 표현할 때 시간복잡도로 표현한다.
  • 실제 걸리는 시간을 측정
  • 실행되는 명령문의 개수를 계산
  • 빅-오(O) 표기법
    • 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시
    • 계수는 생략

      ❗ 당장 APS를 시작하는 단계에서는 크게 중요하진 않다... 나중에 자세히 공부하기로.

🌟 SW 문제 풀기 5단계
1. 지문을 읽는다.
2. 문제를 이해한다.
3. 문제를 손으로 푼다.
4. 푼 걸 코딩한다.
5. 디버깅하고 검증한다.


📌 배열(Array)

🔷 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조

  • 프로그램 내에서 여러 개의 변수가 필요할 때, 일일이 다른 변수명을 이용하여 자료에 접근하는 것은 매우 비효율적일 수 있다.
  • 배열을 사용하면 하나의 선언읕 통해서 둘 이상의 변수를 선언할 수 있다.
  • 단순히 다수의 변수 선언을 의미하는 것이 아니라, 다수의 변수로는 하기 힘든 작업을 배열을 활용해 쉽게 할 수 있다.

⭐ 1차원 배열

🔷 선언

  • 자료형: 배열을 이루는 자료형
  • 이름: 프로그램에서 사용할 배열의 이름
  • 길이: 배열을 이루는 원소의 수

🔷 접근

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) {
	// ...
}

📌 정렬(sort)

🔷 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값 혹은 그 반대의 순서대로 재배열하는 것

  • : 자료를 정렬하는 기준이 되는 특정 값

  • 대표적인 정렬 방식의 종류

    1. 버블 정렬(Bubble Sort)
    2. 선택 정렬(Selection Sort)
    3. 삽입 정렬(Insertion Sort)
    4. 카운팅 정렬(Counting Sort)
    5. 병합 정렬(Merge Sort)
    6. 퀵 정렬(Quick Sort)

📌버블 정렬(Bubble Sort)

🔷 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식

  • 정렬 과정
    1. 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동
    2. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬

      🌟 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양 같다하여 버블 정렬이다. 시간 복잡도는 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));
profile
Hodie mihi, Cras tibi

0개의 댓글

Powered by GraphCDN, the GraphQL CDN