3/16 Coding Test - BOJ

✅ 문제 풀이 - 자료구조

🎈 4949 균형잡힌 세상

문자열에 포함되는 괄호는 (), []로 2종류로 문자열이 균형을 이루는 조건은 아래와 같다.

• (는 )와 짝을 이뤄야 한다
• [는 ]와 짝을 이뤄야 한다
• 모든 오른쪽 괄호들은 자신과 짝을 이루는 왼쪽 괄호가 존재하고, 모든 괄호는 1:1 매칭
• 짝을 이루는 두 괄호가 존재하면, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
  문자열이 각 줄마다 주어질 때 균형을 이루면 yes, 아니면 no를 출력하는 문제
• 입력값은 온점 하나만 입력 시 종료

import sys
input = sys.stdin.readline

while True:
    sentence = input().rstrip()
    stack = []
    flag = True
    if sentence == '.':
        break
    for i in sentence:
        if i =='(' or i =='[':
            stack.append(i)
        elif i == ')':
            if not stack or stack[-1] == '[':
                flag = False
                break
            elif stack[-1] == '(':
                stack.pop()
        elif i == ']':
            if not stack or stack[-1] == '(':
                flag = False
                break
            elif stack[-1] == '[':
                stack.pop()
    if flag == True and not stack:
        print('yes')
    else:
        print('no')

