자료구조 복제 및 알고리즘(algorithm)

자료구조 복제

자료구조 복제(copy)란 객체의 주소를 복사하는 것을 의미합니다. 객체의 주소를 복사하는 방법에는 객체의 주소를 그대로 넘겨주는 얕은 복사와 객체의 내용만 넘겨주는 깊은 복사가 있습니다. '깊은 복사' 용어는 copy 모듈에서 제공하는 deepcopy() 함수에 의해서 붙여진 이름입니다.

 

실습 객체 주소 복사

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

name address = 139974885811776

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

print(name)
print(name2)

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

# 원본 수정
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 address = 139974885811776
name3 address = 139974903229952

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

['김길동', '이순신장군', '강감찬']
['김길동', '이순신', '강감찬']

# (1) 얕은 복사 : 주소 복사(내용, 주소 동일)

'name2=name' 명령문은 name이 참조하고 있는 주소를 name2 참조변수에 넘겨주는 형식으로 주소가 복사됩니다. 얕은 복사를 하면 원본 객체의 원소가 수정되면 사본 객체도 함께 수정됩니다.

 

# (2) 깊은 복사 : 내용 복사(내용 동일, 주소 다름)

copy.deepcopy(name) 명령문은 copy 모듈에서 제공하는 deepcopy() 함수에 의해서 name이 참조하고 있는 내용만 넘겨주는 형식으로 복사됩니다. 깊은 복사를 하면 원본 객체의 원소가 수정되면  원본과 사본은 서로 다른 주소를 참조하기에 사본 객체의 원소는 변경되지 않습니다.

 

알고리즘(algorithm)

□ 입력 : 외부에서 제공되는 자료가 있을 수 있습니다.

□ 출력 : 적어도 한 가지 이상의 결과가 나올 수 있습니다.

□ 명백성 : 각 명령들은 애매한 부분 없이 간단명료해야 합니다.

□ 유한성 : 반드시 종료 조건이 있어야 합니다.

□ 효과성 : 모든 명령들은 명백하고, 실행 가능한 것이어야 합니다.

 

최댓값/최솟값(max/min)

전체 자료의 원소 중에서 가장 큰 값과 가장 작은 값을 선별하는 가장 기본적인 알고리즘입니다.

 

실습 최댓값/최솟값 알고리즘 예시

# (1) 입력 자료 생성
import random
dataset = []
for i in range(10) :
	r = random.randint(1, 100)
    dataset.append(r)
print(dataset)

[33, 13, 27, 33, 5, 17, 6, 82, 92, 96]

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

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

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

max = 96  min = 5

 

# (1) 입력 자료 생성

알고리즘에서 사용할 자료를 생성합니다. 1~100 사이의 임의의 난수 정수를 10개를 생성하는 예문입니다.

 

# (2) 변수 초기화

최댓값과 최솟값이 저장될 변수에 초기값으로 dataset의 첫 번째 원소를 두 변수에 똑같이 할당합니다.

 

# (3) 최댓값/최솟값 구하기

dataset의 전체 원소를 하나씩 비교하여 최댓값/최솟값을 구합니다. 최댓값 변수(vmax) 보다 더 큰 원소가 나타나면 해당 값으로 교체하고, 최솟값 변수(vmin) 보다 더 작은 원소가 나타나면 해당 값으로 교체합니다.

 

# (4) 결과 출력

최댓값과 최솟값을 출력하고, 프로그램을 종료합니다.

 

정렬(sort)

전체 자료의 원소를 일정한 순서로 나열하는 알고리즘입니다. 작은 수에서 큰 수로 정렬하는 방식을 오름차순(ascending sort)라고 하고, 큰 수에서 작은 수로 정렬하는 방식을 내림차순(descending sort)라고 합니다. 정렬 알고리즘은 선택정렬(selection sort), 버블정렬(bubble sort) 등이 있습니다.

 

※ 선택정렬

3

5

1

2

4

각 회전별 정렬 내용

회전	정렬 내용
1회전	[1, 5, 3, 2, 4]
2회전	[1, 2, 5, 3, 4]
3회전	[1, 2, 3, 5, 4]
4회전	[1, 2, 3, 4, 5]

정렬 과정을 살펴보면 각 회전이 종료될 때마다 전체 원소 중에서 가장 작은 값이 왼쪽의 첫 번째로 옮겨지는 것을 알 수 있습니다. 다음 회전에서는 기준변수의 위치가 오른쪽으로 한 칸씩 이동됩니다. 비교변수의 시작은 항상 기준변수보다 하나 더 큰 위치(i+1)부터 시작해서 n까지 한 칸씩 이동합니다.

실습 선택정렬 알고리즘 예시

# (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
    	if dataset[i] > dataset[j] :
        	tmp = dataset[i]
            dataset[i] = dataset[j]
            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
        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, 3, 1, 2, 4]
[5, 3, 1, 2, 4]
[5, 3, 1, 2, 4]
[5, 3, 1, 2, 4]
[5, 3, 1, 2, 4]
[5, 3, 1, 2, 4]
[5, 4, 1, 2, 3]
[5, 4, 1, 2, 3]
[5, 4, 2, 1, 3]
[5, 4, 3, 1, 2]
[5, 4, 3, 1, 2]
[5, 4, 3, 2, 1]
[5, 4, 3, 2, 1]

# (1) 오름차순 정렬

5개의 원소를 갖는 dataset 변수를 대상으로 오름차순 정렬하는 과정입니다. 기준변수의 값과 비교변수의 값을 비교하여 기준변수의 값보다 더 작은 값이 나타나면 기준변수의 값과 비교변수의 값을 서로 교체합니다.

 

# (2) 내림차순 정렬

오름차순 정렬에서 이용된 조건식만 if dataset[i] < dataset [j]으로 변경하면 됩니다. 기준변수의 값보다 더 큰 비교변수의 값이 나타나면 기준변수의 값과 비교변수의 값을 서로 교체합니다.

 

검색(search)

검색 알고리즘은 크게 순차검색과 이진검색 방식이 있습니다. 알고리즘의 시간 복잡도를 비교할 때, 순차검색 알고리즘보다 이진검색 알고리즘이 훨씬 좋습니다. 검색 속도만 보면 이진검색이 빠르지만, 정렬에 필요한 시간 복잡도까지 고려해서 적합한 알고리즘을 선택해야 합니다.

 

※ 이진검색(binary search)

전체 원소가 정렬된 상태에서 중앙 위치(mid)을 계산하여 절반은 버리고, 나머지 절반을 대상으로 검색을 수행하는 알고리즘입니다. 알고리즘의 시작은 start와 end 변수를 이용하여 정 중앙 위치를 갖는 mid 변수를 계산합니다.

 

실습 이진검색 알고리즘 예시

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

low = 0 # start 위치
high = len(dataset) - 1 # end 위치
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 번째

오름차순 정렬된 8개의 원소를 갖는 dataset 변수를 대상으로 키보드로 입력한 값을 이진 검색 알고리즘으로 찾는 과정입니다. low는 시작 위치, high는 끝 위치를 갖는 변수이고, loc 변수는 찾은 값의 색인을 저장할 변수이며 state는 값의 유무를 알려주는 상태변수입니다. while은 시작 위치가 끝 위치보다 작거나 같은 반복을 수행합니다.