슥지니의 코딩노트

문제 링크:https://www.acmicpc.net/problem/4949

<문제 풀이>

문자열에서 괄호를 제외한 다른 문자들은 무시하고 괄호만 확인해서 괄호들이 짝이 맞는지만 확인하면 됩니다.

[괄호 쌍 체크]

문자를 하나씩 확인해서

1. 여는 괄호 일 때 괄호를 스택에 push

2. 닫는 괄호 일때 스택의 top이 가리키는 괄호와 같으면 pop, 다르면 짝이 안 맞으므로 False

순회를 마쳤을 때 스택이 비어있으면 True, 비어있지 않으면 False

<C++ 소스 코드>

문제 링크: https://www.acmicpc.net/problem/5430

문제 풀이

[주의 1]

R 연산을 할 때마다 reverse 함수를 사용하면 시간 초과가 납니다.

왜냐하면

reverse 함수가 O(N)의 시간복잡도가 걸리니깐

전체 O(n * len(p))의 시간복잡도가 걸립니다.

p의 길이가 0 <= len(p) <= 100,000,

n의 범위가 0 <= n <= 100,000 이므로

만약에 p가 전부 R로 이루어져 있고, n = 100,000 이면

O(10^5 * 10^5) = O(10^10)이 되니깐 시간제한 1초 안에 해결할 수 없습니다.

[주의 2]

빈 배열에서 R연산을 해도 error가 아니다

reverse 함수를 사용하지 않고 R연산을 구현하는 방법은

deque를 사용하면 됩니다.

D연산을 배열의 앞과 뒤에서 할 수 있는데

처음엔 앞에서 시작해서 R연산을 할 때마다 앞, 뒤를 바꿔주면 됩니다.

<c++ 소스 코드> deque 덱, 자료구조

문제 링크: https://www.acmicpc.net/problem/2164

문제 풀이

숫자 카드를 위 그림과 같이 큐에 넣고

큐의 크기가 1이 될 때까지 다음을 반복하면 됩니다.

first 원소를 pop
그 다음 first원소를 push + pop

<c++ 소스 코드> 큐, 자료구조

문제 링크: https://www.acmicpc.net/problem/6198

[문제 풀이] 스택, 자료구조

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

먼저 크기가 N인 배열을 준비합니다.

arr[i]는 i번째 빌딩을 바라보는 관리자들의 수가 됩니다.

->arr[1] == 0 (어떤 빌딩도 바라볼 수 없음)

   arr[2] == 1 (1번 빌딩이 바라보고 있음)

   arr[3] == 1 (1번 빌딩이 바라보고 있음)

   arr[4] == 2 (1번, 3번 빌딩이 바라보고 있음)

   arr[5] == 0 (어떤 빌딩도 바라볼 수 없음)
   arr[6] == 1 (5번 빌딩이 바라보고 있음)

그리고 빌딩을 저장할 수 있는 스택을 하나 준비합니다

이때 스택엔 i번째 빌딩을 볼 수 있는 빌딩을 저장합니다. 

-> 1번 빌딩 stack = {0}

    2번 빌딩 stack = {0, 1}

    3번 빌딩 stack = {0, 1}    

    4번 빌딩 stack = {0, 1, 3}

    5번 빌딩 stack = {0}

    6번 빌딩 stack = {0, 5}

스택의 size -1은 i번째 빌딩을 바라볼 수 있는 관리자의 수가 됩니다.

1 ~ N 빌딩을 순회하면서

i 번째 i +1 번째 빌딩을 체크해서

if(i + 1 번째 i번쨰 빌딩보다 작으면)

->i번째 빌딩이 i+1번째 빌딩을 볼 수 있으니깐 i번쨰 빌딩을 스택에 추가합니다.

else if(i +1번째 빌딩이 i번쨰 빌딩보다 크거나 같으면)

->i+1번째 빌딩을 볼 수 없는 관리자들을 스택에서 제거합니다.

  ex) 5번 빌딩일 때 1번, 3번을 제거함)

<c++ 소스 코드> 

문제 링크: https://www.acmicpc.net/problem/2493

문제 풀이

첫 번째 탑에서 시작해서 탑을 두 개씩(i, i+1) 이용하면 스택으로 문제를 해결할 수 있습니다. 

스택을 하나 준비해서 탑의 번호를 저장합니다

