[자료구조] 정렬, 탐색

 

≣ 목차

 

---

알고리즘 시간 복잡도

알고리즘을 풀때는 제한 시간내에 코드가 실행 완료되는것이 중요하다. 이를 위해 우리는 알고리즘의 시간복잡도와 공간 복잡도가 어떠한가를 미리 파악한 후 이에 맞는 문제 풀이 방법을 생각해내야 한다.이러한 복잡도를 표현하는 방법 중 가장 흔히 사용되는 방법은 빅오 표기법(big-O notation)이다.

이에 관한 설명은 아래 링크에 자세히 작성되어 있다.

https://seung2344.tistory.com/22

---

리스트 

파이썬에는 다른 언어들에서 다뤄지는 배열과 유사한 성질의 리스트(list)라는 자료구조가 존재한다. 

동일한 자료형만 가질 수 있는 배열과는 달리, 리스트는 다양한 자료형을 하나의 리스트 안에 담을 수 있다.

• 선언 방법
  

a = [1,2,'a','b',"xyz"]
b = []
c = list()
d = [0]*10 		#[0,0,0,0,0,0,0,0,0,0]
e = [i*2 for i in range(5)] 	#[0,2,4,6,8]

리스트는 위와 같은 다양한 방법을 통해 선언이 가능하다.

• 연산 

a = [1,2,3]
b = ['a','b','c']
c = a+b 	#[1,2,3,'a','b','c']
d = a*3 	#[1,2,3,1,2,3,1,2,3]
e = a*0 	#[]

이처럼 리스트 사이의 덧셈이 가능하며, 곱셈 연산 역시 가능하다. 0을 곱하며 빈 리스트가 생성됨을 유의하자.

• 인덱싱

a = [1,2,3,4,5,6,7,8,9,10]

#값 접근
a[0] 	#1
a[-1] 	#10
a[1:4] 	#[2,3,4]
a[:3] 	#[1,2,3]
a[5:] 	#[6,7,8,9,10]
a[:] 	#[1,2,3,4,5,6,7,8,9,10]

#값 수정
a[2]=50

리스트의 값 접근 방법은 배열과 동일하다. 
인덱스 슬라이싱을 할 땐 [시작 인덱스, 종료 인덱스+1]임을 꼭 기억하자.
슬라이싱을 할 때도 음수 인덱스를 적을 수 있다.

• 메서드

a = [1,2,3,4,5,5,6]
b = [10,20]

#길이
len(a) 	# 7

#값 삭제
del(a[1]) 		# a=[1,3,4,5,5,6]
del(a[0:2]) 		# a=[4,5,5,6]
a.remove(5)  		# a=[4,5,6]	
a.pop() 	 	# a=[4,5], 6반환

#값 추가
a.append('a') 		# a=[4,5,'a']
a.insert(2,'x') 	# a=[4,5,'x','a']

#리스트 연결
a.extend(b) 		# a=[4,5,'x','a',10,20]

#리스트 뒤집기
a.reverse() 		# a=[20,10,'a','x',5,4]

#값 위치 반환
a.index(10) 		# 1

#모든 값 삭제
a.clear() 		# a=[]

리스트의 연결 메서드인 extend와 + 연산의 차이는 새로운 리스트의 생성여부라고 보면 된다. extend의 경우 a 자체에 다른 리스트가 붙는 것이고, +의 경우 새로운 리스트가 새로 생성되게 된다.
리스트의 주요 메서드 중 하나인 sort는 아래 정렬파트에 설명되어있다.

---

정렬  

정렬이란 특정한 기준에 따라 데이터를 늘어놓는 알고리즘을 말한다.
파이썬의 대표적인 정렬 방법으로는 메서드인 .sort()와 내장 함수인 sorted()가 있다. sort()를 사용할 경우 해당 리스트 자체가 정렬이 되는 것이며, sorted() 사용할 경우 정렬된 새로운 리스트가 생기게된다.

a = [1,4,8,3,10,5,2]
b = ['bbb','ccc','aaa']

c = sorted(a) 	# c=[1,2,3,4,5,8,10]
a.sort(reverse=True) 	# a=[10,8,5,4,3,2,1]

 

함수를 정의함으로써 새로운 정렬기준을 만들 수 있다.

---

 탐색   

탐색이란 복수의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업이다. 선형 탐색과 이진 탐색이 가장 기본적인 방법 중에 하나이다.

• 선형 탐색(Linear search) : 순차적으로 모든 요소를 탐색하는 방법. 리스트의 길이에 비례하는 시간이 걸린다.
• 이진 탐색(Binary search) : 리스트의 가운데 원소와 찾으려는 값을 비교하고, 결과에 따라 리스트의 범위를 줄여나가며 탐색하는 방법. 탐색하려는 리스트가 이미 정렬되어 있는 경우에만 적용할 수 있다.