SEB_BE_43 / 23.01.19 회고

rse·2023년 1월 19일
0

코드스테이츠_BE_43

목록 보기
20/65

오늘

  • 시간복잡도
  • 탐욕 알고리즘
  • 완전 탐색 알고리즘
  • 이진 탐색 알고리즘

의사 코드 작성 (pseudocode)

의사 코드란 코드를 작성할 때 어떻게 작성을 할 것인지 적어두는 것을 의미한다.
다른 말로 수도 코드, 로직 이라고도 말한다.
의사 코드를 작성하고 그것을 바탕으로 코드를 작성하면 더 빠르고 깔끔하게 코드를 짤 수 있다.
의사 코드는 필수로 작성하자.

시간 복잡도 (time complexity)


출처 https://www.bigocheatsheet.com/

탐욕 알고리즘 (Greedy)

Greedy = 최대한 이득을 볼 수 있는 방법을 생각.
매 순간 최적이라고 생각되는 해답을 찾고, 해답 도출.
예시를 들어보자.
A마트에서 과자 이벤트를 한다. 그런데 무게가 정해져 있고 그 무게 안에서 과자들을 담을 수 있는데 과자 종류는 이렇게 있다.

  • A과자 40g
  • B과자 20g
  • C과자 34g
  • D과자 15g

정해진 무게는 40g이라고 했을 때 어떻게 하면 가장 효율적으로 과자를 담을 수 있을까?

이럴 때 탐욕 알고리즘을 사용하여 구할 수 있다.

다만 탐욕 알고리즘은 현재 결정한 해답이 최적이 아니게 된다면 쓰지않는 것이 좋다.
대표적인 예시로 마시멜로 실험이 있다.

마시멜로 실험은 지금 마시멜로를 받겠다 라고 하면 1개를 받을 수 있지만 1분을 기다리면 2개를 받을 수 있는 실험이다. 

이런 상황에서 greedy 알고리즘은 지금 받겠다가 최적이라고 판단하지만 1분을 기다리면 2개를 받는 것이 이 상황에서는 최적이 되는 것이다.
그렇기에 greedy를 사용할 때는 이 조건을 생각해보고 사용하는 것이 좋다.

탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

연습문제

완전 탐색 알고리즘

profile
기록을 합시다

0개의 댓글