이때 스택의 top()은 i번쨰 탑이 레이저를 발사했을 때 수신받을 수 있는 가장 가까운 탑입니다.

수신받을 수 있는 탑이 없는 경우는 높이가 0인 0번째 탑이 존재한다고 생각하고 0번째 탑이 수신하도록 하면 됩니다.

이제 i번째와 i+1번째 탑 두 개를 이용해서 다음과 같은 알고리즘을 만들 수 있습니다.

1. 만약 i+1번째 탑이 i번째 탑보다 크다면

-> 스택의 top()이 i+1번쨰 탑보다 클 때까지 스택을 pop()합니다

  ->스택의 top()이 i+1 번째 탑보다 작으면 top()이 i+1번째 탑의 레이저를 수신하지 못합니다.

  (단 스택의 top() > 0 이상일 때입니다. 왜냐하면 아무것도 수신받는 레이저가 없을 땐 0번째 탑이 수신하도록 했습니다.

2. 그렇지 않으면 만약 i+1번째 탑이 i번째 탑보다 작으면

-> i번째 탑을 스택에 push()합니다.

  -> i번쨰 탑이 i+1번째의 탑의 레이저를 수신하게 만듭니다.

3. 그렇지 않으면 만약 i+1번째 탑이 i번쨰 탑보다 작으면

-> 스택을 pop()하고 i번쨰 탑을 스택에 push()합니다.

  -> i+1번째 레이저를 가장 가까운 탑이 수신하도록 합니다.

문제의 입력을 예로 설명하면

i = 1일 때

0번째 탑이 1번째 탑의 레이저를 수신합니다.

i = 2일 때

1번째 탑이 2번째 탑의 레이저를 수신하고 2번째 탑을 스택에 push()합니다.

i = 3일 때

2번째 탑이 3번째 탑의 레이저를 수신합니다.

i = 4일 때

2번째 탑이 4번째 탑의 레이저를 수신하고 4번째 탑을 스택에 push()합니다.

i = n일 때

4번째 탑이 5번째 탑의 레이저를 수신합니다.

<C++ 소스 코드> 스택, 자료구조

문제 링크:https://www.acmicpc.net/problem/3273

<문제 풀이>

시간제한이 1초이고 N < 10^6 이므로 O(N^2) 풀이는 시간 초과입니다.

수열을 하나씩 꺼내보면서, 꺼낸 수와 합이 X가 되도록 하는 수열 내의 다른 어떤 수가 존재하는지 확인할 수 있으면 O(N)의 시간 복잡도로 문제를 해결할 수 있습니다.

수열에서 하나씩 꺼내서 X에서 뺀 뒤 그 수가 수열 내에 존재하는지 확인하면 됩니다.

-> a1 + a2 = X

    a2 = X - a1

문제 입력을 예로 들면

9

5 12 7 10 9 1 2 3 11

13

1) 5 -> 13(X) - 5 = 8 

2) 12 -> 13(X) - 12 = 1

3) 7 -> 13(X) - 7 = 6 

4) 10 -> 13(X) - 10 = 3

5) 9 -> 13(X) - 9  = 4

6) 1 -> 13(X) - 1  = 12

7) 2 -> 13(X) - 2  = 11

8) 3 -> 13(X) - 3  = 10

9) 11 -> 13(X) - 11  = 2

꺼낸 수가 등장한 수인지를 체크하는 배열을 만들고 입력받은 데이터를 순회하면서 

1. X - data가 이전에 등장했다면 카운트. 9) 11 -> 13(X) - 11 = 2  : 2는 7)에서 등장한 수로 체크함

2. 꺼낸 수는 등장한 수 배열에 체크해줍니다.  

X - data가 음수가 나올 수도 있음(배열 런타임 에러)

<C++ 소스 코드>

문제 링크:https://www.acmicpc.net/problem/10871

<문제 풀이>

입력받은 수를 X보다 작으면 출력하면 되는 문제입니다.

<C++ 소스 코드> 수학, 구현

문제 링크: www.acmicpc.net/problem/1197

<문제 풀이>

Union-Find 알고리즘을 이용해서 기본적인 크루스칼 알고리즘을 구현하면 되는 문제입니다.

<C++ 소스 코드> 최소 스패닝 트리, 크루스칼 알고리즘