🎯PS/Algorithm

[Algorithm/Python] 파이썬 itertools에서 combinations, permutations를 사용하지 않고, 조합과 순열 구현

파이썬에서는 순열과 조합을 간단하게 바로 구해볼 수 있다. 그러나, itertools가 기억이 나지 않는 경우를 대비하여 순열과 조합을 직접 구현해보도록 하자. 📌 itertools 패키지의 combinations, permutations 활용 먼저 itertools를 통해 조합과 순열을 구하는 방법이다. ✅ [ CODE ] # 조합 from itertools import combinations arr = [0, 1, 2, 3] print(list(combinations(arr, 2))) # [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] ✅ [ CODE ] from itertools import permutations arr = [0, 1, 2] print(lis..

[Algorithm] DFS와 BFS || Depth-First & Breadth-First Search

❕ 인접 행렬 인접 행렬은(Adjacency Matrix)로 2차원 배열을 이용하여 그래프의 연결 관계를 표현하는 방식이다. INF = 999999999 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) ❕ 인접 리스트(Adjacency List) 리스트로 그래프의 연결 관계 표현하는 방식 graph = [ [] for _ in range(3)] # 노드와 거리 graph[0].append((1, 7)) graph[0].append((2, 5)) graph[1].append((0, 7)) graph[2].append((0, 5)) print(graph) 메모리 : 인접 리스트 win 속도 : 인접 행렬 win 📌DFS (스택) DFS(Depth-..

[Algorithm] DP(Dynamic Programming), 동적 계획법

다이나믹 프로그래밍(Dynamic Programming)은 동적 계획법이라고도 불린다. 이 알고리즘은 똑같은 연산을 계속 반복하지 않고, 한 번의 풀이만으로 해결하고자 하는 알고리즘이다. 큰 문제 하나를 여러 개의 작은 문제로 나누어서 해결하고자 하는 방법이다. ❗ 분할 정복 vs. 다이나믹 프로그래밍 둘의 공통점은 큰 문제 하나를 여러 개의 작은 문제로 나누어서 해결한다는 것이다. 분할 정복과 다이나믹 프로그래밍의 차이점은 DP의 경우, 나누어진 부분 문제가 중복되기 때문에, 재활용할 수 있다는 것이다. 분할 정복의 경우, 나누어진 부분 문제가 중복되지 않는다. ❗ 탑다운(Top-Down) vs. 바텀업(Bottom-Up) 탑다운 방식은 큰 문제를 해결하기 위해서 작은 문제를 호출하며 풀어나가는 방식 ..

[Algorithm] 시간 복잡도 & 공간 복잡도

❕ 시간 복잡도입력에 대해 총 얼마나 오래 걸리는 지를 의미한다. 알고리즘이 진행되면서 연산되는 횟수이다. 빅오 표기법을 사용하여 표현하는데, 빠르게 증가하는 항만 고려하여 표기한다.arr = [1, 2, 3, 4, 5] sum = 0 for i in arr: sum += i print(sum)N개의 입력을 받고 연산 횟수는 N에 비례하기 때문에, 시간 복잡도는 $O(N)$이다. a = 5 b = 7 print(a + b)한 번의 연산만 하기 때문에 시간 복잡도는 $O(1)$이다 arr = [3, 5, 1, 2, 4] for i in arr: for j in arr: print(i + j)N개의 입력을 받고 N X N만큼의 연산이 필요하기 때문에 시간 복잡도는 $O(N^2)$이다. $O(1)$

[Algorithm] 탐욕(그리디) 알고리즘 || Greedy Algorithm

📌 그리디 알고리즘이란?Greedy란 '탐욕스러운'이라는 뜻으로, 탐욕법이나 욕심쟁이 알고리즘이라고도 한다. 그리디 알고리즘은 매 순간 가장 좋은 것을 선택하는 알고리즘이다. 기준에 따라 좋은 것을 선택하는 알고리즘이기에 당장 가장 좋은 것만을 선택해 나아가도 문제가 없는지 기준을 파악할 수 있어야 한다. 그리디 알고리즘은 항상 최적의 해를 찾을 수 있는 것은 아니다. 따라서, 최적의 해를 선택하고 조건을 만족하는지, 해결이 가능한지를 확인해주어야 한다. 예시 문제 2문제 추가📌 거스름돈 찾기그리디 알고리즘에서 가장 기본적으로 풀기 좋은 문제이다.거스름돈으로는 500원, 100원, 50원, 10원짜리 동전들이 있다. 거슬러 줘야 할 동전의 최소 개수를 구하라. (단, 거슬러 줘야 할 돈 N은 항상 10의..