Computer

[백준][C++][DP] 13398 연속합 2

13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 이 문제는 범위를 나누어서 생각해야 하는 문제이다. 그렇기 때문에 top-down 방식보다 bottom-up 방식이 더 풀기 수월할 것 같은 문제이지만, 일단 나는 top-down 위주로 연습하고 있기 때문에 top-down으로 풀이하겠다. 이 문제의 조건은 1912 연속합 문제와 거의 동일하지만 한 가지의 추가 조건이 있는데, 수열에서 수 하나를 뺄 수 있다는 조건이다. 이 추가 조건에 대한 고려로써 먼저 수열에서 수를 첫번째부터 마지막까지 하나씩 빼본 후 테스트하..

[백준][C++][DP] 1932 정수 삼각형

1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net DP만 부시는 중.... 비슷한 유형 계속 풀다보니 확실히 감이 생기는 것 같다. 이 문제의 경우 점화식을 D[n][i] = 크기 n의 정수 삼각형에서 i번째 요소를 마지막으로 선택했을 때의 최대 경로합 으로 정의하면, D[n][i] = max(D[n-1][i-1], D[n-1][i]) + a[n][i] (i != 1 && i != n) D[n][i] = D[n-1][i] + a[n][i] (i == 1) D[n][i] = D[n-1][i-1] + a[n][i] (i == n) 이 된다. 이를 코드로 옮기면 다음과 같다. #inclu..

[백준][C++][DP] 2156 포도주 시식

2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 역시 DP 문제이다. 처음에 이 문제를 풀때는 2차원 배열을 만들어서 D[n][0] = n번째 잔을 마시지 않는 경우 = max(D[n-1][0], D[n-1][1], D[n-1][2]) D[n][1] = n번째 잔을 마시고 연속된 잔의 수가 1인 경우 = D[n-1][0] + a[n] D[n][2] = n번째 잔을 마시고 연속된 잔의 수가 2인 경우 = D[n-1][1] + a[n] 이렇게 풀었는데, 코드가 너무 복잡해지길래 다른 분들의 풀이를 살짝 참고해서 1..

[백준][C++][DP] 11053, 14002 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 가장 긴 증가하는 부분 수열 문제는 LIS 문제라고 부른다. 이 문제에서 주의해야할 점은 점화식에서 D[n]이 정답이 아닐 수도 있다는 것. 이 문제를 풀기 위해서 점화식을 D[n] = '길이 n의 수열에서 n번째 요소가 포함된 부분수열의 최대 길이' 로 정의하였는데, 문제에서 요구하는 것은 '길이 n의 수열에서 부분수열의 최대 길이' 이기 때문에 1부터 n까지의 D[n]값을 모두 검사..

[백준][C++][DP] 10844 쉬운 계단 수

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP, 동적 계획법은 1차원 방식으로 푸는 문제가 있고 2차원 혹은 그 이상의 차원의 배열을 사용하여 푸는 방식이 있다. 이 문제와 같이 마지막 수를 기록해야 하는 경우(연속, 증가 등)에 2차원 배열을 사용한다. 이 문제의 경우 계단수의 몇번째 수인지를 나타내기 위해 n, 마지막 수가 무엇인지를 나타내기 위해 i를 사용하였다. 마지막 수가 0와 9인 경우만 따로 처리를 해주고, 나머지는 점화식을 세워서 풀면 되는 문제 #include long long memo[101][10] = { 0, }; long lon..

[알고리즘] 정렬 알고리즘 - 선택 정렬, 힙 정렬, 병합 정렬, 퀵 정렬

버블 정렬과 삽입 정렬에 대해서는 다음 글을 참고 바랍니다. [백준][알고리즘][C++] 2750 수 정렬하기, 버블 정렬, 삽입 정렬 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수 katteniiki.tistory.com 1. 선택 정렬 선택 정렬은 시간 복잡도가 O(n^2)인 알고리즘입니다. 이름에서 알 수 있듯이 선택 정렬은 정렬 대상 중에 가장 작은 값(가장 앞에 정렬되어야 하는 값)을 선택하여 배치하는 방법입니다. 그런 방식으로 정렬하려면 메모리 공간이 추가적으로 더 필요하겠네? 라고 생..

[백준][C++] 1966 프린터 큐

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 우선순위 큐를 사용하면 간단하게 풀 수 있다. #include #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(NULL); int test; std::cin >> test; while (test--) { int n, m; std::cin >> n >> m; //n은 전체 문서의 개수, m은 원하는 문서의 순서 std::prio..

[C++] 함수 포인터 헷갈리는 부분에 대하여

봐도 봐도 헷갈리는 함수 포인터.... 자료구조를 공부하다가 다음과 같은 코드를 보고 대혼란이 왔다. typedef int (*PriotityComp)(HData d1, HData d2); typedef struct _heap { PriotityComp* comp; //생략 }Heap; void HeapInit(Heap* ph, PriotityComp pc) { //생략 ph->comp = pc; //???? } 아니 대체..... 라인12가 왜 컴파일이 되는 것인가... 내가 알고 있던 함수 포인터는 무엇이었는가... 난 이렇게 살아왔는데...(?) 상태가 되어버림 분명 comp는 PriotityComp* 형이고 pc는 PriotityComp형인데 왜 이런 연산이 가능한 것이지??? 싶어서 별 시도를 ..