알고리즘의 성능
- 알고리즘의 작업량을 표현할 때 시간복잡도로 표현한다
- 시간 복잡도
실제 걸리는 시간을 측정
실행되는 명령문의 개수를 계산
시간 복잡도 = 빅-오(O) 표기법
- 빅-오 표기법(Big-Oh Notation)
- 시간 복잡도 함수 중 가장 큰 영향력을 주는 n에 대한 항만을 표시
- 계수는 생략하여 표시
O(3n + 2) = O(3n) = O(n)
최고차항만 선택 후 계수 3 제거
배열
일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조
배열의 필요성
- 여러 개 변수 필요할 때, 다른 변수 명 이용해 접근하는 것은 비효율적
- 하나의 선언을 통해 둘 이상의 변수를 선언할 수 있다
- 변수로 하기 힘든 작업을 배열 활용해 쉽게할 수 있다
배열활용 예제
상자들이 쌓여있는 방에서 90도 회전해 중력의 영향으로 상자가 낙하한다. 낙차가 가장 큰 상자를 구해라
-
입력값 받기
list(map(int, input().split())) -
배열 요소 중 같거나 높은 애와의 거리가 얼마인지 구한다
요소의 오른쪽에 같거나 큰 애가 몇 개?
그리고 그 개수 중 가장 큰 값을 리턴
- 입출력을 제외한 나머지 내장함수 사용 금지 (max, min 등)
- 최댓값 찾기
첫번째 원소를 가장 큰 값으로 가정
배열은 순회하면서 최대값이라고 생각한 애보다 요소가 크면 최대값을 재할당
box[i]의 오른쪽인 box[i + 1] ~ box[n - 1]
j 부터
ans = [0] * 10
j 가 배열을 순회하면서 더 작은 요소의 개수를 찾아서 ans 배열에 넣어준다'
정렬
2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값, 혹은 그 반대의 순서대로 재배열 하는 것
- 키
자료를 정렬하는 기준이 되는 특정 값
정렬 방식의 종류
- 버블 정렬
- 카운팅 정렬
- 선택 정렬
위 세개는 꼭 기억
버블 정렬
인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
- 정렬 과정
첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동
한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
물위에 올라오는 거품 모양과 같다고 보아 버블 정렬
