알고리즘 스터디(Python반) 8기 3주차

[스터디/8기] 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반)

Week3: Searching

basic

• 에라토스테스트의 체 알고리즘

def prime_list(n):
    sieve = [True] * n

    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           
            for j in range(i+i, n, i): 
            # i이후 i의 배수들을 False 판정
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]

• 플루이드-워셜 알고리즘
  O(n^3) 이라 써먹지는 않을 것 같지만 복기용으로

for k in range(1, n + 1): 
	for a in range(1, n + 1): 
    	for b in range(1, n + 1): 
        	graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

checklist

• from itertools import combinations 로 조합 관련 함수를 사용할 수 있다
  이걸 몰라서 재귀로 열심히 힘들게 풀었음... 모든 경우의 수를 구해야 할 때 떠올리기!

• list(map(sum, combinations(weights, i))).count(m)

• list.append() 의 return 값은 list가 아니다.. 너무 당연한건데 어이없게 이걸로 고생함;

• 탐색할 때, 한 개씩이 아니라 한 줄씩 탐색하는 경우가 있다

• abs(queen[i] - queen[row]) == row - i
  대각선은 기울기이고, 기울기는 세로의 변화량/가로의 변화량이므로 '차이'를 가지고 구한다

• 파이썬에서도 C++과 같이 bit 연산을 사용할 수 있다

• 파이썬에서는 dfs 보다 bfs 가 더 빠르다

comment

• 갑자기 어려워짐 😥😥
  그래서 스터디가 끝난 이후에야 3주차를 리뷰할 수 있었다 ㅋ 4주차는 언제...

• 파이썬은 정말 기능이 많다. 항상 C로 모든 걸 손수 구현하던 나에겐 신세계

• 프로그래머스 기준 level 4인 문제들은 처음 생각이 어려울 뿐, 막상 사용되는 알고리즘은 흔한 알고리즘이고 코드 길이도 길지 않아서 신기하다