파이썬 자료구조와 배열 그리고 검색 알고리즘에 대해 배운 하루
파이썬 자료구조와 배열
파이썬 리스트
배열을 통해 어떻게 자료를 담을지, 어떻게 활용할지에 대해서는 매우 다양한 방법이 있습니다.
파이썬의 리스트 선언은 아래와 같습니다.
a = []
listA = [1,2,3]a = [] 라고 선언해주면 그냥 빈 리스트를 하나 만들어주는 것입니다. listA에는 원소 1,2,3이 리스트에 담기게 됩니다. 이때 각 원소에 접근하는 방식은 인덱스 번호를 통해 접근할 수 있습니다. 인덱스 번호의 시작은 0번부터 시작입니다.
listA[0] # 원소 1을 가리킨다
listA[1] # 원소 2을 가리킨다
listA[2] # 원소 3을 가리킨다위처럼 인덱스 번호를 통해 원소값을 찾을 수 있는데 만약 리스트가 엄청 큰 경우 리스트 맨 마지막 원소에 접근하기 어려운 경우가 있습니다. 이럴경우에는 인덱스 번호 -1부터 시작하면 거꾸로 리스트 원소들을 탐색할 수 있습니다.
listA[-1] # 원소 3을 가리킨다
listA[-2] # 원소 2을 가리킨다
listA[-3] # 원소 1을 가리킨다파이썬 튜플
파이썬의 배열에는 리스트뿐 아니라 튜플이란 배열도 존재합니다.
튜플의 선언은 아래와 같습니다.
a = (1,2,3)리스트와는 다르게 ( )괄호로 묶어주면 튜플입니다. 리스트와의 차이점은 튜플은 한번 선언하게 되면 원소값을 변환할 수 없다는 차이점이 있습니다. 또, 리스트가 쓸 수 있는 함수와 튜플이 사용할 수 있는 함수에 차이가 있습니다.
파이썬 리스트와 관련된 여러 실습 코드
리스트에 원소값을 추가하는 방법
a = [1,2,3] # 리스트 선언
a.append(4) # append 함수를 사용하여 원소 추가가 가능함
# a리스트에는 이제 1,2,3,4 원소값이 존재함리스트에 모든 원소값을 출력하는 방법
리스트의 모든 원소값을 출력하기 위해서는 반복문을 사용하는데 그러면 모든 원소값을 확인할 수 있습니다.
for i in a:
print(i) # 1 2 3 4가 출력, 물론 자동 줄바꿈이 되어서 출력됨일반적으로 반복문을 통해 출력할 때, enumerate를 사용해주는 경우도 있습니다
enumerate 사용
enumerate를 사용하면 인덱스와 원소를 짝지어서 튜플 형태로 리스트를 꺼낼 수 있습니다.
for idx, x in enumerate(a):
print(f'인덱스 번호 : {idx} == 원소 값 : {x}')
#아래와 같은 결과 값을 만날 수 있다.
#인덱스 번호 : 0 == 원소 값 : 1
#인덱스 번호 : 1 == 원소 값 : 2
#인덱스 번호 : 2 == 원소 값 : 3
#인덱스 번호 : 3 == 원소 값 : 4
원하는 원소 값을 입력받고 역순으로 정렬하기
아래 예제코드를 작성하겠습니다.
def revers_list(listA):
lx = len(listA)
for i in range(0,lx//2):
listA[i], listA[-1-i] = listA[-1-i], listA[i]
print(f'ddd{listA[-1-i]}')
n = int(input('입력을 원하는 수를 입력하세요 : '))
a = []
for i in range(n):
a.append(int(input('리스트에 추가할 정수를 입력하세요 : ')))
print(f'입력한 리스트는 {a}')
print('역순으로 출력하겠습니다.')
revers_list(a)
print(a)위 코드는 이제 사용자가 원하는 리스트 크기를 입력하고 원하는 원소값을 입력하도록 설계했습니다.
그리고 입력받은 리스트를 한번 출력해주고 직접 만든 역순리스트 함수 revers_list에 매개변수로 입력받은 리스트를 넘겨주고 실행한 결과값을 출력하면 입력한 리스트가 역순이 되어 출력되는 것을 확인할 수 있습니다.
위 코드를 더 살펴보면 len(listA) 라고 작성한 부분이 있는데 len은 리스트의 길이를 반환해주는 함수입니다.
검색 알고리즘
원하는 값을 가진 원소를 찾아내는 알고리즘을 말하며 자료구조에 따라 활용할 수 있는 알고리즘이 다양하게 존재합니다.
선형 검색(Linear Search)
직선 모양으로 늘어선 리스트에서 검색하는 경우에 원하는 값을 가진 원소를 찾을 때 까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘입니다.
검색할 값과 같은 원소를 찾는 경우에는 검색에 성공한 경우이지만 찾지 못하고 리스트의 맨 끝에 도달하게 되면 검색에 실패한 경우입니다.
보초법(Sentinel Method)
보초법은 선형 검색을 할 때 배열의 맨 마지막에 찾고자 하는 값을 추가해줍니다. 이를 통해 종료 판단횟수(if문)의 사용횟수를 절반으로 감소시켜주는 역할을 합니다.
검색이 종료된 후 검색 값과 같은 원소를 찾은 위치가 만약 배열 뒤에 추가한 보초의 위치라면 찾지 못함을 뜻하고 그렇지 않으면 찾음을 뜻합니다.
이진탐색(Binary Search)
이진탐색(검색은 리스트의 데이터가 오름차순이나 내림차순으로 정렬이 되어 있다는 것을 전제조건으로 사용합니다.
이진탐색을 사용하면 선형검색에 비해 빠른 실행 결과를 만날 수 있습니다.
이진탐색을 사용하기 전에 리스트를 정렬해준 후 절반으로 계속해서 검색범위를 나누어 가면서 검색을 원하는 값을 찾아가는 방식입니다.
이진탐색의 예시를 보여드리겠습니다.
def search1(listB, key):
pl = 0
pr = len(listB)-1
while True:
pc = (pl + pr) // 2
if listB[pc] == key:
return pc
elif listB[pc] < key:
pl = pc + 1
else:
pr = pc - 1
if pl > pr:
break
return -1
n = int(input('입력할 원소의 갯수를 입력해주세요 : '))
listA = []
for i in range(n):
listA.append(int(input('원소를 입력해주세요 : ')))
listA.sort()
print(listA)
key = int(input('입력하신 원소 중에 찾고자 하는 값을 입력해주세요 : '))
idx = search1(listA, key)
if idx == -1:
print('존재하지 않는 원소 값입니다.')
else:
print(f'찾고자 하는 값은 {key}이며 해당 원소의 인덱스 값은 listA[{idx}]입니다.')
search1의 함수를 보면 pl은 검색 범위의 맨 앞을 표시하는 변수이고 맨 끝은 pr이라는 변수를 설정해둡니다. 그리고 중앙 인덱스를 pc로 잡아주게 되면 이진탐색을 위한 작업이 끝납니다.
이제 찾고자하는 key값을 pc와 비교해줍니다 그리고 key값이 pc보다 작은 경우 다시 검색 범위를 설정해주는 똑같이 검색범위의 왼쪽 끝은 pl로 잡아주고 pr은 pc보다 한칸 왼쪽으로 잡아 검색 범위를 재설정해줍니다. 만약 크다면 pl이 pc보다 오른쪽으로 한칸 크게 설정하고 pr이 오른쪽 끝 범위로 설정하여 검색범위를 다시 설정해줍니다.
이렇게 계속해서 반복하면서 이진탐색을 진행합니다.
이진탐색의 종료 조건은 pc와 key가 일치하는 경우에 탐색성공을 의미하며 종료되고 검색범위가 더이상 없으면 탐색실패를 의미하며 종료됩니다.
4일차는 파이썬의 일부 탐색 알고리즘과 배열에 대해 공부했습니다. 정말 알고리즘의 일부만 배운 것이라 생각되기 때문에 열심히 혼자 학습해 나아가야된다고 생각이 듭니다.
※공부하고 있어 다소 틀린점이 있을 수 있습니다. 언제든지 말해주시면 수정하도록 하겠습니다.
※용어에 대해 조금 공부 더 해서 수정하겠습니다.
