- 쉽게 생각하면 배열
- 원하는 위치의 값을 얻기 위해 O(1)의 시간복잡도로 얻을 수 있는 자료구조
왜 배열은 1번째부터가 아닌 0번째부터 시작할까?
- 컴퓨터 과학자 다익스트라(Dijkstra)가 코드의 가독성과 오류를 덜 일으키는 최적의 방안이라 제시했기 때문이다.
ArrayList의 삽입과 삭제
- 위 그림처럼 ArrayList 3번째 위치에 25를 삽인한다고 했을때,
- 삽입할 위치만큼 공간을 확보하여 기존의 원소들을 뒤로 이동시킨다.
- ArrayList에서 원하는 값을 추가하고자 할 떄는 배열의 크기가 n일 때 최대 n번으 ㅣ이동을 통해 자리를 만들어 주어야 한다.
- 따라서 시간복잡도는 O(n)이 된다.
- 다른 예로 ArrayList에 3번째 위치의 원소를 삭제한다고 할때,
- 먼저 원하는 위치의 원소를 빈 값으로 바꾸어준 뒤, 삭제한 위치의 이후에 있는 값들을 왼쪽으로 이동시켜 준다.
=> 그림에서는 3번째 위치의 25를 삭제한뒤 4, 5, 6번째 원소들이 3, 4, 5번째 위치로 이동했다. - ArrayList에서 원하는 값을 삭제하고 할 때는 배열의 크기가 n일 때 최대 n번의 이동이 필요하다.
- 따라서 시간복잡도는 O(n)이다.
삽입과 삭제 후 원소들의 위치를 바꾸지 않으면 되지 않을까??
- 삽입이 많을 시에는 배열의 크기가 늘어나며, 삭제 후 원소의 위치를 바꾸지 않는다면 배열의 순서가 보장되지 않으므로 원치 않는 값을 지울 수 있다.
=> 따라서 삽입과 삭제 후에는 반드시 원소의 위치를 바꾸어 주어야 한다.
- 삽입이 많을 시에는 배열의 크기가 늘어나며, 삭제 후 원소의 위치를 바꾸지 않는다면 배열의 순서가 보장되지 않으므로 원치 않는 값을 지울 수 있다.
- ArrayList의 사용법을 간략히 살펴보면
=> "변수명 = [ ]"으로 리스트를 통해 사용된다. - Python에서는 ArrayList만을 위한 자료구조가 따로 존재하지 않으며, "변수명 = [ ]"는 ArrayList를 대체하기 위한 자료구조이다.
예제 1. ArrayList를 사용하는 예제 - 최소, 최대
[문제]
N개의 정수가 주어진다. 이때, 최솟값과 최대값을 구하는 프로그램을 작성하시오.[입력]
첫째 줄에 정수의 개수 N(1 <= N <= 1,000,000)이 주어진다. 뚤째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.[출력]
첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.
예제 입력 예제 출력 5 7 35 20 10 35 30 7
- n 개의 정수를 입력받기 위해 배열을 사용하지 않고 하나하나 전부 변수를 만들어 입력받는다면 n 개의 변수를 직접 만들어야 한다.
one = int(input())
two = int(input())
three = int(input())
four = int(input())
...
bigNumber = int(input())-
이는 매우 비효율적인 일이기 때문에, 하나의 변수만으로 모든 데이터를 저장하기 위해 배열을 사용한다.
-
위의 예제에서,
5
20 10 35 30 7을 입력 받기 위한 코드는 아래와 같다.
n = int(input())
array_list = list(map(int, input().split()))- 최댓값과 최솟값을 찾기 위해서는 배열 안에 수들을 하나하나 순회해보며 가장 큰 값과 가장 작은 값을 찾으면 된다.
- 이를 위해 최댓값을 저장할 변수 max_num 을 만들고, 배열의 첫 번째 값으로 초기화해 둔다.
max_num = array_list[0]- 최솟값을 저장할 변수 min_num 을 만들고, 배열의 첫 번째 값으로 초기화해 둔다.
min_num = array_list[0]- 그 후 최댓값을 찾기 위해 배열을 순회하며 현재 배열값 num 이 max_num 보다 크다면 max_num 값을 num 값으로 바꿔준다
max_num = num- 최솟값을 찾기 위해 배열을 순회하며 현재 배열값 num 이 min_num 보다 작다면 min_num 값을 num 값으로 바꿔준다
min_num = num해답코드
n = int(input())
array_list = list(map(int, input().split())) # 정수 n과 n개의 정수를 입력받는다.
max_num = array_list[0]
min_num = array_list[0] # 최댓값과 최솟값을 저장하기 위한 변수를 생성한다.
for num in array_list: # for문을 이용하여 배열을 순회한다.
if num > max_num:
max_num = num # 현재 배열값 num이 max_num값보다 크다면 max_num값을 num값으로 바꿔준다.
if num < min_num:
min_num = num # 현재 배열값 num이 min_num값보다 작다면 min_num값을 num값으로 바꿔준다.
print(min_num, max_num) # 최솟값과 최대값을 출력한다.예제 2. 2차원 배열 사용 예제 - 나는 요리사다
[문제]
"나는 요리사다"는 다섯 참가자들이 서로의 요리 실력을 뽐내는 티비 프로이다. 각 참가자는 자신있는 음식을 하나씩 만들어오고, 서로 다른 사람의 음식을 점수로 평가해준다. 점수는 1점부터 5점까지 있다.각 참가자가 얻은 점수는 다른 사람이 평가해 준 점수의 합이다. 이 쇼의 우승자는 가장 많은 점수를 얻은 사람이 된다.
각 참가자가 얻은 평가 점수가 주어졌을 때, 우승자와 그의 점수를 구하는 프로글맹르 작성하시오.
[입력]
총 다섯 개 줄에 각 참가자가 얻은 네 개의 평가 점수가 공백으로 구분되어 주어진다 첫 번째 참가자부터 다섯 번째 참가자까지 순서대로 주어진다. 항상 우승자가 유일한 경우만 입력으로 주어진다.[출력]
첫째 줄에 우승자의 번호와 그가 얻은 점수를 출력한다.
예제 입력 1 예제 출력 1 5 4 4 5 4 19 5 4 4 4 5 5 4 4 5 5 5 4 4 4 4 5
예제 입력 2 예제 출력 2 4 4 3 3 2 17 5 4 3 5 5 5 2 4 5 5 5 1 4 4 4 4
- 예제 입력 1을 보면,
첫 번째 참가자 = 5 4 4 5 -> 합 18
두 번쨰 참가자 = 5 4 4 4 -> 합 17
세 번째 참가자 = 5 5 4 4 -> 합 18
네 번째 참가자 = 5 5 5 4 -> 합 19
다섯 번째 참가자 = 4 4 4 5 -> 합 17- 네 번쨰 참가자가 가장 많은 점수를 받았기에 다음을 출력하면 정답이 된다.
4 19- 이를 위해 2차원 배열을 입력받는 방법을 이용한다
변수명 = [list(map(int, input().split())) for _ in range(참가자수)]- 그리고 각 참가자가 총 몇 점을 받았는지 저장해서 가장 높은 점수를 받은 사람을 출력하면 된다.
해답코드
# 각 참가자들의 점수를 2차원 배열 형태로 입력받는다.
human = [list(map(int, input().split())) for _ in range(5)]
humanScore = [0] * 5 # 참가자들의 총합 점수를 저장하기 위한 배열을 생성한다.
score = 0 # 최대 점수를 저장하기 위한 변수를 생성한다.
for i in range(5): # 0부터 4까지 for문을 탐색해 참가자들을 순회한다.
sum = 0 # 참가자들의 점수를 저장하기 위한 변수 sum 이다.
for j in range(4): # 4번의 평가를 받았으므로, 0~3까지 for문을 실행한다.
sum += human[i][j] # sum에 참가자가 받은 점수를 더해준다.
humanScore[i] = sum # 해당 참가자의 총 점수는 sum에 저장한다.
score = max(score, sum) # 점수의 최댓값을 score에 저장한다.
# 참가자의 총 점수가 score(최대 점수)라면 "i + 1"과 score(최대 점수)를 출력하고 for문을 탈출한다.
for i in range(5):
if humanScore[i] == score:
print(i + 1, score)
break예제 3. 삽입과 삭제가 많은 ArrayList의 잘못된 사용 예 - 크게만들기
[문제]
N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.[입력]
첫째 줄에 N과 K가 주어진다 ( 1<= K <= N <= 500,000 )
둘째 줄에 N자리 숫저가 주어진다. 이 수는 0으로 시작하지 않는다.
[출력]
입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.
예제 입력 1 예제 출력 1 4 2 94 1924
예제 입력 2 예제 출력 2 7 3 3234 1231234
예제 출력 3 예제 출력 3 10 4 775841 4177252841
- 이 문제는 탐욕법 알고리즘과 스택 자료구조가 무엇인지 알아야 정확한 풀이를 할 수 있다.
- 배열을 사용하여 데이터의 삽입과 삭제가 많을 때 시간 복잡도에 문제가 생길 수 있다는 점을 소개하며 잘못된 정담을 코드로 보여주는 것이다.
- 가장 큰 수를 만들기 위해서는 수를 지우는 가능한 횟수 k가 남아 있을 때, 수의 index 위치에 해당하는 값보다 왼쪽에 있는 수가 커야 한다.
n = 4, k = 2
num = 1924- 위와 같은 경우, 처음에 1을 순회하고, 그 다음 9를 순회할 때 해당 index 위치보다 왼쪽에 있는 1은 9보다 작으므로 지워야 한다.
num = 924, k = 1- 그 다음 2를 순회할 때 9는 2보다 크므로 넘어가고, 그 다음 4를 만났을 때 해당 index 위치보다 왼쪽에 있는 9, 2 중에 2는 4보다 작으므로 지운다.
num = 94, k = 0- 예외적으로
n = 4, k = 2
num = 4321- 위와 같이 해당 인덱스 위치 값의 왼쪽 수보다 모두 작아 k가 남는다면 끝에서부터 지우면된다.
num = 43, k = 0- 위의 로직을 코드화하면 아래와 같다(아래 코드는 해답코드가 아니며 크게 의미가 없으므로 코드 설명은 생략한다.)
n, k = map(int, input().split())
number = list(input())
for i in range(0, len(number)):
while number[i] > number[i - 1] and k:
k -= 1
del number[i - 1]
number.insert(0, 'a')
answer = ''
for i in range(0, len(number) - k):
if number[i] != = 'a':
answer += number[i]
print(answer)- 하지만 이 코드는 시간 초과가 된다.
- 이 문제를 통해 배열의 삽입과 삭제가 빈번할 때 시간복잡도에 유의하며 사용해야 한다는 것을 명심!
데이터 사이언스 입문