[묘공단] 코딩테스트합격자되기_1.배열
1. 배열
- 인덱스와 값을 일대일 대응해 관라하는 자료구조.
- 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근이 가능.
1-1. 배열 선언하기
#기본으로 구현하는법
arr= [0,1,2,3,4,5]
#리스트 생성자를 사용하는 방법
arr_1= list(range(6))
1-2. 배열과 차원
- 중첩 리스트 형태로 다차원 배열 표현 가능
#1차원 배열
arr = [1,2,3,4]
#2차원 배열
arr_1= [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
#3차원 배열
arr_2 = [[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]]
1-3. 배열의 효율성
- 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있음
- 데이터에 접근하기 위한 시간 복잡도는 O(1)
*시간복잡도*
알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기 (chulgil.me)
1-3-1. 맨 뒤에 데이터를 삽입할 경우
arr=[1,24,5]
배열이 1차원이고 arr[3] =2 를 할때 임의 접근을 바로 할 수 있으며 데이터를 삽입해도 다른 데이터 위치에 영향X
따라서 시간 복잡도는 O(1)
1-3-2. 맨 앞에 데이터를 삽입할 경우
위에 있는 배열있다고 생각을 해봅시다. 맨 앞에 2를 삽입을 한다면 기존에 있던 데이터들이 한 칸씩 밀려날 것이다.
데이터를 N개라 하면 시간 복잡도는 O(N)된다.
1-3-3. 중간에 삽입할 경우
중간 숫자인 24 앞에 데이터 2를 넣는다고 생각을 하면 24 뒤에 있는 데이터들은 뒤로 밀려나야할 것이다. 그러므로
밀어야할 데이터가 N으로 봤을때 시간복잡도는 O(N)이 된다.
*배열을 선택할때 고려할 점
- 배열을 사용하기 좋은 경우는 데이터에 자주 접근하거나 읽어야할 경우이다.
- 단점은 메모리 공간을 충분히 확보를 해야한다.
그래서 배열을 사용할 때 2가지를 고려해야한다.
1. 할당할 수 있는 메모리 크기를 확인해야한다.
- 보통 정수형 1차원 배열은 1000만개 , 2차원은 3000*3000크기를 최대로 생각
2, 중간에 데이터 삽입이 많은지 확인해야한다.
- 배열은 선형 자료구조이기 때문에 빈번하게 데이터를 중간이나 처음에 넣으면 시간복잡도가 높아져 시간초과가 된다.
1-4. 자주 활용하는 리스트 기법
- 파이썬에서 배열구조가 필요한 때 리스트를 활용을 한다.
1-4-1. 데이터 삽입하기
insert()메소드를 사용할 땐 첫번째 인수에 데이터를 삽입할 위를 받고 , 두 번째 인수에 삽입할 데이터를 받으면됩니다. 그러면 지정한 위치에 데이터를 삽입하고 뒤쪽 데이터를 하나씩 뒤로 이동시킨다.
1-4-2. 리스트에서 데이터 삭제
pop메소드를 사용할 때는 pop(삭제할 인덱스)를 넣어주면 된다.
remove()메소드는 pop()메소드와 달리 괄호에 인덱스가 아니라 특정 데이터를 넣어서 인덱스가 빠른 데이터를 삭제를 시키킨다. 예를들면 arr.remove(4)를 구현했을 때 '4'라는 데이터를 삭제하라는 뜻이다. 배열안에 4라는 데이터가 2개가 있다. 인덱스로보면 3 , 6 인덱스이다. 여기서 가장 앞에 있는 인덱스가 지워지는것이다.
2. 몸풀기 문제
2-1. 배열 정렬하기
-제약 조건-
1. 정수 배열의 길이는 2이상 10⁵이하입니다
2. 정수 배열의 각 데이터 값은 -100000이상100000이하입니다
arr = [1,-5,2,4,3]
arr2 = [2,1,1,3,2,5,4]
arr3 = [6,1,7]
#출력
[-5, 1, 2, 3, 4]
[1, 1, 2, 2, 3, 4, 5]
[1, 6, 7]
- 답안 -
def solution(arr):
arr.sort()
return arr