본문 바로가기

알고리즘

트리의 최대 지름 트리 노드간의 최대 지름을 구하는 방법은 간단하다 1. 먼저 임의의 노드를 하나 선택한다음 최대거리의 노드를 구한다 2. 구한 노드를 다시 선택하여 그 노드의 최대거리가 트리에서 얻을수 있는 제일긴 노드간의 거리이다. 코드 - 백준 1167 트리의 지름 https://www.acmicpc.net/problem/1167 #include #include using namespace std; #define sync() { ios_base::sync_with_stdio(0); cin.tie(0);} #define endl '\n' struct Edge { int to, weight; }; vector graph; vector visit; int res, idx; void dfs(int i, int x) { if.. 더보기
LIS 최장 증가 수열 예를들면 3 1 2 4 8 6 7 라는 배열이 있다면 가장 길게 증가하는순으로 정렬된 배열을 말한다 위 예제에선 1, 2, 4, 6, 7 이 가장 긴 증가 부분수열이다. DP를 이용해 손쉽게 n^2 시간으로 풀수있다. arr = [3, 1, 2, 4, 8, 6, 7] n = len(arr) dp = [1] * n for i in range(1, n): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j] + 1) res = max(dp) 하지만 n의크기가 10만정도로 커진다면? 바로 nlgn 으로 풀수있는 알고리즘이 존재한다. 원리는 임의의 배열에 입력이 들어올때마다 정렬된 형태를 유지하며 가장 큰값보다 큰입력이 들어올경우 새로 추가하고 그것이.. 더보기
펜윅트리로 최소값구하기 펜윅트리란 어떤 배열의 특정구간 구간합과같은 쿼리가 많을경우 별도의 특별한 트리구조를 만들어 이를통해 시간복잡도문제를 해결하기 위한 자료구조입니다. 펜윅트리말고도 이와같은 트리로 세그먼트트리도 있으나 개인적으로 펜윅트리가 구현하기 깔끔하고 필요한 트리를 만들기위한 메모리를 절약할수 있으며 속도도 왠만하면 더 빠른기대값을 얻을수 있습니다. 하지만 펜윅트리로는 최소값, 최대값같은 구간값을 일반적으로 구할수가 없습니다. 구간합 같은경우 A - B 구간의 합을 구할때 1-B까지의 구간합 - 1-A까지의 구간합을 통해 계산하며 되지만 최대값 최소값같은경우 펜윅트리의 구조상 생략되는 값이 존재하기때문입니다. 펜윅트리는 어떤수를 2진수로 표현할때 1의 위치, 개수에따라 값을 구하는 방식으로 만들어지는 방식을 살펴보면.. 더보기
알고리즘 기본지식 프로그래밍은 결국 문제해결을 위한 수학자들이 만들어낸 도구다. 무언가를 만들어내는 마법같은것들이 아닌 여러가지 작은문제들이 모여 프로그램을 만드는것이다 소프트웨어 설계에도 각 단계들이 존재하듯이문제해결에도 단계가있다(필수는 아니고 딱히 정해진것은 없지만 도움은 된다)1. 문제를 이해하는것이다. 가장 중요한 단계로 문제를 제대로이해하지못하면 아무리 코딩능력이 뛰어나도 소용이없다.2. 문제를 전산화하는것이다. 즉 문제를 컴퓨터입장에서 바꿔보는것이다.3. 문제를 해결할 알고리즘과 자료구조를 결정한다. 4. 결정한 알고리즘과 자료구조에 오류는없는지 체크한다 5. 결정한 알고리즘과 자료구조를 코딩하여 실행한다. 6. 실행한 알고리즘이 성공하든 실패하든 1~5 단계들을 다시한번 생각해보고 개선점은 없는지 생각해본다.. 더보기
소수 구하기 일반적인 방법으로 1~n (n : 구하고자 하는수) 를 소수로 나눠지는지 n % i 이런식으로 구하면 대략 O(n)의 시간이 걸린다그런데 n의 제곱근 까지 구한후 나머지가 1보다 큰수를 저장하면 모든 소수를 구할수 있다 대략 O(제곱근(n)) 시간이 걸리는데코드를 살펴보자 import math def factor_simple(n): arr = [] if n >= 10: sqrtn = int(math.sqrt(n)) + 1 else: sqrtn = n for div in range(2, sqrtn): while n % div == 0: n //= div arr.append(div) if n > 1: arr.append(n) return arr n = int(input()) for i in factor_si.. 더보기
멱집합 구하기 획기적인 방법이 있다 바로 비트마스크를 이용하는 방법이다 (나는 정말 획기적이라고 느꼈다.) 예를들면 원소의개수가 3개 (a, b, c)가 있다치면이걸 비트마스크로 표현하면 000 // 공집합001 // c010 // b011 // b, c100 // a101 // a, c110 // a, b111 // a, b, 이런식으로 모든 부분집합 즉 멱집합을 구할수 있다 소스코드def powerset(s): #배열생성이 generate 방식이다 x = len(s) masks = [1 더보기

티스토리툴바