"이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편 5장의 써머리입니다."

05. 배열

1) 배열 개념

배열(Array) : 인덱스와 값을 일대일 대응해 관리하는 자료구조

임의 접근(Random Access) : 데이터에 한 번에 접근 가능해서 어디에 있는지 알면 빠르게 접근하는 방식

배열 선언

• 파이썬의 경우 배열 지원 X → 리스트 문법 지원

(1) 일반적인 방법

arr = [0, 0, 0, 0, 0, 0]
arr = [0] * 6

(2) 리스트 생성자를 사용하는 방법

arr = list(range(6)) #[0, 1, 2, 3, 4, 5]

(3) 리스트 컴프리헨션을 활용하는 방법

arr = [0 for _ in range(6)] #[0, 0, 0, 0, 0,0]

• 리스트 컴프리헨션(List Comprehension) 참고

: 기존 리스트를 기반해 새 리스트를 만들거나, 반복문, 조건문을 이용해 복잡한 리스트 생성하는 등 다양한 상황에서 사용할 수 있는 문법

배열과 차원

배열은 다차원 배열을 사용할 때도 있지만 컴퓨터 메모리의 구조는 1차원이므로 다차원 배열도 실제로는 1차원 공간에 저장. 즉, 배열은 차원과 무관하게 메모리에 연속 할당됨

리스트 컴프리헨션을 활용한 2차원 배열 선언

# 크기가 3 * 4인 리스트 선언
arr = [[i]*4 for i in range(3)] # [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]

2) 배열의 효율성

배열 연산의 시간 복잡도

배열의 데이터에 접근하기 위한 시간 복잡도는 O(1)

배열에 데이터를 추가, 삭제 연산에 대한 시간 복잡도는 다름

(1) 맨 뒤에 삽입할 경우

데이터를 삽입해도 다른 데이터 위치에 영향 X

임의 접근이 가능하여 시간 복잡도는 O(1)

(2) 맨 앞에 삽입할 경우

기존 데이터를 뒤로 한칸씩 밀어야 하기 때문에 연산 필요

데이터 개수를 N개로 일반화하면 시간 복잡도는 O(N)

(3) 중간에 삽입할 경우

현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산 필요

밀어야 하는 데이터 개수가 N개라면 시간 복잡도는 O(N)

배열로 데이터를 저장하기 전에 항상 이런 비용을 생각해보는 것이 좋음

배열을 선택할 때 고려할 점

(1) 할당할 수 있는 메모리 크기를 확인

배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당 실패↑

보통 정수형 1차원 배열 - 1000만 개, 2차원 배열 - 3000 * 3000 크기를 최대로 생각

(2) 중간에 데이터 삽입이 많은지 확인

배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도↑

3) 자주 활용하는 리스트 기법

리스트에 데이터 추가

(1) append() 메서드로 데이터 추가

맨 끝에 데이터 추가하려면 append() 사용

my_list.append(2)

(2) +연산자로 데이터 추가

+연산자로 리스트 맨 끝에 다른 리스트의 데이터 추가 가능

my_list = [1, 2, 3]
my_list = my_list + [4, 5]

(3) insert() 메서드로 데이터 삽입

insert() 사용하면 특정 위치에 데이터를 삽입 가능

eg) insert(데이터를 삽입할 위치, 삽입할 데이터)

my_list = [1, 2, 3, 4, 5,]
my_list.insert(2, 9999) # [1, 2, 9999, 3, 4, 5]

리스트에서 데이터 삭제

(1) pop() 메서드로 특정 위치의 데이터 팝

eg) pop(팝할 데이터의 인덱스)

삭제하고 삭제한 데이터의 값을 반환

my_list = [1, 2, 3, 4, 5]
poped_element = my_list.pop(2) # 3
print(my_list) # [1, 2, 4, 5]

(2) remove() 메서드로 특정 데이터 삭제

remove() 메서드는 특정 데이터 자체를 삭제하는 함수

→ 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제

my_list = [1, 2, 3, 2, 4, 5]
my_list.remove(2) # [1, 3, 2, 4, 5]

리스트 컴프리헨션으로 데이터에 특정 연산 적용

(1) 리스트에 제곱 연산 적용 예시

numbers = [1, 2, 3, 4, 5]
squares = [num**2 for num in numbers] # [1, 4, 9, 16, 25]

• 주목해야 할 점 : numbers 리스트의 값 변화 유무 → numbers의 값 자체는 변형되지 않음
  → 리스트 컴프리헨션은 연산이 끝난 리스트를 반환, 연산 대상 리스트 변형 X
  
  

