크래프톤 정글 week03, day21 - 동적 계획법(Dynamic Programming), 연결리스트(Linked-List), 포인터(Pointer)

동적 계획법(Dynamic Programming)

• 복잡한 문제를 간단한 여러 개의 하위 문제로 분해하여 해결하는 알고리즘 설계 기법
  • 큰 문제를 작은 문제로 나누어 해결하는 분할 정복과 비슷하지만, 다이나믹 프로그래밍은 각 하위 문제들이 서로 연관되어 있고, 작은 문제들의 해결을 통해 전체 문제를 해결한다.
  • 동일한 하위 문제를 반복적으로 해결해야 할 경우, 해결 결과를 메모리에 저장해두고 이를 재사용함으로써 중복 계산을 피해 연산 시간을 단축시키는 것을 메모이제이션(Memoization)이라고 한다.

• 사용을 위한 두 가지 조건
  • 중복 하위 문제 구조(Overlapping Subproblems)
    • 큰 문제와 작은 문제를 같은 방법으로 해결할 수 있으며, 작은 문제의 답을 메모리에 저장하고 필요할 때마다 활용한다.
  • 최적 부분 구조(Optimal Substructure)
    • 문제의 최적의 해가 부분 문제의 최적의 해로부터 구성될 수 있어야 한다.
    • 예시로 피보나치 수열, 0-1 배낭 문제, LCS 등이 있다.

• 예시)
  • 피보나치 문제(재귀 방식)

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return(fibonacci(n-1) + fibonacci(n-2))

• 피보나치 문제는 보통 재귀 형식으로 사용해서 구현을 하지만, 이 경우 입력값이 커지면 계산 시간이 너무 늘어나게 되어 다이나믹 프로그래밍을 이용해 효율적으로 짜는게 좋다

 

• 피보나치 문졔(DP 방식)

•  

def fibonacci(n):
    fib = [0, 1] + [0] * (n-1)
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

 

• DP의 경우엔 리스트에 각 값을 저장해 재활용할 수 있어서 중복 계산을 방지하고 계산 시간을 줄일 수 있다. 이것이 DP의 핵심이다.

---

연결 리스트(Linked-List)

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.
  • 포인터는 다음 노드와의 연결을 담당

• 연결 리스트의 특징
  • 동적 크기
    • 연결 리스트는 노드를 동적으로 할당해 크기를 조절할 수 있다. 이로 인해 필요한 만큼만 메모리를 사용하게 된다.
  • 삽입 및 삭제 용이
    • 데이터의 삽입과 삭제가 배열에 비해 용이하다.
    • 배열의 경우 데이터 삽입 및 삭제 시 해당 위치 뒤의 모든 데이터를 이동시켜야 하지만, 연결 리스트는 추가하려는 위치의 앞 노드와 뒤 노드를 연결하거나 끊는 것으로 간단히 해결이 가능하다.
• 단점
  • 접근 속도
    • 연결 리스트는 배열과 달리 인덱스를 통한 접근이 불가능하며, 특정 위치의 데이터를 찾기 위해선 처음부터 순차적으로 접근해야 한다.
  • 메모리 사용
    • 각 노드가 데이터 외에도 포인터를 저장하므로 추가적인 메모리를 사용하게 된다.

• c언어에서 연결 리스트를 구현하려면, struct를 사용하여 노드를 정의하고, malloc() 함수를 사용해 동적으로 노드를 할당 받아야 한다.
  • 또한 노드를 연결하거나 삭제할 때 포인터를 직접 조작해야 한다. 이로 인해 c언어에서는 연결 리스트의 구현이 다른 언어에 비해 복잡하고 오류가 발생하기 쉽다.

• 리스트와 연결 리스트의 차이

차이점	리스트	연결 리스트
메모리 구조	배열 기반의 구조를 가지고 있어, 데이터들이 메모리 상에서 연속적으로 저장	각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지고 있으며, 이 노드들이 연결되어 있는 구조. 즉, 메모리 상에서 불연속적으로 위치할 수 있다.
데이터 접근	인덱스를 통해 O(1)의 시간 복잡도로 데이터에 접근	특정 위치의 데이터에 접근하려면 처음부터 순차적으로 접근해야 하므로 O(n)의 시간 복잡도를 가진다.
데이터 삽입 및 삭제	데이터를 삽입하거나 삭제할 때는 해당 위치 이후의 모든 데이터를 이동시켜야 하므로 시간 복잡도가 O(n)이다.	데이터를 삽입하거나 삭제할 때 해당 노드의 포인터만 변경하면 되서, 찾는데 걸리는 시간을 제외하면 O(1)의 시간 복잡도를 가진다.
메모리 할당	크기 변경이 빈번하게 일어나면 메모리 재할당과 데이터 복사로 인한 비효율이 발생할 수 있다.	필요할 때마다 노드를 동적으로 생성하여 메모리를 할당하므로 이러한 문제가 없다.

---

포인터

• 메모리의 주소를 저장하는 변수
  • 어떤 값이 저장된 메모리 위치를 가리키는 역할

• 포인터를 선언할 때는 자료형 뒤에 별표(*)를 붙여서 선언한다.
  • 예를 들어 int *p; 라는 선언은 p가 정수형 값을 가진 메모리의 주소를 저장하는 포인터임을 의미한다.

• 포인터를 사용하면 메모리의 특정 위치에 직접 접근이 가능해, 배열이나 함수, 동적 메모리 할당 등 다양한 곳에서 활용된다.

• 포인터를 사용하는 이유
  • 동적 메모리 할당
    • malloc(), calloc() 등의 함수를 사용하여 런타임 중에 메모리를 동적으로 할당하고, 포인터를 통해 이 메모리에 접근할 수 있다.
  • 배열과 문자열
    • 배열 이름은 배열의 첫 번째 원소를 가리키는 포인터로 사용되며, 문자열은 문자 배열의 포인터로 표현된다.
  • 함수의 인자 전달
    • 포인터를 통해 함수의 인자를 전달하면, 원래 변수가 저장된 메모리 위치를 직접 접근해 값을 변경할 수 있다. 이를 통해 함수에서 여러 개의 값을 반환하거나, 큰 데이터 구조를 효율적으로 전달 가능하다.

​

​

학습 시간 : 14시 ~ 25시