방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 dp를 이용하면 쉽게 해결할 수 있는 문제였습니다. 이동할 수 있는 경우는 오른쪽, 아래 2가지 경우만 존재하므로 원본 배열과 같은 크기의 visited 배열을 만듭니다. 이후의 과정은 다음과 같습니다.

1. visited 배열을 조회함(0행 0열부터 n-1행 n-1열 까지)

2. 해당 칸이 직전 과정에서 이동한 칸이면(visited[i][j] != 0 이면) 위 또는 아래로 원본 배열에 해당하는 칸만큼 움직이기 단, 원본 배열의 해당 칸은 0이 아님

이 과정을 반복하면서 마지막에 도착했을 때 출력하면 됩니다.

소스코드

n = int(input())
dx = [0, 1]
dy = [1, 0]

graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))
visited = [[0] * n for _ in range(n)]
visited[0][0] = 1

for i in range(n):
  for j in range(n):
    if graph[i][j] != 0 and visited[i] != 0:
      for k in range(2):
        nx = i + dx[k]*graph[i][j]
        ny = j + dy[k]*graph[i][j]
        if nx < 0 or ny < 0 or nx >= n or ny >= n:
          continue
        visited[nx][ny] += visited[i][j]
print(visited[n-1][n-1])

https://school.programmers.co.kr/learn/courses/30/lessons/42842

문제 해결을 위한 과정

이 문제의 경우 수학적 지식을 이용하면 해결할 수 있는 문제였습니다.

저 같은 경우는 for문을 돌리면서 yellow의 가로길이는 brown-2라는 것을 이용해 해결할 수 있었습니다. 이를 소스코드로 작성하면 다음과 같습니다. 또한 가로, 세로의 순서를 맞추기 위해 가로에 더 큰 값을 집어넣어야 합니다. 이를 위해 answer.clear()를 넣어주어 혹시 모를 가로, 세로 길이의 역전을 방지하였습니다.

소스코드

def solution(brown, yellow):
    answer = []
    n = brown // 2
    for i in range(3, n):
        temp = yellow % (i-2)
        if temp == 0:
            temp2 = yellow // (i-2)
            if i + i + temp2 + temp2 == brown:
                answer.clear()
                answer.append(i)
                answer.append(temp2 + 2)
        
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제 해결을 위한 과정

이 문제의 경우 permutaions를 이용하면 해결할 수 있는 문제였습니다. 순서가 중요하므로 조합이 아닌 순열이라는 점이 중요합니다.

결국 각각의 수로 만들 수 있는 순열을 생성한 뒤 해당 숫자가 소수인지를 판별하면 됩니다. 중복이 허용되지 않으므로 set자료형에 삽입하여 중복을 제거하였습니다. 

소수 판별의 경우 isPrime이라는 메소드를 생성하여 해결하였습니다. 소스코드로 작성하면 다음과 같습니다.

소스코드

from itertools import permutations
import math

def isPrime(num):
    if num <= 1:
        return False
    
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    tempAnswer = set()
    temp = []
    for i in range(len(numbers)):
        temp.append(numbers[i])
        
    for i in range(1, len(temp) + 1):
        for p in permutations(temp, i):
            tmp = ""
            for j in range(len(p)):
                tmp += p[j]
            if isPrime(int(tmp)):
                tempAnswer.add(int(tmp))
    answer = len(tempAnswer)
    return answer

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

문제 해결을 위한 과정

이 문제의 경우 dp를 이용한 냅색 알고리즘입니다. 입력받은 물품들을 정렬하지 않는 이유는 dp는 순서에 의존하지 않는 최적화 문제이기 때문입니다. 따라서 순서를 고려하지 않기 위해 정렬을 하지 않는 것입니다. 표를 그리면 다음과 같습니다. 

행은 탐색한 배낭의 번호를, 열은 가져갈 수 있는 무게를 나타냅니다. 이렇게 하게 되면 다음과 같은 점화식을 얻을 수 있습니다.

if 현재 열의 무게 < 현재 탐색한 배낭의 무게 :

    graph[i][j] = graph [i-1][j]

else:

    graph [i][j] = max(graph [i-1][j], value + graph[i-1][j-weight])

이를 소스코드로 작성하면 다음과 같습니다.

소스코드

n, k = map(int, input().split())
graph = [[0] * (k+1) for _ in range(n+1)]
obj = []
for _ in range(n):
  a, b = map(int, input().split())
  obj.append((a, b))

for i in range(1, n + 1):
  for j in range(1, k + 1):
    weight = obj[i-1][0]
    value = obj[i-1][1]
    if j < weight:
      graph[i][j] = graph[i-1][j]
    else:
      graph[i][j] = max(graph[i-1][j], value + graph[i-1][j-weight])
print(graph[n][k])

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

문제 해결을 위한 과정

이 문제의 경우 dp를 이용하면 쉽게 해결할 수 있었습니다. 문제에서 볼 수 있듯 어떤 칸에 대해서 위, 왼쪽, 좌측대각선 위(11시 방향) 중 최댓값을 현재 칸에 더해주고, 이 결과로 나온 배열에서 제일 우측 하단 배열의 값을 출력해 주면 됩니다. 다만 0번째 행, 0번째 열 처럼 위, 왼쪽, 좌측 대각선 중 한 경우라도 없는 경우는 따로 예외처리를 하여 해결하면 됩니다. 

