본문 바로가기

코딩 테스트

 (74)
백준 투포인터 2230 start end 를 두고 특정 기준 m 에 따라 start 혹은 end 를 ++ 하면서 풀어가면 모든 경우의 수를 확인 가능하다.O(n) 정도로 그럭저럭.... #include #include #include #include #include using namespace std;int n, m;int main(void){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; vector arr(n); for (int i = 0; i > arr[i]; } sort(arr.begin(), arr.end()); int startIdx = 0; int endIdx = 0; int answer = INT_MAX; while (start..
백준 LIS 2 - 12015 배열 크기가 더 커진 LIS 풀이에는 차이가 없다. 중요한건 lower_boung 를 사용해서 lis 의 크기를 유지하면서도 lis 내용을 갱신해준다. #include #include #include #include using namespace std;int main(void){ int n; cin >> n; vector arr(n); for (int i = 0; i >arr[i]; } vector lis; lis.push_back(arr[0]); for (int i = 1; i lis.back()) { lis.push_back(arr[i]); } else { auto iter = lower_bound(lis.begin(), lis.end(), arr[i]); *iter = arr[i..
백준 24060 병합 정렬 #include #include using namespace std;int n, m;int countAnswer = 0;int answer = 0;void merge(vector&, int, int, int);void merge_sort(vector& arr, int start, int end){ if (start & arr, int start, int mid, int end){ int i = start; int j = mid + 1; int t = 0; int size = end - start + 1; vector temp(size); while (i > n >> m; vector arr(n); for (int i = 0; i > arr[i]; } merge_sort(arr, 0, arr.size() ..
백준 11053 LIS 1 #include #include #include #include using namespace std;int main(void){ int n; cin >> n; vector arr(n); for (int i = 0; i >arr[i]; } vector lis; lis.push_back(arr[0]); for (int i = 1; i lis.back()) { lis.push_back(arr[i]); } else { auto iter = lower_bound(lis.begin(), lis.end(), arr[i]); *iter = arr[i]; } } cout
백준 11727 타일링 #include #include #include #include #include using namespace std;vector arr(1001, -1);int Dp(int n){ if (arr[n] != -1) { return arr[n]; } arr[n] = (Dp(n - 1) + Dp(n-2)*2) % 10007; return arr[n];}int main(void){ arr[1] = 1; arr[2] = 3; int n; cin >> n; int a = Dp(n); cout
백준 17829 - 222풀링 쿼드트리로 2*2 행렬을 계속해서 만들자 #include #include #include #include int n;using namespace std;int Recursion(int x, int y, int len, vector>& vec){ // 마지막 2*2 정사각형을 만들기 위해 if (len == 1) { return vec[x][y]; } vector v; int divsize = len / 2; v.push_back(Recursion(x, y, divsize, vec)); v.push_back(Recursion(x, y + divsize, divsize, vec)); v.push_back(Recursion(x + divsize, y, divsize, vec)); v.push_back(Rec..
백준 2493 탑 스택 문제 어렵네... 생각이 안남 #include #include #include #include using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int num; cin >> num; stack> sta; for (int i = 0; i > n; while (!sta.empty()) { if (sta.top().first > n) { cout
백준 1992 쿼드트리 재귀 안쪽에서 for 문 시작과 끝 범위에 대한 생각을 꼭 해야한다.  #include #include #include #include int n;using namespace std;void Recursion(int x, int y,int len, vector>& vec){ bool one = true; bool zero = true; for (int i = x; i > n; vector> vec(n, vector(n, -1)); int k = 0; for (int i = 0; i > str; for (int j = 0; j

티스토리툴바