[240109] 알고리즘 특강 02. 알고리즘 & 파이썬 코드카타

[알고리즘 특강 with 분석가 by 임정 튜터]

 

0. 알고리즘

 

1. 그리디 알고리즘(Greedy Algorithm); 탐욕 알고리즘

- 매순간 가장 좋아보이는 것을 선택하여 문제를 풀어가는 방법

- ex.거스름돈 문제: 1,260원 거슬러줘야 할 때 최소의 동전을 줄 수 있도록 동전별 개수 구하기

└ 유사한 문제 예시 https://www.acmicpc.net/problem/5585

 

2. 완전탐색(Brute Force)

- 모든 경우의 수를 다 찾는 방법

- 알고리즘 문제에서 가장 먼저 접근하는 방법으로 단순하고 확실하지만 시간복잡도가 높아질 가능성이 농후 

- ex.3자리 숫자 자물쇠를 푸는 가장 쉬운 방법은 000~999를 모두 맞춰보는 것.. 

 

3. 이분탐색

- 숫자를 이진법에 맞춰 2개로 나눠서 탐색하는 방법으로, Up Down 게임과 이치과 같음 

- 알고리즘에 따라 성능이 향상되는 것을 보여주는 단적인 사례 

- 계속 절반씩 나눠서 진행하므로, O(logN)의 시간복잡도를 가져 이분 탐색이 유효하게 됨 

이분탐색 logic

4. 재귀

- 재귀함수는 코드적인 면에서는 효율적이지만 배우는 입장에서는 꽤 난해한 방법 

- 팩토리얼 예시 

└ 2! = 1*2 

└ 5! = 1*2*3*4*5 

└ 이것을 코드로 구현한다면? 

#재귀 미사용
def factorial(n):
	num = 1
    for i in range(1, n+1):
    	num = num*i
    return num

#재귀 사용
def factorial(n):
    if n <= 1 :
    	return 1
    else: 
    	return n * factorial(n - 1)

(재귀 원리)

- 팩토리얼을 구하는 함수 f를 도식화하면 ↓ (Stack과 유사한 구조)

(cf) 알고리즘 공부

---

[파이썬 코드카타]

1. 배열의 평균값 https://school.programmers.co.kr/learn/courses/30/lessons/120817

 

1) 어떤 문제가 있었나 2) 내가 시도해본 건 무엇인가 3) 어떻게 해결했나

평균값을 구하는 문제를 for문을 활용해서 해결 

def solution(numbers):
    answer = 0
    for num in numbers:
        answer = answer + num
    answer = answer / len(numbers)
    return answer

4) 무엇을 새롭게 알았나

다른 사람 풀이를 보니, for문 안써도 sum 함수로 리스트에 있는 값을 모두 더할 수 있었음 

def solution(numbers):
    return sum(numbers) / len(numbers)