파이썬 자료구조

• 열거형 객체 : 하나의 메모리 영역에 여러 개의 자료가 나열된 집합 자료구조
• 자료구조 : 열거형 객체가 메모리에 배정될 때 기억공간에 적재되는 구조
• 순서가 있는 자료구조와 순서가 없는 자료구조로 구분

순서 있는 자료구조 Sequence Data Structure

• str, list, tuple 클래스

str

• 문자들의 모음
• 일정한 순서를 갖는다.
• 색인을 이용하여 원소를 참조할 수 있다.

#help(str) 

# str 클래스 형식
str_var = str(object='string')
print(str_var)
print(type(str_var))
print(str_var[0])
print(str_var[-1])

string
<class 'str'>
s
g

# str 클래스 간편 형식
str_var2 = 'string'
print(str_var2)
print(type(str_var2))
print(str_var2[0])
print(str_var2[-1])

string
<class 'str'>
s
g

list [] or list()

• 1차원 배열 구조
  • 형식) list변수 = [값1, 값2,..]
• 다양한 자료형 저장 가능
• index 사용(순서 있음)
  • 형식) list변수[index]
• 값 수정(추가,삽입,수정,삭제)

#help(list) # Help on class list in module builtins:

단일 list

# 단일 list 예
lst = [1,2,3,4,5]
print(lst)
print(type(lst))
for i in lst :
    print(lst[:i]) # i 전까지

[1, 2, 3, 4, 5]
<class 'list'>
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]

for i in lst :
    print(lst[i-1: ])

[1, 2, 3, 4, 5]
[2, 3, 4, 5]
[3, 4, 5]
[4, 5]
[5]

x = list(range(1, 11))
print(x)
print(x[:5]) # [1, 2, 3, 4, 5]
print(x[-5:]) # [96, 97, 98, 99, 100]

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

print('index 2씩 증가 ')
print(x[::2]) # 홀수 
print(x[1::2]) # 짝수(index 1부터 시작) 

index 2씩 증가 
[1, 3, 5, 7, 9]
[2, 4, 6, 8, 10]

중첩 list 생성

a = ['a', 'b', 'c']  # list 생성 
b = [10, 20, a, 5, True, '문자열'] # 서로 다른 type 가능
print(b[0]) # 10
print(b[2]) # ['a', 'b', 'c'] -> 중첩 list 
print(b[2][0]) # a  -> 중첩 list 1번 원소 
print(b[2][1:]) # ['b', 'c'] -> 중첩 list 2번 이후 원소 

10
['a', 'b', 'c']
a
['b', 'c']

# 자료구조 확인
print(type(a), type(b)) # <class 'list'>
print(id(a), id(b)) # 40648584 40647432

<class 'list'> <class 'list'>
2809380025544 2809379306504

추가,삭제,수정,삽입

# 추가,삭제,수정,삽입
num = ['one', 'two', 'three', 'four']

print(num) # ['one', 'two', 'three', 'four']
print(len(num)) # 4

num.append('five') # 추가
print(num) # ['one', 'two', 'three', 'four', 'five']

num.remove('five') # 삭제 
print(num)

num[3] = '4' # 수정 
print(num)

['one', 'two', 'three', 'four']
4
['one', 'two', 'three', 'four', 'five']
['one', 'two', 'three', 'four']
['one', 'two', 'three', '4']

list 연산

# list 결합 
x =  [1, 2, 3, 4]
y = [1.5, 2.5]
z = x + y  # new object
print(z) # [1, 2, 3, 4, 1.5, 2.5]

[1, 2, 3, 4, 1.5, 2.5]

# list 확장 
x.extend(y)  # x 확장 
print(x) # [1, 2, 3, 4, 1.5, 2.5]

[1, 2, 3, 4, 1.5, 2.5]

# list 추가 
x.append(y) # x 추가 
print(x) # [1, 2, 3, 4, 1.5, 2.5, [1.5, 2.5]]

[1, 2, 3, 4, 1.5, 2.5, [1.5, 2.5]]

# list 제곱  
lst = [1, 2, 3, 4] # list 생성

# lst 원소를 2개씩 생성하여 result 저장
result = lst * 2 # 각 원소 연산 안됨 
print(result) # [1, 2, 3, 4, 1, 2, 3, 4]

[1, 2, 3, 4, 1, 2, 3, 4]

# list 사칙연산 : 원소 대상 
print('1.5 * 2 = ', y[0] * 2) # 1.5 * 2 =  3.0

1.5 * 2 =  3.0