리스트 연관 메서드

len() : 리스트의 전체 데이터 개수 반환

index() : 특정 데이터가 처음 등장한 인덱스 반환, 없으면 -1 반환

sort() : 사용자가 정한 기준에 따라 리스트 데이터 정렬

count() : 특정 데이터 개수 반환

fruits = ["apple", "banana", "cherry", "apple", "orange", "banana", "kiwi"]
len(fruits) # 7
fruits.index("banana") # 1
fruits.sort() # ["apple", "apple", "banana", "banana", "cherry", "kiwi", "orange"]
fruits.count("apple") # 2

4) 몸풀기 문제

문제 01) 배열 정렬하기

정수 배열을 정렬해서 반환하는 함수 완성

def solution(arr):
	ary = arr.sort()
	return ary

문제 02) 배열 제어하기

정수 배열 하나 받음, 배열의 중복 값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환하는 함수 구현

def solution(arr):
	for i in range(0, len(arr)):
		if(arr.count(i) > 1):
			arr.pop(i)

	arr.sort(reverse=True)
	return arr

5) 합격자가 되는 모의 테스트

문제 03) 두 개 뽑아서 더하기

정수 배열 numbers가 주어짐, numbers에서 서로 다른 인덱스에 있는 2개의 수를 뽑아 더해 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 함수 완성

def solution(numbers):
  result = []
  
  for i in range(len(numbers)):
    for j in range(i+1, len(numbers)):
      if(i != j):
        result.append(numbers[i] + numbers[j])
        result = sorted(set(result))
  
  return result

문제 04) 모의고사

수포자의 1번 문제부터 마지막 문제까지 다음과 같이 찍는다

- 1번 수포자 찍는 방식 : 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, …
- 2번 수포자 찍는 방식 : 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, …
- 3번 수포자 찍는 방식 : 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, …

1번 문제부터 마지막 문제까지의 정답이 순서대로 저장된 배열 answers가 주어졌을 때 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 반환하도록 함수 작성

def solution(answers):
  result = []
  pattern = [
    	[1, 2, 3, 4, 5],
    	[2, 1, 2, 3, 2, 4, 2, 5],
    	[3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
	]
  count1 = count2 = count3 = 0
  
  for i in range(len(pattern)):
    for j in range(len(answers)):
      if(pattern[i][j] == answers[j]):
        if(i == 0):
          count1 += 1
        elif(i == 1):
          count2 += 1
        else:
          count3 += 1

  cnt = [count1, count2, count3]
  max_cnt = max(cnt)
  
  for i in range(len(cnt)):
    if max_cnt == cnt[i]:
      result.append(i + 1)
  
  return sorted(result)

문제 05) 행렬의 곱셈

2차원 행렬 arr1과 arr2를 입력 받아 arr1에 arr2를 곱한 결과를 반환하는 함수 완성

def solution(arr1, arr2):
  result = [[0 for j in range(len(arr2))] for i in range(len(arr1))]
  
  for i in range(len(arr1)):
    for j in range(len(arr1[i])):
      for k in range(len(arr2)):
        result[i][j] += arr1[i][k] * arr2[k][j]
  
  return result

문제 06) 실패율

실패율 정의 : 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어의 수

전체 스테이지 개수가 N, 게임을 이용하는 사용자가 현재 멈춰 있는 스테이지의 번호가 담긴 배열 stages가 주어질 때 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨 있는 배열 반환하는 함수 완성

def solution(N, stages):
  result = []
  res = {}
  challengers = len(stages)
  
  for i in range(1, N + 1):
    fails = stages.count(i)
    res[i] = fails / challengers
    challengers -= fails
  
  result = sorted(res, key=lambda x : res[x], reverse=True)
  
  return result

문제 07) 방문 길이

명령어가 매개변수 dirs로 주어질 때 게임 캐릭터가 처음 걸어본 길의 길이를 구해 반환하는 함수

def solution(dirs):
    answer = set()
    x = y = 5
    nx = ny = 0
    list_dirs = list(dirs)
    
    for i in range(len(list_dirs)):   
      if 0 < y < 10:
        if list_dirs[i] == "U":
          nx, ny = x, y + 1  
        elif list_dirs[i] == "D":
          nx, ny = x, y - 1
          
      if 0 < x < 10:
        if list_dirs[i] == "R":
          nx, ny = x + 1, y 
        elif list_dirs[i] == "L":
          nx, ny = x - 1, y
      
      answer.add((x, y, nx, ny))
      answer.add((nx, ny, x, y))
      x = nx
      y = ny
    
    return len(answer) // 2