자료구조 공부 2024.04.18

자료구조

자료구조의 의미

• 데이터를 구조적으로 저장하는 방식

• 데이터의 효츌적인 접근을 위한 자료의 조직, 관리, 저장 - 삽입, 삭제, 수정

자료구조의 필요성

• 메모리를 효율적으로 사용하기 위해(근데 요즘에는 메모리가 좋아져서 큰 상관은 없음)

• 자료구조를 배우면 우리가 할 수 있는 범위가 넓어짐 (임베디드 쪽에선 필수)

# 자료구조
num = [4, 5, 6]
largist_num = 0
#-----------------------

# 문제해결 알고리즘
for i in num:
  if largist_num < i:
    largist_num = i
#-----------------------

데이터 단위

자료형

자료형	Java	C++	C	Python
정수형	int	int	int	int (동적)
긴 정수형	long	long long	long
부동 소수점 수	float	float	float	float
더블 정밀도 부동 소수점 수	double	double	double	float
문자	char	char	char	str
문자열	String	string	char[]	str
불린형	boolean	bool	_Bool (C99 이후)	bool

추가 설명

1. Java:
   • 자바는 강 타입 언어로서 변수의 타입이 실행 전에 명확히 지정되어야 함.
   • long은 int보다 더 큰 정수를 저장할 수 있으며, double은 float보다 더 넓은 범위와 더 높은 정밀도를 제공.
2. C++:
   • C++은 C 언어의 기능을 확장한 것으로, 기본 데이터 타입 외에도 클래스와 템플릿 같은 고급 기능을 지원.
   • long long은 매우 큰 정수 값을 저장하는 데 사용됨.
3. C:
   • C 언어는 가장 기본적인 프로그래밍 언어 중 하나로, 다른 많은 언어들의 기초가 됨.
   • char[]는 문자열을 저장하는 전통적인 방법.
4. Python:
   • 파이썬은 동적 타이핑을 지원하는 고급 언어로, 자료형을 명시할 필요가 없다.
   • 모든 숫자는 int 또는 float로 처리될 수 있으며, 정수의 크기는 메모리가 허용하는 한 무제한이다.

---

자료형	Java (32/64-bit)	C++ (32/64-bit)	C (32/64-bit)	Python (동적)
정수형 (int)	4바이트	4바이트	4바이트	시스템에 따라 변동
긴 정수형 (long)	8바이트	8바이트 (일반적)	4/8바이트	시스템에 따라 변동
부동 소수점 수 (float)	4바이트	4바이트	4바이트	시스템에 따라 변동
더블 정밀도 부동 소수점 수 (double)	8바이트	8바이트	8바이트	시스템에 따라 변동
문자 (char)	2바이트	1바이트	1바이트	시스템에 따라 변동
문자열 (String, string, char[])	참조변수에 따라 달라짐	참조변수에 따라 달라짐	참조변수에 따라 달라짐	시스템에 따라 변동
불린형 (boolean, bool, _Bool)	1바이트	1바이트 (컴파일러에 따라 다름)	1바이트 (컴파일러에 따라 다름)	시스템에 따라 변동

추가 설명

• Java:
  • int, long, float, double의 크기는 자바 플랫폼에 의해 엄격하게 정의된다. char는 유니코드 문자를 위해 2바이트를 사용.
• C++ 및 C:
  • 데이터 타입의 크기는 주로 사용하는 컴파일러와 플랫폼에 따라 다르다. 일반적으로 32비트와 64비트 시스템에서 long의 크기가 다를 수 있다.
  • bool과 _Bool은 일반적으로 1바이트를 사용하지만, 구조체나 배열 내에서는 패딩과 정렬에 따라 다를 수 있다.
• Python:
  • 파이썬은 동적 타입 언어로서 변수에 저장된 데이터의 메모리 크기는 실행 시 결정되며, 운영 체제와 파이썬의 내부 구현에 따라 달라진다.
  • 파이썬의 int는 임의 정밀도를 가지며, 크기가 동적으로 조정된다.

