절취선 블로그

[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,..

목표 앞뒤가 똑같은 숫자를 확인해보자 Palindrome 변수 타입에 상관없이 변수를 역전후 초기값과 비교하면된다. 반복문을 사용하여 ex) x =123; int temp => 3 -> 30 + 2 -> 300 + 20 + 1 요런식으로 계산하면 된다. class Solution { public boolean isPalindrome(int x) { if(xnum){ num=num*10+temp%10; temp/=10; } // System.out.println(ans); return ((num==temp) || (num/10)==temp); } } Linked List 문제는 어떻게 접근할까? Linked List 문제의 경우에는 내부 변수가 Integer 타입이며 만일 Integer 범위에서 벗어나는 ..

목표 이건 공부해도 모르겠더라 BackTracking 백트래킹 알고리즘이 모든 경우의 수 brute force와 비슷해서 이해를 못하는 듯 하다. 누가 정리한 백D브 차이 백트래킹 vs DFS 백트래킹은 이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법으로, 반드시 DFS만으로 가능하지 않고 BFS등으로도 가능한 기법이다. 즉, 정리를 하자면 백트레킹은 하나의 문제 해결 방법론이고 이러한 백트레킹을 구현하는 방법론 중 하나가 DFS이다. 백트래킹 vs 브루트포스 브루트 포스는 모든 경우의 수를 탐색하는 문제 해결 방법론이다. 이와 달리, 백트래킹은 단계마다 조건을 충족하는지 검사하여 조건을 충족하는 경우에만 계속해서 탐색한다. 즉, 정리를 하자면 브루트포스 모든 가지를 탐색하는..

최대 부분 합 구하기 SSAFY 7기 CT 문제에 출제되었던 문제로 1차원 배열에서 가장 큰 값을 가질 수 있는 연속적인 부분 배열을 찾는 문제에 사용되는 알고리즘이다. 많은 문제들이 시간, 공간 복잡성이 적은 카디안 알고리즘을 적용한 문제풀이를 선호한다. 카디안 알고리즘에서는 시,공간 복잡성이 O(n) 으로 다음과 같이 구현한다. LeetCode 53. Maximum Subarray 문제 링크 public int maxSubArray(int[] nums) { int sum = 0; int max = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++){ sum+= nums[i]; max = Math.max(sum, max); if (sum < 0) sum..

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) 공통 원소가 없는..