컴퓨터 알고리즘 - 순환, 그리디 알고리즘 (5/1)

최수환·2023년 5월 1일
0

컴퓨터 알고리즘

목록 보기
9/14
post-thumbnail

순환 (Recursion)

  • 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
  • 정의 자체가 순환적으로 되어 있는 경우에 적합
  • 대표적으로 팩토리얼 값 구하기와 피보나치 수열 문제가 있다.

팩토리얼 프로그래밍

  • (n-1)! 팩토리얼을 현재 작성중인 함수를 다시 호출하여 계산
int factorial(int n)
{
    if (n<=1) return(1); # 순환의 종료조건
    else return (n*factorial(n-1)); # 순환 본문
}
  • 순환의 종료조건이 순환을 하는 본문보다 반드시 먼저 있어야 한다.
  • 반복문 (for문)을 이용해서도 구할 수 있고, 코드의 길이도 큰 차이는 없지만, 가독성이 떨어지고 복잡한 문제는 코드도 길어진다.

< 순환의 비효율성 >

  • fibo(3)을 이미 구했지만 다른 fibo값을 구할때 중복적으로 구한다.
  • memoization을 사용하는 DP 알고리즘을 이용하여 해결 가능!

그리디 알고리즘

Greedy method : 매 단계 가능한 해들 중 가장 좋은 해를 찾는 기법
= 항상 매 순간마다 최선의 선택을 한다.

동전 거스름돈 문제

  • 물건을 사고 거스름 돈을 동전으로만 받아야 하는 상황에서, 가장 적은 수의 동전을 받을 수 있는 방법은 무엇인가?
    단, 동전으로는 500원, 100원, 50원, 10원이 사용된다.
    -> 500원을 사용할 수 있는 만큼 사용하고, 이후에 100원, 50원, 10원을 사용할 수 있는 만큼 사용한다.

< 동전 거스름돈 문제의 특수한 경우 >

만약 160원 동전이 추가 발행된다면, 그리디 알고리즘이 항상 최소 동전 수를 계산할 수 있을까?

  • 그리디 알고리즘: 거스름돈이 200원이라면, 160원 동전 1개와 10원 동전 4개로서 총 5개를 리턴
  • 그리디 알고리즘은 항상 최적의 답을 주지는 못함
  • 동전의 종류가 서로 약수,배수의 관계라면 그리디 알고리즘은 항상 최적의 해를 구해준다.

부분 배낭 문제

  • n개의 물건이 각각 1개씩 있고, 각 물건은 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 때, 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제
  • 두개의 문제로 나뉜다.

-> 부분 배낭 문제

  • 물건을 부분적으로 담는 것을 허용
  • 그리디 알고리즘으로 해결 가능

Greedy method: 단위 무게 당 가장 값나가는 물건을 반복해 배낭에 넣는다.

  • 만일 물건을 '통째로' 넣을 수 없으면, 넣을 수 있을 만큼만 부분적으로 배낭에 넣는다.
  • 입력: n개의 물건, 각 물건의 무게와 가치, 배낭의 용량 C
  • 출력: 배낭에 담은 물건 리스트 L과 배낭 속의 물건 가치의 합 V

-> 0-1 배낭 문제

  • 부분 배낭 문제의 원형으로 물건을 통째로 배낭에 넣어야 한다.
  • DP 알고리즘으로 해결 가능
profile
성실하게 열심히!

1개의 댓글

comment-user-thumbnail
2023년 5월 12일

잘생겼다

답글 달기