메모리 사용 효율성이란?

메모리 사용 효율성은 시스템이 메모리를 효과적으로 활용하는 정도를 나타낸다.
이는 프로그램이 필요한 만큼의 메모리를 사용하고, 불필요한 메모리 낭비를 최소화하여 성능을 최적화하는 것을 의미.
최적화된 메모리 사용은 시스템의 안정성과 성능을 향상시키며, 비용을 절감할 수 있다.

스택

• 스택은 탑(or 핫케이크)(LIFO)

큐

• 큐는 파이프(FIFO)

그래프

트리

그래프와 트리 비교

알고리즘

선택정렬

# 초기 배열을 정의합니다.
arr = [40, 70, 60, 30, 10, 50]

# 배열의 길이보다 하나 적은 만큼 반복합니다. 마지막 원소는 자동으로 정렬됩니다.
for i in range(len(arr)-1):
    # 가장 작은 원소의 인덱스를 현재 검사하는 위치 'i'로 초기화합니다.
    small_idx = i
    # 현재 위치 'i'의 다음 위치부터 배열 끝까지 비교를 수행합니다.
    for j in range(i + 1, len(arr)):
        # 만약 현재 선택된 최소값보다 더 작은 값을 발견하면,
        # 그 값의 인덱스를 최소값 인덱스로 갱신합니다.
        if arr[small_idx] > arr[j]:
            small_idx = j
    # 내부 루프가 끝나면, 가장 작은 값의 원소와 'i' 위치의 원소를 교환합니다.
    # 이로써 'i' 위치에는 이 부분 배열의 최소값이 위치하게 됩니다.
    arr[i], arr[small_idx] = arr[small_idx], arr[i]

# 정렬된 배열을 출력합니다.
print(arr)

버블정렬

# arr = [40, 70, 60, 30, 10, 50]

# for i in range(len(arr) -1, 0,- 1):
#     for j in range(i):
#         if arr[i] > arr[j + 1]:
#             arr[j], arr[j + 1] = arr[j + 1], arr[j]
# print(arr)

# 초기 배열을 정의합니다.
arr = [40, 70, 60, 30, 10, 50]

# 배열의 마지막 요소부터 시작하여 첫 요소까지 검토합니다.
for i in range(len(arr) - 1, 0, -1):
    # 배열의 첫 요소부터 현재 검토 중인 요소까지 반복합니다.
    for j in range(i):
        # 현재 요소가 다음 요소보다 크면 두 요소의 위치를 교환합니다.
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]

# 정렬된 배열을 출력합니다.
print(arr)

삽입정렬

# 초기 배열을 정의합니다.
arr = [40, 60, 70, 50, 10, 20, 30]

# 배열의 두 번째 요소부터 시작하여 마지막 요소까지 반복합니다.
for i in range(1, len(arr)):
    # 선택된 요소의 인덱스에서 시작하여 배열의 시작 방향으로 검토합니다.
    for j in range(i, 0, -1):
        # 현재 요소가 앞 요소보다 작을 경우, 요소들의 위치를 교환합니다.
        if arr[j - 1] > arr[j]:
            arr[j], arr[j - 1] = arr[j - 1], arr[j]

# 정렬된 배열을 출력합니다.
print(arr)

힙정렬

# 힙 정렬 알고리즘 ----------------------------------------------------

# 책의 코드 ----------------------------------------------------------------------
# 초기 배열을 정의합니다.
arr = [40, 70, 60, 30, 10, 50, 90, 80, 20]

