Algorithm/Algorithm
-
[Algorithm] - DFS를 통한 모든 경우의 수Algorithm/Algorithm 2022. 9. 24. 01:49
DFS 특정 Start를 기반으로 Node를 재귀로 타고 들어가 자신이 도착하는 경우의 수를 추출한다. 모든 경우의 수 구하기 아래 경우에서 Node 1에서 4로 가는 경우의 수를 탐색한다고 하여보자. DFS로 구현을 하게 된다면 일반적으로 1-2-3-4 탐색 후 끝나는 것이 일반적이지만, 우리는 모든 경우의 수를 구현해야 한다. 알고리즘 기존의 DFS코드를 활용한다. 이 때 나머지 경우에도 탐색을 해야하기 때문에 Visited edge값을 되돌려주고 임의의 값을 빼준다. 코드 n = 5 edges = [[1,2],[1,3],[2,3],[2,5],[3,4],[3,5],[5,4]] from collections import defaultdict def solution(n,edges): graphs = de..
-
[Algorithm] - 부분합Algorithm/Algorithm 2022. 9. 24. 00:39
부분 합 부분 합이란? 흔히 부분합 알고리즘은 시작점 S 부터 끝점 E까지의 모든 합을 구하는 문제입니다. 하지만, 주어진 시간내에 주어지는 모든 범위의 부분합을 구하기 위해선, 일일이 다 더해주는 것은 비효율적인 일입니다. 임의의 배열을 만들어, 일일히 더하는 것이 아닌 모든 동작을 한번에 하도록 처리하여 주는 것이 주요 목표입니다. O(N) -> O(1) 아이디어 index 2~4까지의 값을 구하려고 합니다. 이 때 부분합은 arr[2]+arr[3]+arr[4]라고 할 수도 있지만, sum[5]-sum[2]와도 같습니다. 만약 부분적으로 특정 값을 빼고 넣어준다고 하여 봅시다. [4,4,4,4,4] 라는 배열에서 1부터 마지막 index까지 6을 추가 2부터 3까지 index만 5를 추가한다고 해봅시..
-
[Algorithm] - LCA ( 최소 공통 조상 )Algorithm/Algorithm 2022. 9. 15. 00:46
LCA ( Lowest Common Ancestor ) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다. 아래 그림에서 노드 13번과 15번 노드의 공통 조상을 찾는다한다. 따라 올라가게 되면 5번 노드가 공통 조상이다. 아래 그림에서 노드 13번과 11번 노드의 공통 조상을 찾는다한다. 따라 올라가게 되면 1번 노드가 공통 조상이다. 알고리즘 1. a,b 노드의 깊이를 파악한다. 2. 깊이가 동일하다면 상위 노드를 찾아가면서 동일한 노드가 나올 때까지 추적 그렇다면 노드의 깊이를 어떻게 파악할 것인가? DFS로 root 노드로 부터 깊이를 미리 구해둔다. 또한, 깊이를 구하면서 자신의 부모 노드를 기억하여 두고 부모 노드로 추적할 수 있게끔 할 수 있어야한다. ..
-
[Algorithm] - 유클리드 호제법 ( 최대 공약수 , 최소 공배수 )Algorithm/Algorithm 2022. 9. 15. 00:21
유클리드 호제법 ( 최대 공약수 ) 2개의 자연수에서 최대 공약수를 구하는 알고리즘 자연수 a , b 가 주어졌을 때 ( a>b 필수조건 ) r = a를 b로 나눈 나머지 값과 같다. a,b = b,r 가 반복되며, r이 0이 될 때 b의 값이 최소 공약수이다. 만약 여러 개의 수의 최대 공약수를 구하기 위해서는 a,b를 구하고 나온 값으로 계속 반복하여 구하면 구할 수 있다. a,b,c => gcd ( gcd(a,b) , c ) def GCD ( a , b ) : if b==0 : return a return GCD ( b , a%b ) print( GCD(78696,19332) ) LCM ( 최소 공배수 ) 최대 공약수를 활용하여 최소 공배수를 구하는 방식 a,b의 곱에서 최대 공약수로 나누면 값 된..
-
[Algorithm] - Bit연산자 부분 집합Algorithm/Algorithm 2022. 9. 7. 16:44
Bit 연산자 Bit연산자로 표현하는 방법을 나타보도록 하겠습니다. 프로그래머스 - 후보키 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42890 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr N이 어떤 집합의 원소 갯수라고 합니다. 특정 부분 집합에 대해 특정 원소가 들어간다 or 들어가지 않는다로 나누어집니다. 이를 원소 갯수만큼 반복하여 생각하면 됩니다. 만약 4가지를 경우의 수로 나타나고 싶다면 각 Index가 표현된 방법을 의미하여, 0001 - 1111로 나타날 수 있다. 그렇기 ..
-
[Algorithm] - 문자열 알고리즘 (KMP 알고리즘)Algorithm/Algorithm 2022. 9. 5. 14:07
문자열 탐색 문자열을 검색하는 상황은 많은 상황에서 쓰입니다. 포털 사이트 키워드 검색에서도 사용될 수 있고, 웹 페이지에서 Ctrl+F 를 눌러서 검색 시 사용될 수 있습니다. 본문에서 찾고자 하는 특정한 String을 패턴이라고도 하는데, 이 패턴을 찾는 방법을 패턴 매칭이라고 합니다. 문자열 검색이라고 생각하면 됩니다. 1. 일반적인 생각 ( Brute-Force ) 본문 문자열의 길이를 M, 패턴의 길이를 N이라 가정 시간 복잡도 : O(NM) 2. KMP 알고리즘(Knuth Morris Partt Algorithm) 접두사와 접미사가 같은 부분부터 다시 매칭하면 된다라는 아이디어 시간 복잡도 : O( N+M ) 1) 접두사( Prefix ) banana -> b / ba / ban / bana ..
-
[Algorithm] - LIS(최장 증가 부분 수열)Algorithm/Algorithm 2022. 9. 5. 13:57
LIS 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열 E.g) [3, 5, 7, 9, 2, 1, 4, 8] 부분 수열 -> [3, 7, 9, 1, 4, 8] / [3, 5, 7, 8] / [1, 4, 8] 길이가 길면서 원소가 증가하는 최장 부분 수열-> [3,5,7,8] 알고리즘 1. DP 각 원소를 돌면서 현재 원소보다 작은 값들(DP) 중 가장 큰 값에다가 연결 각 원소를 돌때마다 하위 원소들에 대해서 완전 탐색이 필요하여 O(N^2) 시간 복잡도 #Init dp = [0]*(n+1); for i in range(n) : for j in range(i) : dp[i] = max(d..
-
[Algorithm] - 정렬Algorithm/Algorithm 2022. 9. 2. 14:06
알고리즘이란? 가정 : 정렬할 데이터가 담긴 배열(리스트)의 각 원소를 O(1) 시간에 접근 가능한가? 결과 : C , Python과 같은 배열인 경우 가능 하지만, 그렇지 않은 경우가 있다. 데이터가 HDD 에 있다면 ? 메인 메모리에 올라와 있어야만 이 가정이 통한다. 정렬 1. 버블 정렬 시간 복잡도 : O(N^2) Stable Sort ( 같은 값이라 하여도 순서를 보장 ) 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환 이 과정을 다시 나머지 n-1개 수에 대해서 반복 2. 삽입 정렬 시간 복잡도 최악의 경우 : O(N^2) , 최상 O(N) Stable Sort ( 같은 값이라 하여도 순서를 보장 ) 정렬 대상이 될 원소를 두 부분으로 나눔 앞은 '이미 정..