소스코드

n, m = map(int, input().split())
graph = []
for _ in range(n):
  graph.append(list(map(int, input().split())))

for i in range(n):
  for j in range(m):
    if i == 0:
      if j != 0:
        graph[i][j] += graph[i][j-1]
    else:
      if j == 0:
        graph[i][j] += graph[i-1][j]
      else:
        graph[i][j] += max(graph[i-1][j], graph[i][j-1], graph[i-1][j-1])

print(graph[n-1][m-1])

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

문제 해결을 위한 과정

이 문제의 경우 dp로 해결할 수 있는 문제였습니다. n=3인 경우 32가지, n=4인 경우 61가지가 존재함을 알고,

9 -> 17 -> 32 -> 61로 규칙을 찾으려 했으나 실패했습니다.

다음과 같이 표를 그리면 규칙을 찾을 수 있었습니다.

 가로는 끝나는 수(0~9), 세로는 n(n>=1)입니다. 예를 들어서 빨간색으로 표시된 3의 경우 3자리 수 중 끝이 1로 끝나는 숫자를 말합니다.

101, 121, 321 총 3가지가 존재함을 알 수 있습니다.

표를 보면 규칙을 알 수 있는데 i, j(각각 행, 열 의미) j가 0이면 i-1행의 j+1을 가져오고, j가 9이면 i-1행의 j-1을 가져오고 그 외의 경우는 직전행의 좌측, 우측 열의 값을 합한 것을 가져옵니다. 이를 소스코드로 작성하면 다음과 같습니다.

소스코드

n = int(input())

dp = [[0] * 10 for _ in range(n)]
for j in range(1, 10):
  dp[0][j] = 1
for i in range(1, n):
  for j in range(10):
    if j == 0:
      dp[i][j] = dp[i-1][j+1]
    elif j == 9:
      dp[i][j] = dp[i-1][j-1]
    else:
      dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

ans = 0
for j in range(10):
  ans += dp[n-1][j]
print(ans % 1000000000)

https://school.programmers.co.kr/learn/courses/30/lessons/42587

문제 해결을 위한 과정

이 문제는 deque를 이용하면 쉽게 해결할 수 있는 문제였습니다. 과정은 다음과 같습니다.

1. priorities 배열을 조회하며 인덱스를 포함한 pair형태로 deque에 넣어준다.

2. 그 후 반복문으로 조회를 하면서 맨 앞에 원소와 인덱스 값을 꺼낸 뒤 다시 한번 for문으로 조회를 하며 deque내부에 더 높은 우선순위가 있는지 찾는다.

3. 더 높은 우선순위가 있다면 append로 뒤에 넣어준다.

4. 더 높은 우선순위가 없다면 처리한다.

4-1. 단 이때 처리된 인덱스가 location과 일치하는지 확인한다.

소스코드

from collections import deque

def solution(priorities, location):
    answer = 0
    q = deque()
    for i in range(len(priorities)):
        q.append((priorities[i], i))
    ans = 0
    
    while len(q) != 0:
        now, idx = q.popleft()
        flag = True
        for i in range(len(q)):
            next, nIdx = q[i]
            if next > now:
                q.append((now, idx))
                flag = False
                break
        if flag == True:
            ans += 1
            if idx == location:
                answer = ans
                break
            
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42628

문제 해결을 위한 과정

이 문제는 heapq를 2개 만들어서 해결하면 쉽게 해결할 수 있는 문제였습니다.

파이썬의 경우 최소 힙 방식이므로 heapq에서 pop 하면 최솟값이 나온다는 것을 염두에 두면 다른 힙에는 원래 수에 -1을 곱한 값을 넣어서 최댓값을 꺼낼 수 있다는 것을 알 수 있습니다. 그림으로 표현하면 다음과 같습니다.

힙을 2개 만들어서 첫번째 힙에는 원래대로 숫자를 삽입, 두 번째 힙에는 -1을 곱한 수를 넣었습니다. 이렇게 하면 첫 번째 힙에서 pop 하면 최솟값을, 두 번째 힙에서는 pop한뒤 -1을 곱하면 최댓값을 pop 할 수 있게 됩니다.

소스코드

import heapq

def solution(operations):
    answer = []
    maxQ = []
    minQ = []
    for i in range(len(operations)):
        cmd, num = operations[i].split()
        num = int(num)
        if cmd == "I":
            heapq.heappush(maxQ, (num))
            heapq.heappush(minQ, (num*-1))
        elif cmd == "D":
            if num == -1 and len(maxQ) != 0:
                delNum = heapq.heappop(maxQ)
                for i in range(len(minQ)):
                    if minQ[i] == delNum*-1:
                        minQ.pop(i)
                        break
            elif num == 1 and len(maxQ) != 0:
                delNum = heapq.heappop(minQ)
                for i in range(len(maxQ)):
                    if maxQ[i] == delNum*-1:
                        maxQ.pop(i)
                        break
    if len(maxQ) == 0 and len(minQ) == 0:
        answer.append(0)
        answer.append(0)
    else:
        answer.append(heapq.heappop(minQ)*-1)
        answer.append(heapq.heappop(maxQ))
    return answer