아네스의 공부일지

아이디어 일단 오름차순 정렬시키고 for문으로 하나를 픽하고 2개를 찾는 것은 투포인터로 구한다. C++ 풀이 #include using namespace std; typedef long long int ll; int N; ll arr[5001]; pair plll; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); //input cin >> N; for(int i = 0 ; i> temp; arr[i] = temp; } //정렬하고 시작 sort(arr, arr+N); ll mini = LLONG_MAX; //최소값 찾을 변수 for(int i = 0 ; i< N-1; i++) { int lef..

아이디어 위 처럼 K번째 moo string에는 K-1번째 moo string이 앞뒤로 붙고 가운데에 mo...o( o의 개수는 k+2만큼 붙는)string이 추가된다. 일단 input N에 따라 적당한 K값을 구해두고 시작하기 위해 K에 따른 moo string 길이에 대한 점화식은 dp[k-1]*2 +(k+3)이다. 그래서 구해보면 이런식이 나오게 되는데, 이는 pow(10,9)까지만 했던거고 이후 제출땐 10^10까지 구해지도록 했다. 이 범위에 따라 N의 적절한 K값을 구하고 dfs로 들어간다. dfs의 베이스 조건은 K==0일때이고, S(k=0)일때로 보면 되겠다(moo) moo string에서 빨간 mooo... 를 기준으로 좌 / 우로 나눴다. 빨간 moo string영역일때의 첫글자라면 m..

문제 요약 array를 3분할 (left, mid, right) left의 sum [1,3,6,10,15] 이런식으로. 처음에 그냥 탐색으로 풀었다가 Timeout났었고, binary search로 접근하다가 조건이 뭔지 몰라서 한참 헤맸다. 결국 유튜브에 설명한번 보고 binary search로 해결했다. python 치트키인 bisect로 풀었길레, C++로 재구현해서 C++/python모두 제출했다. C++(시간초과 코드) class Solution { public: int dp[100001]; int waysToSplit(vector& nums) { int left,right; int last = nums.size()-1; left = 0; //dp계산. dp[0] = nums[0]; for(in..

일단 자꾸 틀리게 되는 원인이였던, 각 테스트 케이스마다 블록 list인 L을 초기화 안해주고 사용했던거랑, 테스트 케이스 수를 주지 않고 while(cin.eof() != EOF)로 했는데 제대로 작동하지 않았던 점. 위 2개의 원인이 시간을 엄청나게 잡아먹었다. 찾느라 애먹음 ㅠ; 아이디어 1. 투포인터 투포인터는 블록 list L을 일단 정렬 후, 양 끝점에서부터 시작해서 두개의 합이 구멍의 크기와 같으면 결과값을 찾은 것이니 즉각 리턴, 구멍의 크기(target)보다 작다면 head index를 1증가해서 다시 한번 테스트. 크다면 반대로 tail값 -1. 2. 이분탐색 투포인터로 풀었는데, 이분탐색으로도 풀길레 나도 풀어봤다. 마찬가지로 search로 들어가서 둘간의 head, tail간의 합 ..

문제를 간단히 요약하면 공유기를 설치할건데, 가능한 서로 떨어뜨려서 놓고싶다는 문제이다. 그 중 가장 가까운 공유기간의 거리를 최대로 하고싶다. 아이디어 문제를 보고 N은 최대 20만, C는 N에 속해있으며, 집의 위치는 10억이다. 대략 1초의 연산속도를 1억번이라고 봤을 때, O(N)의 속도로 찾는다고 해도 좌표를 통해서 찾으면 10초가 소모되어 timeout이 날것이 분명하다. 그래서 처음엔 집위치 list N은 20만개이므로 이를 일단 정렬하고 가운데 집을 기준으로 어떻게 해보려고 갖은 방법을 시도하다가 결국 아래와 같은 풀이로 접근하게 되었다. 이진탐색 문제들을 풀다보면 이걸 이진탐색으로 어떻게 풀어야하지? 에서 꽉꽉막힌다. 답답하기 그지 없는데, '무엇을 이진탐색 할것인가'에서 무엇을 빠르게 ..

이전에 1로 만들기 1을 풀었던 터라, 그대로 가져와서 백트레킹만 구현해서 제출했다. C++ 풀이 #include using namespace std; int dp[1000001]; vector v; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N,cnt =0; cin >> N; dp[1] = 0; //1부터 시작해서 for(int i = 2; i

와 문제 엄청길다 ㅠㅠ KMP문제인데 이해하는데도 한참걸렸고, 사실 이해한건지 만건지 아직 잘 모르겠다. KMP를 사용하지 않으면 O(n*m)의 시간복잡도를 가지지만, 패턴을 미리 만들어두면 거의 O(N)의 속도로 패턴 매칭을 찾을 수 있다. 간략하게 말하면 makeTable에서 접두사와 접미사에 대한 Table을 미리 만들어 두고, 이를 활용하여 kmp를 진행한다. KMP에 대한 설명은 알고리즘 카테고리에서 다시한번 보도록 하자. C++ 풀이 #include using namespace std; string n,m; int result =0; vector result_vec; vector makeTable(string pattern){ int patternSize = pattern.size(); vec..

KMP이해 잘 안됐는데, 이 영상 보고 이해함.

아이디어 post의 가장 오른쪽 원소를 inorder에서 찾아서 나누면서 분할 정복. C++풀이 #include using namespace std; int n; int inorder[100001]; int postorder[100001]; void solve(pair idx_in, pair idx_post) { int post_left = idx_post.first; int post_right = idx_post.second; int in_left = idx_in.first; int in_right = idx_in.second; cout

아이디어 플로이드 와샬 알고리즘 사용. 동빈나 센세의 글보고 이해하자. 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com C++풀이 #include using namespace std; int n, m; int board[101][101]; void floyd(){ //플로이드는 중간에 거쳐가는것이 핵심이다. for(int k = 1 ; k n >> m; memset(board,0x1f,sizeof(board)); for(int i = 0 ; i> s >> e >> w; if(board[s][e] > w)..