개발_기록용

0. 배경 지식소수는 1과 자신만을 약수로 갖는 수.앞서 설명한 약수의 개념이 사용되므로 1부터 N까지 수들 중 소수로 판별해야 한다면기존의 시간 복잡도에 N을 곱해서 O(N^2) 혹은 O(N √N) 이다. 더 좋은 방법은 소수가 아닌 수들을 걸러내는 것이다.이 방법이 "에레토스테네스의 체" 이다. 1. 동작 순서https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 1) 2부터 N까지 모든 정수를 적는다.2) 아직 지우지 않은 수들 중 가장 작은 소수를 찾는다. 이를 P라 한다.3) 아직 지우지 않은 수들 중 P의 배수를 크기 순으로 지운다.4) 아직 모든 ..

유클리드 호제법 : 최대공약수(GCD)를 구하는 방법 중 하나!최대공약수를 구하는 방법을 생각해보자.0. 일반적인 접근법N의 약수의 개수를 구하는 방법1) 1부터 N 이하 정수로 N 을 나눠서 나머지가 0이 되는 수의 개수를 찾음=> 시간 복잡도 O(N) 2) 1부터  √N 이하의 정수로 N 을 나눠서 나머지가 0이 되는 수의 개수를 찾고, 그 개수에 2를 곱한다.=> 시간 복잡도 O( √N) 1. 유클리드 호제법호제법 : 서로 나눈다는 것.두 자연수 a, b 에 대해 (a > b) a를 b로 나눈 나머지를 r이라 하면,a와 b의 최대공약수는 b와 r의 최대공약수와 동일. b를 r로 나눈 나머지 r'을 구하고, 다시 r을 r'로 나눈 나머지를 구하는과정을 반복해 나머지가 0이 되었을 때 나누는 수와 a와..

알고리즘 문제를 풀다보면 순열과 조합을 구해야 하는 경우가 많다. 가령 다음과 같은 문제가 있다고 치자.3, 4, 6으로 이루어진 수들 중 364보다 더 큰 수들 가운데 제일 작은 수를 구하시오 그럼 int arr[3] = {3, 4, 6}의 원소들을 순열로 구하면{3, 4, 6}{3, 6, 4}{4, 3, 6}{4, 6, 3}{6, 3, 4}{6, 4, 3} 이렇게 총 6가지가 존재해 {4, 3, 6}을 골라 436을 반환하면 된다. next_permutation 알고리즘https://en.cppreference.com/w/cpp/algorithm/next_permutation bool next_permutation( BidirIt first, BidirIt last ); (1) (constexpr s..

1. 문제https://www.acmicpc.net/problem/11055 2. 분석수열의 각 원소마다 LIS의 길이를 구하고,그 길이보다 적은 LIS를 갖는 원소들 중에서 나보다 값이 작은 원소 위치에서의 합을 비교한다.이 합이 가장 큰 것을 가져와서, 내가 가진 값을 더해 내 위치의 합으로 저장한다. => 이를 위해, 각 위치에서 LIS 길이 계산하고, 가장 큰 합도 저장해두어야 한다. 3. 코드#include using namespace std;int n;int LISRemember[1005];int SumRemember[1005];class Num{public: int N; int Len = 1; int Sum;};Num myNums[1005];// 이분탐색으로 LIS 구하기int binaryS..

1. 문제 2. 문제 분석 https://codeforces.com/problemset/problem/327/A Problem - 327A - Codeforces codeforces.com 이 문제를 풀기 전, Maximum SubArray에 대해 먼저 살펴보자. 생각하기 어려운 부분이지만, 배우고 나면 간단한 풀이이다. ✔ 먼저 정리할 점 🎯 전체 Array에 대해 SubArray의 size가 0도 될까? 🔊 문제에 주어진 조건에 따라 0도 되면 되고, 최소 1이상이면 그거에 맞게 풀면 된다. 🎯 size가 0인 배열의 합은 0임은 자명하다. 그럼 size가 0인 배열의 곱은 0일까? 🔊 size가 0인 배열의 곱은 1이다. 그게 자연스러움. 생각해보면, size가 0인 것에 곱이 무엇이든 간에, si..

