💡 TIL/Algorithm

Multi-Armed Bandits(MAB) 알고리즘

0. Multi-Armed Bandits(멀티암드 밴딧) 의 역사 카지노의 고객들은 특정 슬롯머신의 수익률이 좋다는 사실을 경험적으로 알게된다. 또, 한번 대박이 터진 슬롯머신은 한동안 수익률이 좋지 않다는 사실을 알게된다. 어느날, 카지노에 방문한 수학자가 “이 슬롯머신에 어떻게 투자를 하면 최적의 수익을 얻을 수 있을까?” 라는 생각을 하게 된다. 💡 멀티 암드 밴딧은 카지노에서 슬롯머신 투자를 최적화하기 위해 만들어진 알고리즘이다. 정리하자면, N개의 슬롯머신이 있다. 각각의 슬롯머신은 수익률이 다르다. 당장, 고객은 각 슬롯머신의 수익률을 알지 못한다. 여기서 내 돈을 어느 슬롯머신에 걸고 슬롯머신의 암(손잡이)을 내려야 돈을 가장 많이 벌 수 있을까? 여기서 슬롯머신이 밴딧(Bandit)이고, ..

알고리즘 정리

✔ 2022.02.01 기준 내용 추가중 기본 시간 복잡도 입력값과 문제를 해결하는 데 걸리는 시간을 함수 관계로 나타낸 것 즉 실행시간을 기준으로, 알고리즘이 얼마나 효율적인지를 판단할 수 있는 척도 시간 복잡도는 최악의 경우, 최선의 경우, 평균의 경우를 계산 이때 최악의 경우는 Big-O, 최선의 경우는 Big-Ω, 평균의 경우는 Big-θ로 나타낸다. Big O 최악의 경우 알고리즘을 실행시켰을 때, 최대로 걸릴 수 있는 시간(상한 시간) 의미 n이 무한대로 간다고 했을 때 상수항을 제거한 n으로 복잡도를 표현하는 방식 가장 보편적인 방법 "너가 지금 설계한 알고리즘의 시간복잡도가 얼마쯤 되니?" 라고 하면 "O(n logn)정도 됨 " Big-Omega 최선의 경우 알고리즘을 실행시켰을 때, 최..

알고리즘 공부 시작 방법 및 순서

Yena Choi 님의 알고리즘 공부 시작 방법 및 순서 를 읽고 정리한 내용입니다. 알고리즘이란? 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것. 알고리즘의 조건 좋은 알고리즘을 만들기 위해서는 다음과 같은 조건을 충족시켜야 한다. 입력 : 외부에서 제공되는 자료가 0개 이상 존재한다. 출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다. 즉 모든 입력에 하나의 출력- 이 나오면 안 된다. 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다. 유한성 : 유한 번의 명령어를 수행 후 유한 시간 내에 종료한다. 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다 공부 순서 기본 개념 이해 기본 알고리즘 코드 학습 쉬운 문제 풀기 … (어..