호로그래머

https://www.acmicpc.net/problem/1912

1912번 연속합 문제 역시 DP를 사용하는 문제입니다.

문제에서 주어진 예제를 사용하여 arr배열이 넣었습니다.

여기서 DP[i]는 arr[i]까지의 연속합의 최대값이라고 할 수 있습니다.

초기값은 역시 자기 자신으로 시작합니다.

두번째 부터 선택을 할 수 있습니다. 10-4 = 6 을 선택할것인지 또는 자기 자신인 -4를 선택할 것인지.

DP[i]는 연속합의 최대값이기 때문에 6을 선택하겠습니다.

3번째 역시도 6+3 = 9와 자기 자신 3을 선택해야하는데 최대값인 9를 선택해줍니다.

그렇게 쭉 칸을 채워나가다가 12를 만나면

위와같이 -14+12 = -2 보다 자기 자신인 12를 선택하는 경우도 나옵니다.

이렇게 표를 다 채우면 최대값은 21일때 33이 최대값이 됩니다. 

저희는 직전값 + 자기 자신의값과 자기 자신의값 중 최대값을 비교 했기 때문에 

DP[i]=max(DP[i-1]+arr[i],arr[i])라는 공식이 만들어지게 됩니다.

아래는 코드입니다.

https://www.acmicpc.net/problem/11053

이번 문제는 다이나믹 프로그래밍을 이용하여 푸는 문제입니다.

배열 A를 입력받은 수열이라고 하면

DP[i]는 A[1],A[2],....,A[i] 까지 수열이 있을 때 A[i]를 마지막으로 하는 가장 긴 증가하는 부분수열의 길이라고 둡니다.

우선 처음에는

10을 마지막으로 하는 가장 긴 증가하는 부분수열의 길이는 1입니다.

다음의 20은 왼쪽에 있는 수 중 자신보다 작으면서 DP[자신보다 작은 수의 위치] 가 자신의 DP[자신]의 값 보다 크면 그수에 1을 더합니다.

이것을 코드로 만들어 보면 이런식으로 나옵니다.

if(A[j]<A[i]&&DP[j]>=DP[i]){

    DP[i]=DP[j]+1;

}

다음에 나오는 10은 만족하는 조건이 없으니 자기 자신의 길이인 1이 됩니다.

30은 자기보다 왼쪽에 있으면서 작은 수인 20이 있고 20의 길이인 2보다 자신의 길이(1) 이 더 작기 때문에 20의 길이의 자신의 길이를 더한 3이 들어가게 됩니다.

이런식으로 채워나가면 다음과같은 표를 만들 수 있게됩니다.

아래는 코드입니다.

q#include<string>

using namespace std;

*문자열 -> 정수

 -stoi(string s) : string -> int

 -stol(string s) : string -> long

 -stoll(string s) : string -> long long

 -stof(string s) : string -> float

 -stod(string s) : string -> double

 -stold(string s) : string -> long double

 -stoul(string s) : string -> unsigned long

 -stoull(string s) : string -> unsigned long long

*정수 -> 문자열

 -to_string(int a) : int->string

이것 들을 활용한 BOJ 문제 10824번 네 수 문제입니다.

https://www.acmicpc.net/problem/10824

C++11 에서는 타입추론이 가능합니다.

auto 타입을 선언하게 되면 초기값의 형식에 맞춰 인스턴스(변수)의 형식이 자동으로 결정됩니다.

해당형식을 추론하도록 컴파일러에게 지시를 하는것이 됩니다.

위와 같은 경우에는 10.0이 double형식이므로 d변수는 double 타입이라 추론하게됩니다.

10은 integer이므로 i를 integer타입이라 추론하게됩니다.

이부분 처럼 함수 선언을 하여

auto answer = sum(5,6);

호출하게 되면 return값이 integer이기 때문에 answer의 타입은 integer로 추론하게 됩니다.

https://www.acmicpc.net/problem/10866

자료구조의 덱 문제입니다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.

• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

덱은 #include<deque> 후에 deque<int> dq로 선언한 후 dq.push_back(int x), dq.size() ...이렇게 사용합니다.

아래는 소스입니다.

https://www.acmicpc.net/problem/1158

이번 문제는 1158번 조세퍼스 문제입니다.

이 문제는 큐를 사용하면 쉽게 풀어낼 수 있는 문제입니다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다.

입력이 7 3 <--이렇게 들어왔다고 가정해보면

1 ~ 7까지를 모두 큐에 PUSH합니다. 그다음에 3번째 숫자만 삭제 해 나갑니다.

위 그림과 같이 2번을 POP해주고 뒤에 PUSH해서 넣어주면 3번째 숫자가 queue의 front에 오게 됩니다.

그렇다면 queue의 front를 출력해주고 pop해주면 한개가 삭제되는것입니다.

이런 과정을 queue가 empty가 될때까지 반복하면서 POP되는 숫자들을 출력해주면 됩니다.

아래는 전체 소스코드입니다!

https://www.acmicpc.net/problem/10845

• push X: 정수 X를 큐에 넣는 연산이다.

• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

• size: 큐에 들어있는 정수의 개수를 출력한다.

• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.

• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

간단하게 큐를 구현하는 코드입니다.

우선 push 3 그리고 push 4를 했을때의 큐의 모습입니다.

큐의 맨 앞부분이 front이고, 맨 뒷부분이 back입니다. 그리고 현재 size 는 2가됩니다.

pop을 하게되면 맨앞에 front에 있는 data가 빠져나가게 됩니다. 

이를 c++코드로 구현하는 것이 이번 10845번 큐 문제입니다.

https://www.acmicpc.net/problem/1406

이번에는 스택을 활용하여 푸는 1406번 에디터 문제입니다. C++기준으로 #include<stack>을 활용하여 풀어 보았습니다.

문제를 보시면 

L : 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)

D : 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)

B : 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)

P $ : $라는 문자를 커서 왼쪽에 추가함

총 4개의 명령어가 존재합니다.

스택을 활용하여 푸는 방법은 다음 그림과 같습니다.

자 우선 input으로 abcd를 받았을 때는 좌측에 abcd를 모두 push 해줍니다. 위에 있는 | 부분이 커서입니다.

L명령어를 받았을 때에는 커서를 왼쪽으로 한칸 이동시켜 주어야합니다. 그러면 그림과 같이 L스택의 top 을 R스택에 push 하고, L스택을 pop 해줍니다.

D명령어를 받았을 때에는 커서를 우측으로 한칸 이동시켜 주어야 합니다. 그러면 그림과 같이 R스택의 top을 L스택에 push해주고 R스택을 pop 해줍니다.

이번엔 P $ 명령어 입니다. $라는 문자를 커서 왼쪽에 추가하는 명령어 인데 L 스택에 $문자를 push해주면 간단하게 끝납니다.

마지막으로 B명령어는 커서 왼쪽에 있는 문자를 삭제 하는 명령어입니다. 이것도 간단하게 L스택을 pop해주면 됩니다.

* 출력을 할때에는 L에 있는 스택을 모두 R로 옮겨 주어야 하나씩 pop하면서 순서대로 출력이 됩니다!!

간단하게 그림으로 설명을 해보았습니다. 아래에는 소스코드입니다.