www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 가장 긴 증가하는 부분 수열 O(n log n)알고리즘을 이용하여 문제를 해결했다 코드 #include #include #include using namespace std; int n; vector A; vector make_long; vector::iterator it; //가장 긴 증가하는 부분 수열 O(n log n)알고리즘을 이용하여 문제를 해결했다 int main() { cin.tie(NULL); io..

www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 가장 긴 증가하는 부분 수열 O(n log n) 알고리즘을 이용하여 문제를 해결했다. 결과는 전체 개수에서 가장 긴 증가하는 부분 수열의 개수를 빼서 구했다 코드 #include #include #include using namespace std; int n; vector number; vector make_long; vector::iterator it; //가장 긴 증가하는 부분 수열 O(n l..

www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 가장 긴 증가하는 부분 수열 O(n log n) 알고리즘을 이용하여 문제를 해결했다 코드 #include #include #include using namespace std; int n; vector c_port; vector make_long; vector::iterator it; //가장 긴 증가하는 부분 수열 O(n log n) 알고리즘을 이용하여 문제를 해결했다 int main() {..

www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 가장 긴 증가하는 부분 수열 O(n log n)알고리즘을 이용하여 문제를 해결했다 코드 #include #include #include using namespace std; int n; vector A; vector make_long; vector::iterator it; //가장 긴 증가하는 부분 수열 O(n log n)알고리즘을 이용하여 문제를 해결했다 int main() { ..

www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 이 문제에서 주의해야 될 점은 상어가 움직이는 것인데, 상어가 이동하려고 하는 칸이 판의 경계를 넘는 경우 방향을 반대로 바꿔서 이동한다는 성질을 이용하면 현재 상어의 속력 s가 어떤 속력일때와 같은 위치로 이동하는지를 알아내 실제 이동하는 칸을 줄일 수 있다. 코드 #include #include #include #include #include #include #include using n..

www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 분할 정복을 이용하여 문제를 해결하였다. 가운데 기준으로 왼쪽에서 얻어지는 가장 큰 값과, 오른쪽에서 얻어지는 가장 큰 값과 가운데에서 만들어지는 가장 큰 값을 비교하였다. 가운데에서 확장을 할 때는 더 큰 쪽으로 확장을 하였다. 코드 #include #include #include using namespace std; int n; vector input..