# 주어진 배열의 일부를 최대 힙 구조로 만드는 함수입니다.
def big_heap(a, b):
    # 1부터 b까지 반복하여 배열의 힙 속성을 구성합니다.
    for i in range(1, b + 1):
        c = i
        # 힙 조건을 만족할 때까지 부모 노드와 비교하여 조건을 만족하지 않으면 교환합니다.
        while c != 0:
            r = (c - 1) // 2  # 부모 노드의 인덱스를 계산합니다.
            # 부모 노드의 값이 현재 노드의 값보다 작으면 두 값을 교환합니다.
            if a[r] < a[c]:
                a[r], a[c] = a[c], a[r]
            c = r  # 현재 노드를 부모 노드로 업데이트하여 계속해서 부모와 비교합니다.

# 배열을 힙 정렬하는 함수입니다.
def heap_s(a):
    # 배열의 끝에서부터 시작하여 1까지 감소시키며 정렬합니다.
    for i in range(len(a) - 1, 0, -1):
        big_heap(a, i)  # 배열의 0번째부터 i번째 요소까지를 힙 구조로 만듭니다.
        a[0], a[i] = a[i], a[0]  # 최대 힙의 루트(최대 값)을 배열의 끝으로 이동합니다.

# 배열을 힙 정렬합니다.
heap_s(arr)
print(arr)


# 고쳐진 코드 -------------------------------------------------------------------
def big_heap(a, n, i):
    largest = i  # 루트를 최대로 가정
    left = 2 * i + 1  # 왼쪽 자식 인덱스
    right = 2 * i + 2  # 오른쪽 자식 인덱스

    # 왼쪽 자식이 현재의 최대값보다 크면, 위치를 변경
    if left < n and a[largest] < a[left]:
        largest = left

    # 오른쪽 자식이 현재의 최대값보다 크면, 위치를 변경
    if right < n and a[largest] < a[right]:
        largest = right

    # 최대값이 루트가 아니라면, 루트와 최대값을 교환하고, 변형된 힙을 다시 조정
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        big_heap(a, n, largest)

def heap_sort(a):
    n = len(a)

    # 배열 a를 최대 힙으로 구성
    for i in range(n // 2 - 1, -1, -1):
        big_heap(a, n, i)

    # 요소를 하나씩 추출하여 배열을s 정렬
    for i in range(n-1, 0, -1):
        a[0], a[i] = a[i], a[0]  # 현재 루트(최대값)를 배열의 끝으로
        big_heap(a, i, 0)  # 감소된 힙에 대해 힙 속성을 복원

# 테스트 배열
arr = [40, 70, 60, 30, 10, 50, 90, 80, 20]
heap_sort(arr)
print(arr)

정렬 알고리즘 성능 비교

문제 분류

동전 거스름돈 문제 풀기

그리디 알고리즘 사용

print("거스름으로 바꿀 수 있는 동전 종류: [500, 100, 50, 10]")

res = {500: 0, 100: 0, 50: 0, 10: 0}

u_coin = int(input("고객에게 지불할 돈을 입력해주세요: "))

while u_coin != 0:
    if u_coin >= 500:
        res[500] = u_coin // 500
        u_coin %= 500
    elif u_coin >= 100:
        res[100] = u_coin // 100
        u_coin %= 100
    elif u_coin >= 50:
        res[50] = u_coin // 50
        u_coin %= 50
    elif u_coin >= 10:
        res[10] = u_coin // 10
        u_coin %= 10
    else:
        break

print(f"따라서, 거스름 돈은 동전별 각각 {res}개 지불하면 됩니다.")
if u_coin:
    print(f"10원 미만 : {u_coin}")

그리디 알고리즘은 각 단계에서 현재 상황에서 가장 최적인 선택을 하는 특징을 가지고 있다.
여기서 “최적”은 현재 상황에서 가장 큰 동전부터 사용하여 최대한 적은 동전을 사용하는 것을 의미.
그리디 알고리즘은 각 단계에서 지역적으로 최적인 선택을 하지만, 이 선택들이 전체적으로 최적해를 보장하는 것은 아니다.
그러나 이 코드에서는 동전의 단위가 큰 순서대로 선택하므로 전체적으로 최적의 해를 얻을 수 있다.