# list 정렬과 원소 찾기
print(result) # [1, 2, 3, 4, 1, 2, 3, 4]

result.sort() # 오름차순 정렬 
print(result) #[1, 1, 2, 2, 3, 3, 4, 4]

result.sort(reverse = True) # 내림차순 정렬 
print(result) # [4, 4, 3, 3, 2, 2, 1, 1]

[1, 2, 3, 4, 1, 2, 3, 4]
[1, 1, 2, 2, 3, 3, 4, 4]
[4, 4, 3, 3, 2, 2, 1, 1]

# list에서 원소 찾기
tmp='''
if '원소' in list : 
    참 실행문 : list에 '원소' 포함 
else :
    거짓 실행문 : 미 포함 
'''

import random

r = []
for i in range(5) :
    r.append(random.randint(1,5))

print(r)
    
if 4 in r :
    print('있음')
else :
    print('없음')

[1, 5, 2, 1, 3]
없음

리스트 내포

• list에 for문 포함
• 형식1) 변수 = [ 실행문 for ]
  • 실행순서 : 1.for문 > 2.실행문 > 3.변수 저장
• 형식2) 변수 = [ 실행문 for if ]
  • 실행순서 : 1.for문 > 2.if > [3.실행문 > 4.변수 저장]

# x변량에 제곱 계산
x = [2,4,1,5,7]
# print(x ** 2) # error

lst = [ i ** 2   for i in x ]
print(lst) # [4, 16, 1, 25, 49]

[4, 16, 1, 25, 49]

# 1~10 -> 2의 배수 추출 -> i*2 -> list 저장
lst2 = [ i*2  for i in num  if i % 2 == 0  ]
print(lst2)

[4, 8, 12, 16, 20]

tuple () or tuple()

• 순서존재(index 사용 가능)
• 수정 불가
• 문자열 원소 표현
• list 속도 빠름
• 제공 함수 없음
• 형식) (원소1, 원소2, ...n) : () 생략 가능

#help(tuple) # Help on class tuple in module builtins

# 단일 인수
t = 10 ; t1 = (10, )
t = (10)

print(t)
print(t, t1) # 10 (10,)

10
10 (10,)

# 여러개 인수
t2 = (1,2,3,4,5,3)
print(t2) # (1, 2, 3, 4, 5, 3)

(1, 2, 3, 4, 5, 3)

# index
print(t2[0], t2[1:4], t2[-1]) # 1 (2, 3, 4) 5

1 (2, 3, 4) 3

#  수정 불가 
# t2[0] = 10 # error

for i in t2 :
    print(i, end=' ')

1 2 3 4 5 3 

# 요소 검사
if 6 in t2 :
    print("6 있음")
else :
    print("6 없음")

6 없음

# tuple 함수
lst = list(range(1,6))
t3 = tuple(lst)
print(t3) # (1, 2, 3, 4, 5, 3)
print(len(t3), type(t3)) # 5 <class 'tuple'>
print(t3.count(3)) # 2
print(t3.index(4)) # 4의 색인 위치 값 -> 3

(1, 2, 3, 4, 5)
5 <class 'tuple'>
1
3

---

순서 없는 자료구조 None-Sequence Data Structure

• set, dict 클래스

set {} or set()

• 순서 없음, 중복 허용 불가
• 형식) 변수 = {값1, 값2,...}
• 집합 개념

# 중복 불가
s = {1,3,5,3,1}
print(len(s)) # 3
print(s) # {1, 3, 5}

3
{1, 3, 5}

# for + set 이용
for d in s :
    print(d, end=' ')  # 1 3 5

1 3 5 

# 집합관련 함수
s2 = {3, 6}
print(s.union(s2)) # 합집합 : s + s2 = {1, 3, 5, 6}
print(s.difference(s2)) # 차집합 : s - s2 = {1, 5}
print(s.intersection(s2)) # 교집합 : {3}

{1, 3, 5, 6}
{1, 5}
{3}

# 추가, 수정, 삭제 함수
s3 = {1, 3, 5}
print(s3)

{1, 3, 5}

# 원소 추가 
s3.add(7) 
print(s3) # {1, 3, 5, 7}

{1, 3, 5, 7}

# 원소 수정
s3.update([5, '다섯'])
print(s3)

{1, 3, 5, 7, '다섯'}

# 원소 삭제
s3.discard(3) 
print(s3) # {1, 5, 7}

{1, 5, 7, '다섯'}

# 중복 데이터 제거
gender = ['남','여','남','여']
sgender = set(gender) # list -> set
lgender = list(sgender) # set -> list
print(lgender) # ['남', '여']