https://codeforces.com/problemset/problem/1003/C Problem - 1003C - Codeforces codeforces.com 알고리즘연습 2024.03.15 다이나믹 프로그래밍 프리픽스 썸 (Prefix Sum) 1. not less than k = k 이상 2. k 이상의 연속적인 날들의 평균치 였으므로 k개의 연속적인 날만 확인하면 안되고, 최대 n개의 날들의 평균치까지 함께 고려해야 함. 3. cout.precision(15); 를 먼저 선언하면 cout할 때 소수점 이하 15자리까지 출력이 가능하다. 아래는 정답 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(false); c..

1. 문제 2. 분석 맨 처음엔 루트에서 가장 먼 두 점을 구해서, 그 두 점에서 부터 역으로 부모 노드 쪽으로 올라가다 같은 부모 노드를 보고 있게 되면 (가장 먼 두 점까지의 거리의 합) - (2 * 부모 노드까지의 거리의 합) 의 형태로 구하려 했으나 실패. 하지만, 루트에서 가장 먼 한 점은 결국 이 트리의 지름의 한 점이 된다는 것은 확실하다. 그리고 그 점에서 다시 가장 먼 한 점을 구하면, 지름의 나머지 한 점을 구할 수 있게 된다! 이 아이디어만 가지면 쉽게 구할 수 있었을 텐데, 생각이 나질 않았다. *해당 아이디어는 아래 블로그에서 채용했다. https://codingwell.tistory.com/61 [ 백준 ] 1967번 - 트리의 지름 ( C++ ) dfs를 이용하여 푸는 문제이다..

1. 문제 2. 문제 분석 이름에서 알 수 있듯, 방향 그래프에서의 최단 거리를 구해야 하는 문제이다. 각 edge의 가중치가 양수이므로, 다익스트라 알고리즘을 사용한다! 🎁 방향 그래프에서의 각 edge의 가중치가 음수도 가능하면 벨만-포드 알고리즘을 사용. 3. 풀이 다익스트라 알고리즘 풀이는 2가지 방법이 있다. 쉽게 구현하지만 비효율적. 어렵게 구현하지만 효율적. 전자는 이차원 배열을 이용해 구현하고, 후자는 우선순위 큐를 사용해 구현한다. 이 문제는 시간이 1초로 넉넉치 않으니 우선순위 큐를 사용한 구현 방법을 쓴다! => 각 노드를 보고 난 후의 거리를 저장할 dst 배열도 필요하다! 4. 코드 #include #include #include #define INF 987654321 using ..

1. 문제 2. 문제 분석 가장 많은 사람들이 헤메는 부분이 바로 순간이동의 시간이 0초인 부분이다. 이 조건 하나로, 수빈이의 걷기보다 순간이동이 더 우선순위를 가지게 된다. BFS는 edge간의 가중치가 없고, 무방향 그래프일 경우 최단거리를 찾게 해준다. 다익스트라는 edge간의 가중치가 있을 경우 최단거리를 찾게 해준다. 이 문제는 edge에 해당하는 {뒤로 걷기, 앞으로 걷기, 순간 이동}의 가중치가 서로 다르다. 따라서, 다익스트라 알고리즘을 사용한다. 3. 풀이 여러 풀이 방식이 있으나, deque를 사용하여 풀이해보자. 선입선출(FIFO)의 queue와, 후입선출(LIFO)의 stack의 기능을 모두 갖춘 deque로 앞과 뒷 방향에서 push를 하고, 매번 front의 값을 pop하여 연..

1. 문제 2. 문제 분석 알고리즘 분류 : 다이나믹 프로그래밍 => 점화식 / 이전에 구한 값으로 이번 값을 구한다 이 문제를 시작할 때 헷갈렸던 것이 "가장 긴 증가하는 부분 수열" 이라는 말의 뜻이다. 본래 수열은 이전 값과 크거나 같은 값도 포함하여 증가하는 수열인데, 여기서 정의한 "증가하는 부분 수열"은 중간에 작거나 같은 값이 있으면 이걸 제외하고, 나머지 증가하는 부분만 따서 길이를 나타낸 것이다. 예를 들어, ex) 70 30 50 60 40 80 10 가 주어졌다면, 2번째 줄의 30부터 30 50 60 80 만 따서 증가하는 부분 수열로 보는 것이다. 3. 풀이 주어진 입력의 크기가 1000으로 크지 않지만, 시간이 1초로 짧으므로 2중 for문으로 일일이 비교하는 것은 시간초과로 비..