절취선 블로그

[LeetCode] 1641. Count Sorted Vowel Strings class Solution: def countVowelStrings(self, n: int) -> int: dp = [[i for i in range(1,6)] for _ in range(n)] for i in range(1,n): for j in range(1,5): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[n-1][4]

🚀 #15. 3SUM 🌠 내 풀이 (3 포인터) class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: # 3 포인터?? answer=[] nums.sort() for i in range(len(nums) -2): p1 = 0 p2 = i+1 p3=len(nums)-1 while p1 0: r -= 1 else: l += 1 return output 🌠 과정 3개의 포인터를 이동해 가며 합이 0인 것을 찾는 방식으로 p1, p3 포인터 범위 내부에서 p2를 for문으로 순회하며 찾아내는 과정이다. 코드레시피 사이트에 따르면 시간 복잡도가 O(n^2)이지만 단순 브루트 포스를 사용할 경우 3중 for문을 사용으로 시간 복잡도가 O(n..

🚀 카카오 실패율 풀이 🌠 내 풀이(틀린것) def solution(N, stages): answer = [] player = [0] * (max(stages)+1) length = len(stages) for i in stages: player[i] += 1 j=0 for i in player: j +=1 if length == 0: fail = 0 else: fail = i / length answer.append((j,fail)) length -= i answer = sorted(answer, key=lambda t: t[1], reverse=True) answer = [i[0] for i in answer] return answer n = 5 stages = [2, 1, 2, 6, 2, 4, 3,..

Spanning Tree 그래프 내의 모든 정점을 포함하는 트리를 의미 n개의 정점을 가지는 그래프의 간선의 수 (n-1)로 이루어져 있다. DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있으며 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다. 최소 신장트리 (MST) Spanning Tree 내에서 노드간의 간선의 합이 값이 최소인 트리를 의미한다. MST Algorithm 을 구현하는 방법은 4가지가 존재한다. 크루스칼 알고리즘 위상 정렬 알고리즘 다익스트라 알고리..

편집거리 알고리즘 Leven Shtein Algorithm 두 개의 문자열 A, B가 주어졌을 때 두 문자열이 얼마나 유사한 지를 알아낼 수 있는 알고리즘입니다. 그러니까, 문자열 A가 문자열 B와 같아지기 위해서는 몇 번의 연산(DELETE / INSERT / REPLACE)을 진행해야 하는 지 계산할 수 있습니다. 예시 두 문자열 s1 , s2 가 주어진다면 s1을 s2로 만드는데 필요한 최소한의 연산을 구하라 s1 = "sunday" / s2 = "saturday" 분석) 두 문자가 같을 경우 어떠한 연산도 수행하지 않는다. 두 문자가 다를 경우 현재 위치 d[i][j]에서 d[i-1][j], d[i][j-1], d[i-1][j-1] 의 요소중에 가장 작은 값에서 +1 을 연산한 값을 배열에 추가한..

Longest Increasing Subsequence(LIS) 최장 증가 부분 수열(Longest Increasing Subsequence) 문제는, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다. 최장 증가 부분 수열 문제는 입력 수열의 길이가 n일 때 O(N^2)의 시간에 풀이가 가능하다. 구현 1. 개념 증가 부분 수열을 만들기 위해서는 2중 loop 문(i, j)으로 순회하면서 하나의 i 이전까지 순열중에서 가장 긴 배열을 선택하면 된다. 모든 index를 순회하면서 각 인덱스의 LIS는 다음과 같다. 최종적으로 위 배열에서 LIS 값은 4 이다. Index(i) arr Index(i) arr i=0 {1} i=4 {..

2021-06-13-Algo-REVIEW Graph Algo? graph 란 Node와 Node사이에 연결된 Edge 의 정보를 가지고 있는 자료구조 Graph Tree 방향성 방향 그래프 혹은 무방향 방향 그래프 순환성 순환 혹은 비순환 비순환 루트 노드 존재 여부 루트 노드 없읍 루트 노드 존재 노드간 관계성 부모와 자식 관계가 없음 부모와 자식 관계 모델의 종류 네크워크 모델 계층 모델 그래프 구현 방법은 2가지가 존재한다. (메모리와 속도 측면에서 다른 결과를 보임) 인접행렬 : 2차원 배열을 사용하는 방식 인접 리스트 : 리스트를 사용하는 방식 Memory space Time 인접 행렬 O(V2) O(1) 인접 리스트 O(E) O(V) 서로소 집합 (Disjoints Sets) 공통 원소가 없는..

1. 공통 식 구하기 초기 공식: (100% - progresses%) / speed = ? day 그러나 (100% - 30%) / 30 = 2 day 값이 산출된다. 이러한 결과를 보상해주기 위해서는 나누 값의 나머지로 보상해주어야한다. day = (100 - progresses[i]) / speeds[i] + ((100 - progresses[i]) % speeds[i] > 0 ? 1 : 0); 2. Stack 공통 식으로 계산된 결과 값은 stack클라스로 peek & pop 으로 값을 비교하여 day의 값이 다음 day보다 작을경우 progresses를 대기하여 동시에 처리하는 과정을 구성한다.

1. 스패닝 트리(STP) 그래프 상에서 모든 노드를 지날 수 있는 경우의 수 2. 최소 스패닝 트리(Minimum Spanning Tree, MST) 최소 스패닝 트리의 정의는 그래프에서 그래프의 모든 정점을 연결하되, 사이클이 존재하지 않도록 모든 정점을 간선으로 연결하는 것을 의미한다. 이때, 간선의 가중치 합을 최소로 하며 연결하여야 한다. - 크루스칼 알고리즘(Kruskal's Algorithm) 크루스칼 알고리즘은 모든 간선에 대해 가장 가중치가 작은 간선부터 연결 (간선 값을 오름차순으로 정렬해야함) 크루스칼 알고리즘 시간 복잡도 :: O(ElgE) - 프림 알고리즘(Prim's Algorithm) 프림 알고리즘은 하나의 시작점을 잡고 시작점과 연결된 정점들에 대해 가장 가중치가 작은 간선부..

1. 하샤드 수 주어진 정수는 각 자리의 자연수의 합으로 나누어지는 수 2. 예) 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수 문제) 양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요.