호로그래머

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이 들어가게 됩니다.

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

아래는 코드입니다.

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하면서 순서대로 출력이 됩니다!!

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

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

9012번 괄호는 괄호의 짝을 찾는 문제입니다.

문제를 읽어보시면 여는괄호가 있을때 닫는 괄호가 있다면 짝이 맞는것입니다.

문제를 접근할때는 여는 괄호가 나올 때 마치 스택에 넣듯이 생각하시면 됩니다.

위 그림과 같이 여는 괄호가 나올때 스택에 넣고 닫는 괄호가 나올때마다 하나씩 뺀다고 생각 하시면 됩니다.

그렇게 되면 Stack_size가 여는 괄호가 나올때는 1씩 증가하고, 닫는 괄호가 나올때 1씩 감소하게 됩니다.

그러므로 Stack_size가 0이면 모든 괄호가 짝이 있어서 "YES"를 출력하면 됩니다.

하지만 0이 아니거나 Stack_size가 한번이라도 음수가 된다면 짝이 없는 것이므로 "NO"를 출력하면 되겠습니다.

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

문제를 읽어보면  '(' 다음에 바로 ')' 이렇게 나오면 레이저가 됩니다 ==>()

그렇지 않고 그냥 '(' 만 있다면 파이프의 시작 부분이 되는것입니다. 

그리고 ')'는 파이프가 끝나는 부분이 됩니다. 

그러므로 파이프가 생성될 때 pipe_counter를 1씩 증가시켜주고 레이저가 나온다면 우선 pipe_count만큼 잘리게 됩니다.

파이프가 끝나게 되면 정답에 +1을 해주어 총 파이프 한개가 레이저에 의해 잘린 횟수가 정답에 더해지게 됩니다.