기본 자료구조와 배열
자료구조
자료구조의 정의: 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적 관계
즉, 자료구조는 데이터가 모여 있는 구조 혹은 논리적인 관계로 이루어진 데이터 구성을 의미한다. 자료구조를 이해하면 컴퓨터에서 처리해야 하는 많은 데이터를 모아 효율적으로 관리하고 구조화할 수 있다.
배열
배열의 정의
배열(Array): 묶음 단위로 값을 저장하는 자료구조
배열에는 객체가 저장되며, 배열에 저장된 객체 하나하나를 원소(element)라고 한다. 또한 각 원소는 0, 1, 2, … 순으로 인덱스(index)를 부여받는다.
- 배열 원소의 자료형(type)은 int, float 등 어떤 것이라도 상관없으며 서로 다른 자료형을 같이 저장할 수도 있고, 배열 원소 자체를 배열에 저장할 수도 있다.
리스트 & 튜플
리스트와 튜플은 공통적으로 데이터 컨테이너(data container)라고도 부르는 배열이다.
리스트[ ]:
- 뮤터블(mutable) 객체 - 원소의 변경이 가능하다
- 이터러블(iterable) - for 문을 활용해 반복이 가능하다
- 딕셔너리의 key로 사용이 불가능하다
-
내포 표기 생성 - 리스트 안에서 for, if 문을 사용하여 새로운 리스트를 생성할 수 있다
numbers = [1, 2, 3, 4, 5] twise = [num * 2 for num in numbers if num % 2 == 1] print(twise) # [2, 6, 10]
튜플( ):
- 이뮤터블(immutable) 객체 - 원소의 변경이 불가능
- 이터러블(iterable) - for 문을 활용해 반복이 가능하다
- 결합 연산자 ( )를 생략할 수 있다. ex) tuple1 = 1, 2, 3, # (1, 2, 3)
- 딕셔너리의 key로 사용이 가능하다
언팩 (unpack): 리스트나 튜플의 원솟값들을 풀어 여러 변수에 대입하는 것
x = [1, 2, 3] # 리스트 x 선언
a, b, c = x # x를 언팩하여 변수 a, b, c에 대입
a, b, c # (1, 2, 3)
등가성과 동일성:
- 등가성(equality) : ‘==’를 사용, 좌변과 우변의 값이 같은지 비교
- 동일성(identity) : is 를 사용, 값과 객체의 식별 번호까지 같은지 비교
파이썬의 변수
파이썬에서는 데이터, 함수, 클래스, 모듈, 패키지 등을 모두 객체로 취급한다. 객체는 자료형을 가지며 메모리를 차지한다. (=’메모리 주소/식별번호(identity)를 가지고 있다’)
⇒ 위 특성 때문에 파이썬의 변수는 값을 갖지 않는다
- 변수는 객체를 참조하는, 객체에 연결된 이름에 불과하다.
예1) 전역변수 n = 1 과, 지역변수 x = 1 은 둘 다 int형 객체 1을 참조하기 때문에 같은 id 값을 갖는다.
예2) n = 5 선언 후 n = ‘ABC’ 라고 선언하면 n의 값이 변하는 것이 아니라 n의 참조 값, 식별번호가 바뀌는 것이다.
⇒ 수, 문자열, 튜플은 값 자체를 바꿀 수 없는 이뮤터블 객체다
- 12는 13이 될 수 없다
- ‘DOG’는 ‘CAT’이 될 수 없다
- (1, 2, 3)이 (1, 2, 3, 4)가 될 수 없다
⇒ 리스트, 딕셔너리, 집합 등은 값을 바꿀 수 있는 뮤터블 객체다
어노테이션(annotation, 주석 달기)과 자료형 힌트
파이썬은 문법의 제약성이 적어 유연성이 높고 자료형 선언 없이 변수나 함수를 자유롭게 사용할 수 있지만 그로 인해 명시적으로 해석하기 어렵다는 단점이 있다. 그래서 파이썬 3 이상부터 함수의 파라미터 또는 변수에 어노테이션(주석)을 달 수 있다.
또한 Any, Sequence 를 임포트 하여 기본 자료형 외의 힌트를 표시할 수도 있다. Any는 제약이 없는 임의의 자료형을 의미하며, Sequence는 시퀀스형 자료(리스트, 바이트 배열, 문자열, 튜플 등)를 의미한다.
from typing import Any, Sequence
def func(a: Sequence) -> Any:
#파라미터 a의 자료형은 Sequence 이며, 함수가 반환하는 것은 임의의 자료형인 Any 이다
def func(a: int = 10) -> int:
#파라미터 a의 자료형은 int이며 디폴트 값은 10이다. 그리고 해당 함수는 int형 변수를 반환한다
배열을 사용하는 기본 알고리즘
스캔
배열의 원소를 하나씩 차례로 주목하여 살펴보는 방식. (예, 선형검색)
스캔은 ‘주사’ 또는 ‘트래버스(traverse)’라고도 한다
예) 배열의 최댓값 구하기
from typing import Any, Sequence
def max_of(a: Sequence) -> Any:
"""시퀀스형 a 요소의 최댓값을 반환"""
maximum = a[0]
for i in range(1, len(a)):
if a[i] > maximum:
maximum = a[i]
return maximum
if __name__ == '__main__':
print('배열의 최댓값을 구합니다.')
num = int(input('원소 수를 입력하세요 : '))
x = [None] * num # 원소 수가 num인 리스트를 생성
for i in range(num):
x[i] = int(input(f'x[{i}]를 입력하세요.: '))
print(f'최댓값은 {max_of(x)}입니다.')
- “for i in range(1, len(a))” 루프 안에서 a[1] 부터 a[len(a)-1] 까지 배열 원소를 하나씩 확인하는 스캔이 이루어진다.
배열 원소를 역순으로 정렬하기
역순 정렬 알고리즘
for i in range(n//2): #range(0, n//2)와 같음
a[i], a[n-i-1] = a[n-i-1], a[i]
#배열의 맨 앞에서 시작하는 인덱스와 배열의 맨 끝에서 시작하는 인덱스 값의 교환
리스트를 역순으로 정렬
x.reverse() # 리스트 x의 원소를 역순으로 정렬 (튜플은 이뮤터블하므로 불가능)
역순으로 정렬한 리스트 생성
y = list(reversed(x)) # 리스트 x의 원소를 역순으로 정렬하여 y에 대입
기수 변환하기(n진수 값 구하기)
n진수는 n을 기수로 하는 수로, 자릿수가 아랫자리부터 n^0, n^1, n^2, n^3 순으로 늘어난다. 예를 들어 10진수 4865는, “4 x 10³ + 8 x 10² + 6 x 10 + 5” 로 풀어쓸 수 있다.
예) 10진수 정숫값을 입력받아 2~16진수로 변환하여 출력하는 함수
def cord_conv(x: int, r: int) -> str:
#정수 x를 r진수로 변환한 뒤 그 수를 나타내는 문자열 반환
d = ' ' #변환 후의 문자열
dchar = '0123456789ABCDEF' #2진수부터 16진수를 표현하는데 쓰이는 숫자 종류
while x > 0:
d += dchar[x%r] #해당하는 문자를 꺼내 결합
x //= r #x를 r로 나눈 몫을 다시 x에 대입
return d[::-1] #문자열을 역순으로 반환
위 코드를 통해 59를 2진수로 변환할 경우의 과정은 아래와 같다.
- x = 59
- dchar[59%2] == dchar[1] == 1, d == ‘1’
- 59 // 2 == 29
- x = 29
- dchar[29%2] == dchar[1] == 1, d == ‘11’
- 29 // 2 == 14
- x = 14
- dchar[14%2] == dchar[0] == 0, d == ‘110’
- 14 // 2 == 7
- x = 7
- dchar[7%2] == dchar[1] == 1, d == ‘1101’
- 7 // 2 == 3
- x = 3
- dchar[3%2] == dchar[1] == 1, d == ‘11011’
- 3 // 2 == 1
- x = 1
- dchar[1%2] == dchar[1] == 1, d == ‘110111’
- 1 // 2 == 0
- d[ : : -1] == ‘111011’
- 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 1 * 2 + 1 = 32 + 16 + 8 + 0 + 2 + 1 = 59
소수 나열하기
소수는 자신과 1 이외의 정수로 나누어 떨어지지 않는 정수다. 이를 재정의하면, 소수는 다음 조건을 만족하는 정수 n이다.
2부터 n-1까지 어떤 정수로도 나누어 떨어지지 않는다
파이썬 기초를 막 배웠을 때 내가 작성한 소수 구하기 코드는 다음과 같았다.
# while문 사용
num=2
while num<=100:
i=2
while i<=num:
if num%i == 0:
if i < num:
break
else:
print(num, end=' ')
i+=1
num+=1
# for문 사용
for num in range(2,101):
for i in range(2,num+1):
if num%i == 0:
if i < num:
break
else:
print(num, end=' ')
그런데 여기서 더 나아가면, n이 짝수일 경우 2로 항상 나눠지기 때문에 2를 제외한 나머지 소수는 무조건 홀수라는 것을 알 수 있다.
또한, 소수인 n이 2와 3으로 나누어 떨어지지 않는다면 2x2인 4와 2x3인 6 등으로도 나누어 떨어지지 않는다. 즉, 모든 정수로 n을 나눠보는 것은 불필요한 과정이다. 정수 n이 소수인지 확인하기 위해서는 다음 조건을 만족하는지 보면 된다.
n은 홀수이며 2부터 n-1까지 어떤 소수로도 나누어 떨어지지 않는다.
이 조건을 반영하면 훨씬 더 나은 소수 구하기 알고리즘을 만들 수 있다.
#1000 이하의 소수 나열하기
ptr = 0 # 이미 찾은 소수의 개수
prime = [None] * 500 # 소수를 저장하는 배열
prime[ptr] = 2 # 2는 소수이므로 초깃값으로 지정
ptr += 1
for n in range(3, 1001, 2): # 홀수만을 대상으로 설정
for i in range(1, ptr): # 이미 찾은 소수로 나눔
counter += 1
if n % prime[i] == 0: # 나누어 떨어지면 소수가 아님
break # 반복 중단
else: # 끝까지 나누어 떨어지지 않았다면
prime[ptr] = n # 소수로 배열에 등록
ptr += 1
위 알고리즘을 사용할 경우 나눗셈은 총 14,622번 이루어지며 이는 약 78000회 이상 나눗셈이 이루어지는 첫번째 알고리즘과 비교했을 때 크게 줄어든 횟수다.
- 같은 결과를 얻을 수 있는 알고리즘은 여러 개일 수 있다
- 빠른 알고리즘은 많은 메모리를 요구한다
+ 여기서 더 나아가면 다음과 같은 알고리즘을 작성할 수도 있다. 아래 알고리즘에서 곱셈과 나눗셈은 3,774번만 이루어진다.
"""
소수 정의: n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.
"""
ptr = 0 # 이미 찾은 소수의 개수
prime = [None] * 500 # 소수를 저장하는 배열
prime[ptr] = 2 # 2는 소수
ptr += 1
prime[ptr] = 3 # 3은 소수
ptr += 1
for n in range(5, 1001, 2): # 홀수만을 대상으로 설정
i = 1
while prime[i] * prime[i] <= n:
counter += 2
if n % prime[i] == 0: # 나누어 떨어지므로 소수가 아님
break # 반복 중단
i += 1
else: # 끝까지 나누어 떨어지지 않았다면
prime[ptr] = n # 소수로 배열에 등록
ptr += 1
counter += 1
댓글남기기