📌 5장 배열
📌💡 5-1. 배열 개념 : 인덱스 값을 일대일 대응해 관리하는 자료구조
- 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응
- 임의 접근(random access)
1차원 배열 선언
# 일반 배열 선언 (고정)
arr = [0,0,0,0,0]
arr = [0]*6
# 리스트 생성자를 사용하는 방법 (가변)
arr = list(range(6)) #[0, 1, 2, 3, 4, 5]
# 리스트 컴프리헨션을 활용하는 방법
arr = [0 for in range(6)] #[0, 0, 0, 0, 0, 0]2차원 배열 선언
# 일반 배열 선언 (고정)
arr = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
# 리스트 생성자를 사용하는 방법 (가변)
arr = [[i]*4 for i in range(3)] # [[0,0,0,0],[1,1,1,1],[2,2,2,2]]
# 리스트 컴프리헨션을 활용하는 방법
arr = [0 for in range(6)] #[0, 0, 0, 0, 0, 0]파이썬의 리스트
배열 크기 가변적, 연산제공(슬라이싱, 삽입, 삭제, 연결)
메모리의 낮은 주소에서 높은 주소 방향으로 연이어 할당(1차원이든 2차원이든 인덱스 순서로 할당)
[리스트 편집 문법]
- 데이터 추가 : .append(넣을 값), +
- 데이터 삽입 : .insert(인덱스, 넣을 값)
- 데이터 삭제 : .pop(인덱스), .remove(값)
- 리스트 컴프리헨션 : 리스트를 기반으로 새 리스트 생성, 반복문 조건문을 이용해서 생성
[리스트 관련 문법]
alphabets = ["a","b","c","d","e","b"]
len(alphabets) #5
alphabets.index("a") #1
alphabets.count("b") #2
[리스트 정렬]
sort()
- 인수 전달 x -> 오름차순으로 정렬
- 인수 전달 o -> 내림차순으로 정렬
alphabets = ["a","b","c","d","e","b"]
alphabets.sort() #["a","b","b","c","d","e"]
alphabets.sort(reverse = True) #["e","d","c","b","b","a"]
📌💡 5-2. 배열의 효율성
배열 연산의 시간복잡도 : O(1), 임의 접근으로 모든 위치에 있는 데이터에 한번만에 접근
- 맨 뒤에 삽일할 경우 : O(1)
- 맨 앞에 삽입할 경우 : O(N)
- 중간에 삽입할 경우 : O(N)
- 배열 사용할 때 : 데이터에 자주 접근하거나 읽어야 하는 경우 (EX) 그래프)
- 단점 : 할당할 수 있는 메모리 크기 확인해야됨 -> 메모리 낭비 발생, 중간이나 처음에 데이터 삽입이 많을 시 시간 복잡도 높아짐
📌 5-4. 몸풀기 문제
🩶 문제 1. 배열 정렬하기
sort() 함수 & sorted() 함수
- sort() : 원본을 바꾸고 싶을 때
#정렬 전
# 정렬만 수행, 리턴값 None이 출력
arr.sort(reverse = True) #내림차순
arr.sort() #오름차순
#정렬 후
arr #리턴값 정렬된 리스트 - sorted() : 원본은 유지하면서 새로 정렬, 새 변수에 정의해서 사용
sorted_list = sorted(arr)
sorted_list = sorted(arr, reverse=True)🩶 문제 2. 배열 중복값 제어하기 + 내림차순
set() : 집합 생성하는 내장함수 = 집합은 중복값을 허용 X
- 해시 알고리즘 사용 O(1) = 조회시 사용
단, set()의 시간복잡도 O(N)
(why? N개의 데이터를 N번 순회하면서 중복값을 제거해야함)
list(set(arr)) #중복값 제거 후 -> 리스트로 변환
sorted(arr,reverse=True) #내림차순시간복잡도
- N 중복 원소 제거시 = set() 함수 = O(N)
- 정렬시 = sorted() = O(NlogN)
🩶 문제 3. 두 개 뽑아서 더하기
arr = [] #모든 경우의 수 -> i i+1 로 일부분만 다 담는다 (00 01 02 03, 11 12 13, 23
for i in range(len(numbers)):
for j in range(i+1, len(numbers)):
arr.append(numbers[i] + numbers[j])
sorted(list(set(arr))) #set 중복값 제거 후 -> 리스트로 변환 -> 오름차순시간복잡도
- O(N^2) = 모든 조합을 확인하는 과정에서 중복을 체크하는 데
- O(N^2log(N^2)) = set = O(NlogN) sorted = O(NlogN)
🩶 문제 4. 모의고사
💡
enumerate
- 순서가 있는 자료형(list, set, tuple, dictionary,string) 을 입력으로 받았을 때, 인덱스, 값을 포함하여 리터
- 인덱스와 값을 동시에 접근하면서 루프를 돌리고 싶을 때 사용
fruits = ['a','b','c','d','e']
print(list(enumerate(fruits)))
#[{0,'a'},{1,'b'},{2,'c'},{3,'d'},{4,'e'}]
for i,value in enumerate():풀이
def solution(answers):
answer = []
score = [0,0,0]
pattern1 = [1,2,3,4,5]
pattern2 = [2,1,2,3,2,4,2,5]
pattern3 = [3,3,1,1,2,2,4,4,5,5]
for i in range(len(answers)) :
if answers[i] == pattern1[i%5] :
score[0] += 1
if answers[i] == pattern2[i%8] :
score[1] += 1
if answers[i] == pattern3[i%10] :
score[2] += 1
for i, num in enumerate(score) :
if num == max(score) :
answer.append(i +1)
return answer🩶 문제 5. 행렬의 곱셈
def solution(arr1, arr2):
answer = []
m, n, r = len(arr1), len(arr1[0]), len(arr2[0])
for i in range(m):
arr = arr1[i]
result = []
for j in range(r):
tmp = 0
for k in range(n):
tmp += arr[k] * arr2[k][j]
result.append(tmp)
answer.append(result)
return answer
🩶 문제 6. 실패율
def solution(N, stages):
answer = []
length = len(stages)
for i in range(1, N+1):
count = stages.count(i)
if length == 0:
fail = 0
else:
fail = count / length
length -= count
answer.append((i, fail))
answer = sorted(answer, key = lambda x: x[1]. reverse = True)
answer = [i[0] for i in answer]
return answer🩶 문제 7. 방문 길이
# 책,,,,
def is_valid_move(nx, ny) : # ➊ 좌표를 벗어나는지 체크하는 함수
return 0 <= nx < 11 and 0 <= ny < 11
def update_location(x, y, dir) : # ➋ 명령어를 통해 다음 좌표를 결정
if dir == 'U':
nx, ny = x, y + 1
elif dir == 'D':
nx, ny = x, y - 1
elif dir == 'L':
nx, ny = x - 1, y
elif dir == 'R':
nx, ny = x + 1, y
return nx, ny
def solution(dirs):
x, y = 5, 5
ans = set( ) # ➌ 겹치는 좌표는 1개로 처리하기 위함
for dir in dirs : # ➍ 주어진 명령어로 움직이면서 좌표 저장
nx, ny = update_location(x, y, dir)
if not is_valid_move(nx, ny) : # ➎ 벗어난 좌표는 인정하지 않음
continue
# ➏ A에서 B로 간 경우 B에서 A도 추가해야 함(총 경로의 개수는 방향성이 없음)
ans.add((x, y, nx, ny))
ans.add((nx, ny, x, y))
x, y = nx, ny # ➐ 좌표를 이동했으므로 업데이트
return len(ans)/2
우당탕탕