패스트터틀

https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. www.acmicpc.net 232010 일경우 반대부터 수를 넣는다. for (int i = N ; i >= 1; i--) { list.add(height[i],i); } 0 -> 6을 0에다가 추가하기 1 -> 5을 1에다가 추가하기 0 -> 4을 0에다가 추가하기 2 -> 3을 2에다가 추가하기 3 -> 2을 3에다가 추가하기 2 -> 1을 2에다가 추가하기 package ..

https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 이 문제를 풀기위해서 dp -> 2xn 타일링 -> 2xn 타일링2 -> 외판원순회 -> 타일채우기 -> bruteforce -> 부분수열의합 -> dp -> -> lis O(n^2) -> list O(nlogn) 문제를 풀고 왔다. 너무나 오래걸렸다. 최장길이를 구하는 lis와 동일한 문제이다. 다만 n..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 기존에 하던 방식에서 굳이 자기보다 작은것들을 찾고 거기서 최댓값을 찾기위해 다 검색을 해야하는가? 라는 의문에서 시작하여서 더 빠르게 진행하는 방식으로 이끌어 갈수있다. X,Y테이블을 만든다. X테이블은 기존하던것처럼 A와 D에관한 테이블이고 Y테이블은 D에관한 테이블이다. table X: (D는 ..

본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다. 목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. - Linear Searching - Binary Searching - Upper,Lower bound - Linear Searching ~~ for(int i = 0 ; i last) return -1; int mid = (first + last) / 2; if (val == arr[mid]) r..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net LIS = Longest Increasing Subsequence, 최장증가수열이다. 주어진 값에서 증가하는 수의 집합들중 가장 큰 원소의 개수를 구하는 방법에 관한 문제이다. 어떠한 알고리즘이 해당문제를 푸는데 최적화된 알고리즘인것을 보장할수있는것은 어떻게 알수가 있을까? 문제를 풀다보니 회의감이 ..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net https://sudeky.tistory.com/126 (Baekjoon) brute-force - (1) 부분수열의 합( + 부분집합 출력) https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 우선 부분수열의 합을 구하기전에 부분집합을 출력하는방법을 할줄 알아야한다. 부분집합을 출력하는방법은 visited로 표현할수있는데 예를들어서 1,2,3,4 를 가지고 부분집합을 구성할때 visited가 1000 이라면 1 visited가 1110 이라면 123 visited가 0011 이라면 34 ... 의 식으로 표현하면 모든 부분집합을 표현할수 있다. pac..

본 포스팅은 블로거가 개발언어의 개념정리 필요를 위한것입니다. 목차와 차례가 뒤죽박죽이며 오직 블로거의 편의목적을 위해 작성되었음을 알려드립니다. - dp - bitmask - lis - dp dp = dynamic programming 의 약자로 단어자체와 개념은 전혀 연관이없으며 쉽게말해서 기억하며 프로그래밍하는것이다. 예를들어서 fibonacci 수열을 구할때 다음과 같이 코딩을 할수있다. 예를들어서 int dp(int x){ if(x==1) return 1; if(x==2) return 2; return dp(x-2) + dp(x-1); } int main(){ cout