< 풀이 과정 >
스택으로 단순 구현해준 문제.
1. while문으로 sentence를 무한으로 입력받고 .이 들어오는 순간 종료
2. for문으로 각 sentence를 돌며 ( , [ 입력 시 스택에 넣어준다.
3. 만일 문자가 )인데 스택이 비어있거나 스택 내 제일 최근에 담은 문자가 [라면 flag는 False로 변경하고 break
4. 스택 내 제일 최근 문자가 ) 라면 pop해주기.
5. [도 같은 식으로 구현

🎈 1406 에디터

편집기는 소문자만 기록할 수 있고 최대 600,000글자까지 입력이 가능하다.
커서는 문장 맨 앞, 맨 뒤, 문장 중간 임의의 위치할 수 있다.
길이가 L인 문자열의 경우 커서가 놓일 수 있는 위치는 L+1가지의 경우가 있다.
명령어는 다음과 같다

• L : 커서를 왼쪽으로 한 칸 옮김 (현재 커서가 문장 맨앞이면 무시)
• D : 커서를 오른쪽으로 한 칸 옮김(현재 커서가 문장 맨뒤면 무시)
• B : 커서 왼쪽 문자 삭제 (현재 커서가 문장 맨 앞이면 무시)
• P $ : $라는 문자를 커서 왼쪽에 추가
  첫 줄에는 문자열이, 둘째 줄에는 명령어 개수 m, 이후 m줄에 걸쳐 명령어가 주어질 때 최종 문자열을 출력하는 문제. 최초 커서는 문장 맨뒤에 위치해있다.

import sys
input = sys.stdin.readline

left = list(input().rstrip())
right = []
m = int(input())
for i in range(m):
    command = input().split()
    if command[0] == 'P':
        left.append(command[1])
    elif command[0] == 'L' and left:
        right.append(left.pop())
    elif command[0] == 'D' and right:
        left.append(right.pop())
    elif command[0] == 'B' and left:
        left.pop()
print(''.join(left + list(reversed(right))))

< 풀이 과정 >
insert, remove를 사용한다면 O(N)이라는 시간 복잡도가 발생해 append, pop을 통해 해결을 해야하는 문제
커서를 기준으로 left, right로 나누어 두 리스트로 해결하였고 m줄 마다 입력되는 명령어에서 다음과 같이 수행한다.

• 첫 문자가 P이면 left 리스트에 $를 append
• 첫 문자가 L이고 left 리스트가 비어있지 않다면 right리스트에 left 젤 끝 글자 append
• 첫 문자가 D이고 right 리스트가 비어있지 않다면 left리스트에 right 젤 끝 글자 append
• 첫 문자가 B이고 left 리스트가 비어있지 않다면 left리스트의 제일 끝 글자 삭제
  최종적으로 left와 right를 뒤집은 리스트를 더해 출력하는 문제

✅ 문제 풀이 - DP

🎈 11048 이동하기

NXM크기의 미로에 갇혀있을 때 이동하는 경우의 수는 우측, 아래, 왼쪽 아래 대각선으로 총 3가지이다. 미로를 이동하며 가져올 수 있는 사탕의 최대값을 구하는 문제

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = graph[i-1][j-1] + max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
print(dp[n][m])

< 풀이 과정 >
dp를 이용하여 구현한 문제
이동가능한 경우의 수가 우측, 아래, 왼쪽 아래 대각선으로 총 3가지 경우의 수만 생각해주면 된다.
따라서 dp를 (n+1)X(m+1) 크기의 값은 0인 2차원 리스트로 만들어 준 후, dp내부 값은 그래프의 오른쪽 위 대각선에 dp상 위쪽, 왼쪽, 오른쪽 위 대각선 3가지 중 가장 큰 값을 더해주고 최종적으로 계산된 dp[n][m]을 출력하는 문제

🎈 2133 타일 채우기

n이 주어질 때 3Xn 크기의 벽을 2x1, 1x2 타일로 채울 수 있는 경우의 수를 구하는 문제

import sys
input = sys.stdin.readline
n = int(input())
dp = [0] * 31
if n % 2 == 1:
    print(0)
else:
    dp[2] = 3
    for i in range(4, 31, 2):
        dp[i] = dp[i-2]*3 + 2
        for j in range(2, i-2, 2):
            dp[i] += dp[j]*2
    print(dp[n])

< 풀이 과정 >
직접 구현해보면서 상당히 까다롭다고 느낀 문제.
패턴을 발견해보면 n이 홀수인 경우 만들 수 있는 경우의 수는 없다
그렇다면 n이 짝수인 경우의 문제인데 다음과 같다.

• n이 2인 경우 만들 수 있는 case는 3가지
• n이 2씩 증가할 때마다 이전 dp값 3가지를 곱해주고 3X4 모양으로 새롭게 만들어지는 경우 2가지를 더해 dp[n] = dp[n-2] 3 + 2로 계산 가능
• 끝 점으로부터 4칸 이상 남은 경우 3x4의 모양만 추가가 가능하므로 dp[n] += dp[i-2] * 2

🎈 2225 합분해

n, k를 입력받아 0~n개의 정수 k개를 가지고 n을 만드는 경우의 수를 구하는 문제

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [[0]*201 for _ in range(201)]

for i in range(201):
    dp[1][i] = 1
    dp[2][i] = i+1
for i in range(2, 201):
    dp[i][1] = i
    for j in range(2, 201):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1e9
print(int(dp[k][n]))

< 풀이 과정 >
kXn 크기를 가진 2차원 리스트로 dp를 구현하여 풀이 진행

• k가 1이라면, 결국 n을 만드는 경우의 수는 n 자신 1가지 뿐이다

• k가 2라면, 0~n까지의 개수를 의미하므로 n+1 가지

• for문으로 k를 돌려 2번째 행을 k자신으로 만들어주고, for문으로 n번 반복하며 dp를 채워주는데 방식은 다음과 같다. dp[i][j] = 이전 행 값 + 이전 열 값 으로 계산을 반복해주고 최종적으로 10^9으로 나눈 나머지를 출력하길 요구하였기에 이를 반영하여 출력한다.

🎈 2565 전깃줄

전깃줄 개수 n이 주어지고, 두 전봇대 번호를 통해 이어지는 전선이 n줄에 걸쳐 주어질 때, 전선이 서로 교차되지 않길 원하므로, 교차되는 전선을 자르는 최소 개수를 출력하는 문제

import sys
input = sys.stdin.readline

n = int(input())
wire = sorted(list(map(int, input().split())) for _ in range(n))
dp = [1] * n
for i in range(1, n):
    for j in range(i):
        if wire[j][1] < wire[i][1]:
            dp[i] = max(dp[i], dp[j] + 1)
print(n - max(dp))

< 풀이 과정 >
주어진 전깃줄 a,b 입력값을 wire 리스트에 저장한 후, sorted를 진행하면 A전봇대를 기준으로 오름차순 정렬된다. 교차하는 여부를 판단하려면, B전봇대를 보면 되는데, B전봇대 기준 앞 숫자가 뒷 숫자보다 크다면 교차하는 것을 의미한다.
따라서 교차하지 않도록 하기 위해서 교차되는 B전봇대의 숫자를 뽑아내야 하는데 이는 전체 전선에서 B전봇대 기준 오름차순 결과인 전봇대 번호 개수를 빼주면 되는 문제.

코드를 디테일하게 살펴보면 다음과 같다.

• 입력받은 a, b를 wire 리스트에 추가한 후 A전봇대 기준 sorting
• dp는 전선 개수를 의미하므로 각 전봇대 번호 별 1개씩 저장
• B전봇대 기준 앞 숫자보다 뒷 숫자가 더 크다면, dp[j] + 1과 dp[i] 중 큰 값을 dp[i]로 갱신하며 오름차순 된 전선 개수를 max(dp)로 뽑아 낸다.