print(lgender[1])

['남', '여']
여

dict {k:v}, dict()

• {'key':value, 'key':value, ...}
• json 형식, R의 list 동일
• key 접근만 가능함(index, value 사용 불가)
• key 중복 불가
• 출력 순서 random

dict 생성 방법1

dic = dict(key1 = 100, key2 = 200, key3 = 300)
print(dic) # {'key2': 200, 'key1': 100, 'key3': 300}

{'key1': 100, 'key2': 200, 'key3': 300}

dict 생성 방법2

person = {'name':'홍길동', 'age': 35, 'address' : '서울시'}
print(person)
print( person['name']) # index : key

{'name': '홍길동', 'age': 35, 'address': '서울시'}
홍길동

print(type(dic), type(person))

<class 'dict'> <class 'dict'>

원소 수정, 삭제, 추가

# dict 원소 수정 
person['age'] = 45
print(person)

{'name': '홍길동', 'age': 45, 'address': '서울시'}

# dict 원소 삭제
del person['address']
print(person) # {'name': '홍길동', 'age': 45}

{'name': '홍길동', 'age': 45}

# dict 원소 추가 
person['pay'] = 350
print(person) # {'name': '홍길동', 'pay': 350, 'age': 45}

{'name': '홍길동', 'age': 45, 'pay': 350}

# 요소 검사
print(person['age']) # 35
print('age' in person) # True

45
True

# 요소 반복
for key in person.keys() : # key 넘김 
    print(key) # key 출력 

name
age
pay

for v in person.values() : # value 넘김 
    print(v) # value 출력  

홍길동
45
350

for i in person.items() : # item 넘김 
    print(i) # ('name', '홍길동')

('name', '홍길동')
('age', 45)
('pay', 350)

# 키로 값 가져오기 : get(key)
print( person['name']) # index 형식
print( person.get('name')) # get함수 -> 홍길동 

홍길동
홍길동

# 내용 지우기 obj.clear()
person.clear()
print(person) # {}

{}

#  {key : [val1, val2]} - {'영화' : [평점, 관객수]}
movie = {'광해' : [9.24, 1200], 
         '공작' : [7.86, 500], 
         '관상' : [8.01, 900],}

for r in movie.items() :
    print(r)

('광해', [9.24, 1200])
('공작', [7.86, 500])
('관상', [8.01, 900])

for r, d in movie.items() :
    print(r, d)   

광해 [9.24, 1200]
공작 [7.86, 500]
관상 [8.01, 900]

문] 평점 8이상인 영화 제목과 누적관객수 출력하기

tot = 0
for r, d in movie.items() :
    if d[0]  >= 8.0 :
        print(r)  # 광해 관상
        tot += d[1]
print('누적 관객수 = ', format(tot, '3,d'))

광해
관상
누적 관객수 =  2,100

[실습] 문자 빈도수 구하기[1]

charset = ['abc', 'code', 'band', 'band', 'abc','band']
wc = {}

for ch in charset :
    if ch in wc :
        wc[ch] += 1 # key이용 : 수정  
    else :
        wc[ch] = 1
        
print(wc) # {'a': 1, 'c': 0, 'b': 1}

{'abc': 2, 'code': 1, 'band': 3}

# 최고 출현 단어
print('max = ', max(wc, key=wc.get)) 

max =  band

# 출현 빈도수 단어 정렬
print(sorted(wc, key=wc.get, reverse=True)) 
print(sorted(wc, key=wc.get)) 

['band', 'abc', 'code']
['code', 'abc', 'band']

[실습] 문자 빈도수 구하기[2]

• get(key, 0) + 1
• 해당 key의 값이 없으면 0, 있으면 기존 값에 +1

charset = ['abc', 'code', 'band', 'band', 'abc']
wc = {}

for key in charset : 
    # get()함수 : key 이용 value 가져오기 
    wc[key] = wc.get(key, 0) + 1 # get() 이용

print(wc)

---

객체 복사

• 얕은 복사 : 객체의 주소 복사
• 깊은 복사 : 객체의 데이터 복사, deepcopy() 사용

# 1. 얕은 복사 : 주소 복사(내용, 주소 동일)
name = ['홍길동', '이순신', '강감찬']
print('name address =', id(name)) 

name2 = name # 주소 복사
print('name2 address =', id(name2)) 

print(name)
print(name2)

name address = 2189825160328
name2 address = 2189825160328
['홍길동', '이순신', '강감찬']
['홍길동', '이순신', '강감찬']

