본문 바로가기

알고리즘225

BOJ 12013 - 248게임 (dp) https://www.acmicpc.net/problem/12013 dp[i][j] : 구간[i,j]~~ 40이하의 자연수가 최대 248개 주어진다. 인접한 두 수가 같다면 1을 더한 값으로 합칠 수 있다. (7,7,1->8,1) 더이상 합칠 수 없을 때까지 합친 후에 남아있는 수 중 가장 큰 수의 최대값을 구해라. dp[i][j] : i~j를 합할때 남아있는 수 중 가장 큰 수. dp[i][i]=a[i] dp[i][j] =if(dp[i][k]==dp[k+1][j]) max ( dp[i][k]+1; ) i~j간격 1부터 차례로 갱신해야 하는 것에 주의. for문의 가장 바깥에 해당하는 것이 간격임. (코드의 sz) 모든 d중 최대값이 정답 #include #include #include #include .. 2020. 2. 7.
BOJ 12012 - Closing the farm (유니온파인드) https://www.acmicpc.net/problem/12012 거꾸로 생각해서 쉬워지는 문제 최대 2e5개의 정점과 간선으로 이뤄진 양방향 그래프가 주어진다. 정점의 개수를 n이라고 할때 쿼리가 n개 들어온다. 각 쿼리에선 정점이 하나 주어지는데(u), 현재 전체 컴포넌트의 수가 1이라면 YES를, 1이상이라면 NO를 출력한 후, 해당 정점과 정점에 연결된 간선을 모두 지운다. 문제 설명대로 완성된 그래프에 간선을 지워가면서 컴포넌트의 수를 log시간 이하로 구하는 것은 매우 어렵다. (불가능한 것 같다) 쿼리를 기록해두고 거꾸로 접근하면, 아무것도 없는 그래프에 정점과 연결된 컴포넌트를 이어주며 컴포넌트의 개수를 유지하는 문제로 바뀐다. 정점u를 추가할 때 이미 그래프에 추가된 정점들에 대해서만 .. 2020. 2. 7.
BOJ 12011 - Splitting the field (세그트리) https://www.acmicpc.net/problem/12011 작년 중순에 동아리에서 소개해줬던 문제. 최대 5만마리의 소들의 좌표가 주어질때, 이 소들을 하나의 펜스에 딱 맞도록 다 들어가도록 할때 그 영억의 넓이 big과 두 영역으로 펜스를 나눠 넣을때 두 영역의 합 small에 대해 big-small의 최소값을 구해라. (좌표 범위 최대 1e9) 한 영역의 크기는 (ymax-ymn)*(xmax-xmn)이다. 펜스가 나눠지는 모양은 다음과 같이 네가지 경우 뿐이다. 1,2번의 경우, x좌표 기준으로 오름차순 정렬한 후 다음과 같이 구할 수 있다. 3,4번의 경우, y좌표 기준으로 오름차순 정렬한 후, 같은 방법으로 구할 수 있다. 구간[l,r] y값 최대, y값 최소, x값 최대, x값 최소를 .. 2020. 2. 7.
선형 자료구조 c++의 vector를 떠올리면 된다. 내부적으론 모두 정적 배열로 구현돼 있다. append()를 할 때 이미 배열이 꽉 차있으면 동적 배열의 크기를 다시 할당해야 한다. 이는 현재 들어있는 원소수에 비례하는 시간이 필요하다. 이 부분을 최적화하지 않는다면 동적배열의 자료의 추가/제거 시간은 선형시간이다. 하지만 크기를 다시 할당할때 현재 있는 원소수*2로 할당한다면 평균 O(1)에 가능하다. 일반적인 양방향리스트의 구현 struct listNode{ int element; listNode * next, prev; } 삭제와 undo - knuth의 dancing link, 조합탐색, UI의 되돌리기에서 쓰임 void deleteNode(listNode* node){ node->prev->next = .. 2020. 2. 7.

티스토리툴바