반응형
| 자료구조 | 시간 복잡도 | |||||||
| 평균 | 최악 | |||||||
| 접근 | 탐색 | 삽입 | 삭제 | 접근 | 탐색 | 삽입 | 삭제 | |
| 배열 array | O(1) | O(N) | O(N) | O(N) | O(1) | O(N) | O(N) | O(N) |
- 주로 여러개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용된다.
- [인덱스, 값] 쌍의 집합이다. 인덱스가 주어지면 해당하는 요소가 대응되는 자료구조
- 순차적 메모리 공간에 할당되는 순차적 표현
- 같은 자료형의 변수를 여러 개 만드는 경우에 유용함
- 동일한 이름을 사용하는 인덱스 번호로 각 항목을 접근할 수 있다.
- 배열은 어느 위치에나 O(1)에 조회가 가능하다
- 인덱스(Index) : 각 요소는 배열 내에서 고유한 인덱스를 가지며, 이 인덱스는 배열의 시작부터 얼마나 떨어져 있는지를 나타냅니다. 대부분의 프로그래밍 언어에서 인덱스는 0부터 시작하며, 1씩 증가합니다.
- 크기(Size) : 배열의 크기는 배열에 저장된 요소의 개수를 나타냅니다. 배열을 생성할 때 크기를 지정하거나 동적 배열을 사용하여 동적으로 크기를 조절할 수 있다.
- 동일한 자료형 : 배열은 동일한 자료형의 요소를 가지고 있어야 한다. 예를 들어, 정수 배열은 정수형 요소로 이루어져 있다.
- 메모리 구조 : 배열은 연속적인 메모리 위치에 요소를 저장하므로, 특정 인덱스의 요소에 빠르게 접근할 수 있습니다. 이는 배열의 강점 중 하나로, 빠른 읽기와 쓰기 연산을 가능하게 합니다.
- 수정 가능(Mutable) : 일반적으로 수정 가능한(Mutability) 자료구조입니다. 따라서 특정 인덱스의 값을 변경하거나 요소를 추가, 삭제할 수 있습니다.
리스트에 데이터 추가
append() 메서드로 데이터 추가
lst = [1, 2, 3]
lst.append(4) # [1, 2, 3, 4]
+연산자로 데이터 추가
lst = [1, 2, 3]
lst = lst + [4, 5] # [1, 2, 3, 4, 5]
insert() 메서드로 데이터 삽입
lst = [1, 2, 3, 4, 5]
lst.insert(2, 9999) # [1, 2, 9999, 3, 4, 5]
insert(idx, num)
리스트에서 데이터 삭제
pop() 메서드로 특정 위치의 데이터 팝
lst = [1, 2, 3, 4, 5]
popped_element = lst.pop(2) # 3
print(lst) # [1, 2, 4, 5]
pop(idx)
remove() 메서드로 특정 데이터 삭제
lst = [1, 2, 3, 2, 4, 5]
lst.remove(2) # [1, 3, 2, 4, 5]
리스트 컴프리헨션
nums = [1, 2, 3, 4, 5]
squares = [num ** 2 for num in nums] # [1, 4, 9, 16, 25]
문제 01 배열 정렬하기
더보기
# 정수 배열의 길이는 2이상 10^5 이하입니다
# 정수 배열의 각 데이터 값은 -100,000 이상 100,000 이하 입니다
import time
def bubble_sort(arr) : # 버블 정렬
n = len(arr)
for i in range(n) :
for j in range(n - i - 1) :
if arr[j] > arr[j + 1] :
arr[j], arr[j + 1] = arr[j + 1], arr[i]
return arr
def merge_sort(arr): # 병합 정렬
def sort(low, high):
if high - low < 2:
return
mid = (low + high) // 2
sort(low, mid)
sort(mid, high)
merge(low, mid, high)
def merge(low, mid, high):
tmp = []
l, h = low, mid
while l < mid and h < high:
tmp.append(arr[l])
l += 1
else:
tmp.append(arr[h])
h += 1
while l < mid:
tmp.append(arr[l])
l += 1
while h < high:
tmp.append(arr[h])
h += 1
for i in range(low, high):
arr[i] = tmp[i - low]
return sort(0, len(arr))
# 퀵 정렬이 sort() 와 동일한 구조를 가지고 있다고 함.
def quick_sort(arr) : # 퀵 정렬
def sort(low, high) :
if high <= low :
return
mid = partition(low, high)
sort(low, mid - 1)
sort(mid, high)
def partition(low, high) :
pivot = arr[(low + high) // 2]
while low <= high :
while arr[low] < pivot :
low += 1
while arr[high] > pivot :
high -= 1
if low <= high :
arr[low], arr[high] = arr[high], arr[low]
low, high = low + 1, high - 1
return low
return sort(0, len(arr) - 1)
def measure_time(func, arr) : # 시간 측정
start = time.time()
result = func(arr)
end = time.time()
return end - start, result
arr = list(range(10000))
# 1. 버블 정렬 시간 측정
# 버블 정렬 실행 시간 : 4.3163259029
bubble_time, bubble_result = measure_time(bubble_sort, arr)
print(f'첫 번째 코드 실행시간 : {bubble_time:.10f}')
# 2. 병합 정렬 시간 측정
# 병합 정렬 실행 시간 : 0.0233900547
merge_time, merge_result = measure_time(merge_sort, arr)
print(f'병합 정렬 실행 시간 : {merge_time:.10f}')
# 3. 퀵 정렬 시간 측정
# 퀵 정렬 실행 시간 : 0.0143389702
quick_time, quick_result = measure_time(quick_sort, arr)
print(f'퀵 정렬 실행시간 : {quick_time:.10f}')
문제 04 모의고사
문제 분석
1. 패턴 찾기
- 각 수포자들의 패턴을 찾아 각 패턴으로 문제를 풀 경우 몇 개를 맞출 수 있는지 체크
2. 예외 사항
- 가장 높은 점수를 획득한 수포자의 번호를 반환할 때 동점자가 발생할 경우를 주의해야함.
- 수포자들이 얻은 점수의 최댓값을 먼저 구하고 이 점수와 일치하는 수포자의 번호를 오름차순으로 반환하면 동점 조건을 해결할 수 있음.
3. 시간 복잡도 분석
- N은 answer의 길이입니다. 각 수포자들의 패턴과 정답을 비교하는 부분은 O(N)의 시간 복잡도를 가짐.
- 이후 results를 순회하면서 가장 높은 점수를 받은 수포자를 추가하는 연산은 O(1)
- 최종 시간 복잡도는 O(N)
더보기
def solution(answers):
# 점수를 저장할 리스트
answer = [0, 0, 0]
# 패턴
ans1 = [1, 2, 3, 4, 5]
ans2 = [2, 1, 2, 3, 2, 4, 2, 5]
ans3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
# 가장 높은 점수를 가진 수포자들의 번호를 담을 리스트
result = []
# 패턴과 정답이 일치하는지 확인
for idx, val in enumerate(answers):
if ans1[idx % len(ans1)] == val:
answer[0] += 1
if ans2[idx % len(ans2)] == val:
answer[1] += 1
if ans3[idx % len(ans3)] == val:
answer[2] += 1
# 가장 높은 점수를 가진 수포자들의 번호를 리스트에 담음
for i in range(len(answer)):
if answer[i] == max(answer):
result.append(i + 1)
return sorted(result)
------------------------------------------------------------------
def solution(answers) :
# 패턴
patterns = [
[1, 2, 3, 4, 5],
[2, 1, 2, 3, 2, 4, 2, 5],
[3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
]
# 리스트 선언
results = [0] * 3
# 각 수포자의 패턴과 정답이 얼마나 일치하는지 확인
for i, answer in enumerate(answers) :
for j, pattern in enumerate(patterns) :
if answer == pattern[i % len(pattern)] :
results[j] += 1
# 가장 높은 점수 저장
max_result = max(results)
# 가장 높은 점수를 가진 수포자들의 번호를 찾아서 리스트에 담음
highest_results = []
for i, result in enumerate(results) :
if result == max_result :
highest_results.append(i + 1)
return highest_results문제 06 실패율
1. 문제 분석
- stages가 20만까지 입력될 수 있으므로, 정렬 알고리즘의 시간 복잡도는 O(NlogN)이어야 함.
2. 예외 사항
3. 시간 복잡도 분석
- N은 stages의 개수이고, M은 stages의 길이입니다.
- challenger 배열을 초기화하고, 각 스테이지 도전자 수를 계산할 때 시간 복잡도는 O(N + M)
- 이후 스테이지 별로 실패율을 계산하는 데 필요한 시간 복잡도는 O(N)
- 실패율을 기준으로 스테이지를 정렬할 때의 시간 복잡도는 O(NlogN)
- 모두 고려하면, 시간 복잡도는 O(2*N + M + NlogN)
- 최종 시간 복잡도는 O(M + NlogN)
더보기
def solution(N, stages) :
# 1. 스테이지별 도전자 수 구함
challenger = [0] * (N + 2)
for stage in stages :
challenger[stage] += 1
# 2. 스테이지별 실패한 사용자 수 계산
fails = {}
total = len(stages)
# 3. 각 스테이지별 순회하며, 실패율 계산
for i in range(1, N + 1) :
if challenger[i] == 0 :
fails[i] = 0
else :
fails[i] = challenger[i] / total
total -= challenger[i]
result = sorted(fails, key = lambda x : fails[x], reverse=True)
return result
print(solution(5, [2, 1, 2, 6, 2, 4, 3, 3]))
print(solution(4, [4, 4, 4, 4, 4]))문제 07 방문 길이
1. 문제 분석
- 중복 경로는 최종 길이에 포함하지 않는다.
- 음수 좌표를 포함해야 함.
2. 예외 사항
- 중복 경로를 제외 시켜야 함
- -5 ~ 5 의 범위를 0 ~ 10 까지의 범위로 바꿔서, 시작 지점을 5, 5로 음수 좌표 문제를 해결해도 됨.
3. 시간 복잡도 분석
- N은 dirs의 길이입니다. dirs의 길이만큼 순회하므로 시간 복잡도는 O(N)
더보기
def solution(dirs) :
s = set() # 겹치는 좌표는 1개로 처리하기 위함
# 명령어를 통해 다음 좌표 결정 - 키-값으로 해결
d = {'U' : (0,1), 'D' : (0,-1), 'R' : (1,0), 'L' : (-1,0)}
x, y = 0, 0
for i in dirs : # 주어진 명령어로 움직이면서 좌표 저장
nx, ny = x + d[i][0], y + d[i][1]
if -5 <= nx <= 5 and -5 <= ny <= 5 : # 좌표 설정
# A에서 B로 간 경우 B에서 A도 추가해야함.
s.add((x, y, nx, ny))
s.add((nx, ny, x, y))
x, y = nx, ny # 좌표 업데이트
return len(s) // 2
반응형