name2[0] = '홍길순'
print(name)
print(name2)

['홍길순', '이순신', '강감찬']
['홍길순', '이순신', '강감찬']

# 2. 깊은 복사 : 내용 복사(내용 동일, 주소 다름)
import copy 
name3 = copy.deepcopy(name)
print(name)
print(name3)

print('name address =', id(name)) 
print('name3 address =', id(name3)) 

# 원본 수정 
name[1] = "이순신장군"
print(name)
print(name3)

['홍길동', '이순신', '강감찬']
['홍길동', '이순신', '강감찬']
name address = 2189825160328
name3 address = 2189825160904
['홍길동', '이순신장군', '강감찬']
['홍길동', '이순신', '강감찬']

# 슬라이스 사용 복사
name4 = name[:]
print('name address =', id(name)) # 2049488
print('name4 address =', id(name4)) # 6933520

name address = 2189825160328
name4 address = 2189825135944

---

알고리즘

• 어떤 문제를 해결하기 위한 일련의 절차

알고리즘 조건

• 입력 : 외부에서 제공되는 자료가 있을 수 있다
• 출력 : 적어도 한 가지 이상의 결과가 나올 수 있다
• 명백성 : 각 명령들은 애매한 부분 없이 간단명료해야 한다
• 유한성 : 반드시 종료 조건이 있어야 한다
• 효과성 : 모든 명령들은 명백하고 실행 가능한 것이어야 한다

1. 최댓값/최솟값

# 입력 자료 
import random

dataset = []
for i in range(10) :
    r = random.randint(1,100)
    dataset.append(r)

print(dataset)

[60, 25, 98, 11, 17, 27, 97, 86, 38, 94]

# 변수 초기화
vmax = vmin = dataset[0]

# 최댓값/최솟값 구하기
for i in dataset:
    if vmax < i:
        vmax = i
    if vmin > i:
        vmin = i

# 결과 출력
print('max =', vmax)
print('min =', vmin)

max = 98
min = 11

max_v = min_v = dataset[0]
size = len(dataset)  # data 길이
idx = 0

while idx < size:  # data 길이 반복
    if dataset[idx] > max_v:
        max_v = dataset[idx]
    if dataset[idx] < min_v:
        min_v = dataset[idx]

print('max = %d, min = %d' % (max_v, min_v))  # max = 45, min = 2

max = 98, min = 11

2. 정렬

# (1) 오름차순 정렬
dataset = [3, 5, 1, 2, 4]
n = len(dataset)
for i in range(0, n-1) : # 1 ~ n-1
    for j in range(i+1, n) : # i+1 ~ n-1
        if dataset[i] > dataset[j] :
            tmp = dataset[i]
            dataset[i] = dataset[j] # 3 5
            dataset[j] = tmp
    print(dataset)

print(dataset) # [1, 2, 3, 4, 5]

[1, 5, 3, 2, 4]
[1, 2, 5, 3, 4]
[1, 2, 3, 5, 4]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

# (2) 내림차순 정렬
dataset = [3, 5, 1, 2, 4]
n = len(dataset)
for i in range(0, n-1) : # 1 ~ n-1
    for j in range(i+1, n) : # i+1 ~ n-1
        if dataset[i] < dataset[j] :
            tmp = dataset[i]
            dataset[i] = dataset[j] # 3 5
            dataset[j] = tmp
    print(dataset)

print(dataset) # [5, 4, 3, 2, 1]

[5, 3, 1, 2, 4]
[5, 4, 1, 2, 3]
[5, 4, 3, 1, 2]
[5, 4, 3, 2, 1]
[5, 4, 3, 2, 1]

3. 검색

• 순차검색, 이진검색
• 이진검색의 검색 속도가 더 빠름
• 이진검색 : 전체 원소가 정렬된 상태에서 중앙 위치를 계산해서 검색 수행

dataset = [5, 10, 18, 22, 35, 55, 75, 103]
value = int(input("검색할 값 입력 : "))

low = 0
high = len(dataset) - 1
loc = 0
state = False
while (low <= high):
    mid = (low + high) // 2

    if dataset[mid] > value:
        high = mid - 1
    elif dataset[mid] < value:
        low = mid + 1
    else: # 찾은 경우
        loc =  mid
        state = True
        break # 반복 exit

if state :
    print('찾은 위치 : %d 번째' %(loc+1))
else :
    print('찾는 값은 없습니다.')

검색할 값 입력 : 55
찾은 위치 : 6 번째