새싹프로그래머의 이야기

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

문제: 정수 N이 주어졌을 때, N자리 이친수의 갯수를 구하는 문제

풀이 방법: DP

풀이 코드:

n = int(input())

dp = [0] * (n+1)

dp[1] = 1

if n > 1:
    dp[2] = 1
    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

풀이 설명:

이 문제는 규칙성이 눈에 보여서 점화식으로 간단하게 해결 할 수 있었습니다.

먼저 조건은 다음과 같습니다.

1. 첫번째 자리는 무조건 1 이어야 한다.

2. 1이 연속되게 나올 수 없다.

즉, N = 1일 때는 1만 가능하며 N = 2일 때 또한 10만 가능하다는 것입니다.

N = 3 이라면, 3번째 자리 수에는 0 또는 1이 올 수 있으므로 경우의 수는 2가지 입니다.

N = 4 라면, 3번째 자리 수가 0일 경우 4번째 자리 수에 0 또는 1이 올 수 있으며 세번째 자리 수가 1일 경우 0만 올 수 있습니다.

이를 도식화 하면 다음과 같습니다.

N = 3일 때는 0 , 1  두가지 경우의 수가 있습니다.

N = 4일 때는 N = 3 일 때 기준으로 0 - 0 , 0 - 1, 1 - 0 으로 이어지는 3가지 경우의 수가 있죠.

N= 5일 때는 그림과 같이 5가지 경우의 수, N =6일 때는 8가지 경우의 수가 생깁니다.

즉, 여기서 하나의 점화식을 구할 수 있었죠.

F(x) = F(x-1) + F(x-2) (x >= 3) 입니다.

따라서, 다음 점화식을 통해 문제를 간단하게 해결 할 수 있었습니다.

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

문제: 2xn 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수를 구하는 문제

풀이 방법: DP

풀이 코드:

n = int(input())
dp = [0] * (n+1)

dp[1] = 1

if n > 1:
    for i in range(2,n+1):
        if i % 2:
            dp[i] = dp[i-1] * 2 - 1
        else:
            dp[i] = dp[i-1]*2 + 1

print(dp[n] % 10007)

풀이 설명: 

문제를 보고 n 값에 따른 규칙성을 찾아보고자 하였습니다.

다음과 같이 2x1 , 2x2 , 2x3 짜리 직사각형이 있다고 할 때, 경우의 수는 다음과 같습니다.

2x1일 경우,  2x1 직사각형 1개로만 채울 수 있습니다.

2x2인 경우, 2x1 짜리 2개로 구성하는 방법, 1x2짜리 2개로 구성하는 방법, 2x2 짜리 1개로 구성하는 방법으로 총 3가지가 있습니다.

2x3 짜리는 어떨까요?

2x1 짜리 3개로 구성하는 방법, 2x1짜리 1 개와 2x2짜리 1개  또는 2x1짜리 1개와 2x1짜리 2개 로 구성하는 방법으로 총 5가지가 있습니다.

2x4짜리는 위와 같은 방법으로 총 11개의 방법이 있는데요.

n = 1 일 때부터 4일 때 까지 경우의 수를 보니 다음과 같은 규칙성을 발견할 수 있었습니다.

n이 홀수일 경우, n-1번째 경우의 수 * 2 - 1

n이 짝수일 경우, n-1번째 경우의 수 * 2 + 1 이라는 규칙을 구할 수 있었습니다.

따라서, 다음과 같이 코드를 구성해 n번째 경우의 수를 구하였습니다.

if n > 1:
    for i in range(2,n+1):
        if i % 2:
            dp[i] = dp[i-1] * 2 - 1
        else:
            dp[i] = dp[i-1]*2 + 1

또한, 10007로 나눈 나머지를 출력하라 하였으므로 다음 코드를 통해 구한 경우의 수를 10007로 나눈 나머지를 출력하도록 하였습니다.

print(dp[n] % 10007)

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

문제: 포도주 잔이 일렬로 놓여 있을 때, 3잔 연속으로 마시지 않는 경우 중 제일 많이먹는 경우를 구하는 문제

풀이 방법: DP

풀이 코드:

import sys

n = int(sys.stdin.readline())
arr = [0]*(n+1)
dp = [0] *(n+1)
for i in range(1,n+1):
    arr[i] = int(sys.stdin.readline())

if n == 1:
    print(arr[1])

else:
    dp[1] = arr[1]
    dp[2] = arr[1] + arr[2]

    for i in range(3,n+1):
        dp[i] = max(dp[i-1],dp[i-3]+arr[i-1]+arr[i],dp[i-2] + arr[i])

    print(max(dp))

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

문제: 동생이 위치한 K에 도달할 수 있는 최단 기간을 출력하는 문제

풀이 방법: 다잌스트라

풀이 코드:

import sys
import heapq

MAX = 100001
n,k = map(int,sys.stdin.readline().rstrip().split())


distance = [1e9] * MAX
visited = [False] * MAX
distance[n] = 0

q = [[0,n]]

def dijkstra():
    while q:
        nowCost, nowNode = heapq.heappop(q)
        visited[nowNode] = True

        if nowNode == k:
            break

        move = [[nowCost, nowNode*2], [nowCost + 1, nowNode - 1], [nowCost+1, nowNode+1]]

        for i in range(3):

            if move[i][1] >= MAX or move[i][1] < 0 or visited[move[i][1]]:
                continue

            if distance[move[i][1]] > move[i][0]:
                distance[move[i][1]] = move[i][0]
                heapq.heappush(q,move[i])


dijkstra()
print(distance[k])

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

문제: 오른쪽에서 큰 수중 제일 왼쪽에 있는 수를 구하는 문제

풀이 방법: 스택

풀이 코드:

import sys
from collections import deque

n = int(input())
array = list(map(int, sys.stdin.readline().rstrip().split()))
stack = deque()
ans = [-1]*n

for i in range(n-1,-1,-1):
    while stack:
        if stack[-1] > array[i]:
            ans[i] = stack[-1]
            stack.append(array[i])
            break
        else:
            stack.pop()

    stack.append(array[i])

print(' '.join(map(str,ans)))

풀이 설명:

풀이에서 핵심으로 잡은 점은 두가지 입니다.

1. 스택의 활용

2. 오른쪽에서 큰 수 중 제일 가까운 수를 구하는 문제이므로, 오른쪽부터 탐색

핵심이 되는 코드를 보면 다음과 같습니다.

for i in range(n-1,-1,-1):
    while stack:
        if stack[-1] > array[i]:
            ans[i] = stack[-1]
            stack.append(array[i])
            break
        else:
            stack.pop()

    stack.append(array[i])

오른쪽부터 탐색을 하면서, 스택에 큰 값을 담습니다.

이때, 스택에 담긴  A라는 값보다 더 큰 B라는 값을 만나게 되면 B 왼쪽의 수들에게는 더 이상 A가 의미가 없어지므로 pop 하도록 하였습니다.

if stack[-1] > array[i]:
    ans[i] = stack[-1]
    stack.append(array[i])
    break

스택의 마지막 값이 더 크다면, 현재 배열의 값의 오큰수는 스택에 담긴 값 입니다.  

따라서, 정답 값을 저장하는 ans에 저장해줍니다.

또한, 현재 배열의 값이 오큰수 일 수 있으므로 스택에 담아줍니다.

else:
    stack.pop()

만약, 현재 배열의 값이 스택의 마지막 값보다 크다면 pop을 해줍니다.

이유는 배열의 값이 더 크기 때문에 앞으로 스택의 마지막 값이 오큰수가 될 가능성이 없기 때문입니다.

마지막으로, ans를 -1로 초기화 해주었기 때문에, 스택에 담겨있는 값들보다 큰 값의 경우 현재 값의 위치의 ans에는 -1이 담겨있게 됩니다.

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

문제: 탑의 갯수와 높이가 주어졌을 때, 각 탑에서 쏘는 레이저를 수신할 수 있는 탑의 번호를 구하는 문제

풀이 방법: 스택

풀이 코드:

import sys
from collections import deque

n = int(input())
array = list(map(int, sys.stdin.readline().rstrip().split()))
stack = deque()
ans = [0]*n

for i in range(n):
    while stack:
        if stack[-1][0] >= array[i]:
            ans[i] = stack[-1][1]+1
            stack.append([array[i],i])
            break
        else:
            stack.pop()

    stack.append([array[i],i])
    
print(' '.join(map(str,ans)))

풀이 설명:

문제 풀이에 활용한 것은 두가지 입니다.

1. 탑에 대한 정보를 스택에 담는다.

2. A라는 탑 뒤에 A보다 높은 B라는 탑이 있을 경우, B 이후에 있는 탑의 레이저는 받지 못한다. 따라서, 스택에서 pop 한다.

풀이에 핵심이 되는 코드를 보겠습니다.

for i in range(n):
    while stack:
        if stack[-1][0] >= array[i]:
            ans[i] = stack[-1][1]+1
            stack.append([array[i],i])
            break
        else:
            stack.pop()

    stack.append([array[i],i])

먼저 stack에는 [높이, index]를 담습니다.

빈 스택이 아닐 경우, while 문이 돌아가게 됩니다.

조건 1) 앞선 탑에 높이가 현재 보다 높은 A라는 탑이 있다면 그 타워에 레이저가 닿을 것이므로, A 타워의 index를 저장해줍니다.

그리고 A 타워 뒤에 A보다 낮은 타워가 있을 수 있으므로 A 타워의 높이와 index를 스택에 저장해줍니다.

반대로, 뒤에 나온  B라는 탑보다 스택에 있는 A라는 탑이 더 낮다면  A에 닿을 레이저는 모두 B라는 탑에 닿아 더이상 필요가 없으므로 pop 하게 됩니다.

문제에 주어진 예시로 설명을 해보자면 다음과 같습니다. (6 9 5 7 4)

처음 6은 그대로 스택에 저장되게 됩니다.

stack = [[6,0]]

ans = [ 0, 0, 0, 0, 0]

그 다음 9를 만나게 되면, 반복문을 돌게 됩니다.

따라서 스택에 있는 6은 그대로 pop되고 9가 들어가게 됩니다.

stack = [[9,1]]

ans = [ 0, 0, 0, 0, 0]

5를 만나게 되면, 반복문을 도는데 이번에는 9 가 5보다 크므로 5 또한 스택에 담기게 됩니다. 그리고 9에 레이저가 닿으므로 9의 index를 저장하게 됩니다.

stack = [[9,1] , [ 5, 2 ]]

ans = [ 0, 0, 2, 0, 0]

7을 만나게 되면, 반복문에서 5보다 7이 더 크므로 5는 pop 되게 되고 다시 5와 같이 스택에 담기게 됩니다. 물론 레이저는 9에 닿으므로 9의 index를 저장하게 됩니다.

stack = [[9,1] , [7,3]]

ans = [ 0, 0, 2, 2, 0]

마지막으로 4를 만나게 되면, 4는 9로 가지 않아도 7에 닿습니다. 따라서, 7의 index를 저장하게 됩니다.

stack = [[9,1] , [7,3] , [4,4]]

ans = [ 0, 0, 2, 2, 4]

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

문제: 주어진 문자들을 바탕으로 만들 수 있는 조건에 부합하는 문자열을 출력하는 문제

풀이 방법: 백트래킹

풀이 코드:

import sys

l, c = map(int,sys.stdin.readline().rstrip().split(' '))

if not (3 <= l <= c <= 15):
    sys.exit(0)

vowel = ['a','e','i','o','u']

stringList = sorted(list(sys.stdin.readline().rstrip().split(' ')))
case = []
vowel_cnt = 0

def backTracking(idx):
    global vowel_cnt
    if len(case) == l:
        if vowel_cnt < 1 or len(case)-vowel_cnt < 2:    # 모음 갯수가 1보다 작거나 자음 갯수가 2보다 작으면 출력하지 않고 return
            return
        for i in range(l):  # 문자열 출력
            print(case[i], end='')
        print()
        return

    for i in range(idx,c):
        if len(case) > 0 and case[-1] >= stringList[i]:  # 영문이 역순으로 들어가지 않도록 처리
            continue
        if stringList[i] in vowel:  # 모음 갯수 count
            vowel_cnt += 1

        case.append(stringList[i])
        backTracking(idx+1)
        pop_char = case.pop()

        if pop_char in vowel:   # 모음이 빠질 경우 모음 갯수에서 1 빼줌
            vowel_cnt -= 1

backTracking(0)

풀이 설명:

문제에서 주어진 조건은 다음과 같습니다.

1) 문자열은 오름차순으로 구성되어야 한다.

2) 최소 1개의 모음과 2개의 자음을 포함하고 있어야 한다.

즉, 문제의 핵심은 백트래킹 기법과 주어진 조건을 어떻게 만족시키느냐 입니다.

vowel = ['a','e','i','o','u']

def backTracking(idx):
    global vowel_cnt
    if len(case) == l:
        if vowel_cnt < 1 or len(case)-vowel_cnt < 2:    # 모음 갯수가 1보다 작거나 자음 갯수가 2보다 작으면 출력하지 않고 return
            return
        for i in range(l):  # 문자열 출력
            print(case[i], end='')
        print()
        return

    for i in range(idx,c):
        if len(case) > 0 and case[-1] >= stringList[i]:  # 영문이 역순으로 들어가지 않도록 처리
            continue
        if stringList[i] in vowel:  # 모음 갯수 count
            vowel_cnt += 1

        case.append(stringList[i])
        backTracking(idx+1)
        pop_char = case.pop()

        if pop_char in vowel:   # 모음이 빠질 경우 모음 갯수에서 1 빼줌
            vowel_cnt -= 1

코드를 보시면 먼저 모음을 담고 있는 array를 만들어 준 후, 백트래킹 함수를 구현하였습니다.

최종 출력할 문자들을 담고 있는 case라는 배열에 값을 넣어줄 때마다, 들어가는 문자가 모음인지 확인하여 모음의 갯수를 세어주었습니다.

영어는 자음 + 모음이므로 출력할 총 문자의 갯수에서 담긴 모음의 갯수를 빼주면 자음의 갯수가 나오므로 이를 활용하였습니다.

이를 바탕으로 최종 출력하기 전, 문제에서 주어진 조건이 부합하는지를 확인하고 조건에 부합하는 문자열만 출력하도록 구현하였습니다.

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

문제: 임의의 수열이 주어졌을 때, 6개의 수를 뽑을 수 있는 경우의 수를 구하는 문제

풀이 방법: 백트래킹

풀이 코드:

import sys

def backTracking(idx):
    if len(case) == 6:
        for i in range(6):
            print(case[i],end=' ')
        print()
        return

    for i in range(idx,array[0]+1):
        if len(case) > 0:
            if case[-1] >= array[i]:
                continue
        case.append(array[i])
        backTracking(idx+1)
        case.pop()
    return

while True:
    array = list(map(int,sys.stdin.readline().rstrip().split(' ')))
    if not array[0]:
        break
    case = []
    backTracking(1)
    print()

풀이 설명:

풀이에 핵심이 되는 backTracking 함수를 설명하고 가겠습니다.

def backTracking(idx):
    if len(case) == 6:
        for i in range(6):
            print(case[i],end=' ')
        print()
        return

    for i in range(idx,array[0]+1):
        if len(case) > 0:
            if case[-1] >= array[i]:
                continue
        case.append(array[i])
        backTracking(idx+1)
        case.pop()
    return

문제의 조건은 다음과 같습니다.

1) 6개의 수를 뽑아라

2) 사전 순으로 출력하라

if len(case) == 6:
    for i in range(6):
        print(case[i],end=' ')
    print()
    return

1번 조건을 만족시키기 위해, 출력할 value들을 담은 배열의 길이가 6일 경우 출력하도록 세팅하였습니다.

for i in range(idx,array[0]+1):
    if len(case) > 0:
        if case[-1] >= array[i]:
            continue
    case.append(array[i])
    backTracking(idx+1)
    case.pop()
return

backTracking은 다음과 같이 구성하였습니다.

먼저 2번 조건을 만족 시켜주기 위해, 뽑은 숫자를 저장하는 case 배열에 역순으로 수가 담기지 못하도록 조건문을 설정해주었습니다.

이후, 주어진 수열의 값을 백트래킹 기법을 통해 탐색하도록 하여 모든 경우의 수를 출력할 수 있도록 하였습니다.

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

문제: N x N 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제.

풀이 방법: 백 트래킹

풀이 코드:

n = int(input())
board = [0] * n
visited = [0]*n
count = 0


def checkAvailable(col):
    for i in range(col):
        if abs(board[col] - board[i]) == col - i:
            return False
    return True

def searchGraph(col):
    global count
    if col == n:
        count += 1
        return

    for i in range(n):
        if col == 0 and n % 2 == 0 and i == n/2:  # 보드가 짝수 size 일 경우, 대칭이기 때문에 *2 연산으로 연산 횟수 줄임
            return
        if visited[i]:
            continue
        board[col] = i
        if checkAvailable(col):
            visited[i] = True
            searchGraph(col+1)
            visited[i] = False

searchGraph(0)

if n % 2 == 0:
    print(count*2)
else:
    print(count)

풀이 설명:

board = [0] * n
visited = [0] * n

board에는 각 행에 퀸이 몇번째 열에 있는지 여부를 저장하는 배열이고, visited는 각 열에 퀸이 존재하는지 여부를 저장하는 배열입니다.

def checkAvailable(col):
    for i in range(col):
        if abs(board[col] - board[i]) == col - i:
            return False
    return True

checkAvailable은 퀸이 놓여질 수 있는지 여부를 판단하는 함수 입니다.

예를들어,  (0 , 0)과 (1 , 1)은 서로 대각선에 위치하는 점 입니다.  (4 , 5)와 (6 , 8)도 서로 대각선의 위치에 존재하는 점 입니다.

대각선에 위치하는 점들 끼리는 행의 값 차이와 열의 값 차이가 서로 같습니다.

따라서, 다음 조건을 통해 대각선 상에 위치한다면 False를 return 하도록 구성하였습니다.

def searchGraph(col):
    global count
    if col == n:
        count += 1
        return

    for i in range(n):
        if col == 0 and n % 2 == 0 and i == n/2:  # 보드가 짝수 size 일 경우, 대칭이기 때문에 *2 연산으로 연산 횟수 줄임
            return
        if visited[i]:
            continue
        board[col] = i
        if checkAvailable(col):
            visited[i] = True
            searchGraph(col+1)
            visited[i] = False

searchGraph 함수는 최종적으로 체스 보드에 퀸이 들어갈 수 있는 경우의 수를 탐색하는 함수 입니다.

한 행에 1개의 퀸만 넣는다고 하였을 때, 퀸이 체스 보드에 들어갈 수 있는 위치는 다음 조건을 만족하여야 합니다.

1. 앞선 행의 대각선 위치에 퀸이 존재하지 않을 것

2. 같은 열에 퀸이 존재하지 않을 것

visited 배열을 통애 같은 열 안에 퀸이 존재하는지 확인하고, 같은 열에 퀸이 존재하지 않을 경우에 대각선에 퀸이 존재하는지 확인합니다.

즉, 두 조건을 만족하면 visited에 해당 열에 퀸이 존재한다고 표시하고(True) 재귀를 통해 다음 행에 대한 searchGraph 함수를 호출합니다.

함수에 들어오는 행의 값이 n일 경우, 0~ n-1번째 행에 퀸이 채워졌다는 의미이므로 1개를 카운트 해줍니다.

추가적으로 시간을 줄이기 위해, 짝수 size의 체스판에서는 경우의 수가 좌우 대칭을 이루기 때문에 절반까지만 세고 x2를 해주는 방식을 사용하였습니다.

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

임의의 점으로 부터 가장 먼 노드를 2번 구해 지름을 구한다는 발상에 너무 감탄했던 문제입니다.

문제: 트리가 주어졌을 때, 트리의 지름을 구하는 문제입니다.

풀이 방법: 다잌스트라

풀이 코드:

import random
import sys
import heapq

n = int(input())

graph = [[] for _ in range(n+1)]
dist = [1E9] * (n+1)

for i in range(1,n+1):
    line = list(map(int,sys.stdin.readline().rstrip().split()))
    nowNode = line[0]

    for j in range(1,len(line)-1,2):
        graph[nowNode].append((line[j+1], line[j])) #cost, nextNode

def dijkstra(node):
    q = [(0,node)]

    while q:
        startCost, startNode = heapq.heappop(q)

        for nextCost,nextNode in graph[startNode]:
            distance = dist[startNode] + nextCost

            if dist[nextNode] > distance:
                dist[nextNode] = distance
                heapq.heappush(q,(distance,nextNode))

#임의의 점으로 부터 제일 먼 노드 X 구하기
startpos = random.randint(1,n)
dist[startpos] = 0
dijkstra(startpos)
index = dist.index(max(dist[1:]))

#X로부터 제일 먼 노드 Y 구하기
dist = [1E9] * (n+1)
dist[index] = 0
dijkstra(index)

#X-Y의 거리가 지름이 된다
print(max(dist[1:]))

풀이 설명:

먼저 입력 값을 보면,

1 3 2 -1

과 같이 입력이 주어질 경우, 1에서 3까지 가는 비용이 2가 된다는 의미이고

3 1 2 4 3 -1

과 같이 입력이 주어지면, 3에서 1까지 가는 비용이 2 그리고 3에서 4까지 가는 비용이 3이라는 의미입니다.

for i in range(1,n+1):
    line = list(map(int,sys.stdin.readline().rstrip().split()))
    nowNode = line[0]

    for j in range(1,len(line)-1,2):
        graph[nowNode].append((line[j+1], line[j])) #cost, nextNode

방향성이 없고 한줄에 한 노드로 부터 갈 수 있는 모든 노드의 정보가 주어지므로 다음과 같이 입력을 받아주었습니다.

def dijkstra(node):
    q = [(0,node)]

    while q:
        startCost, startNode = heapq.heappop(q)

        for nextCost,nextNode in graph[startNode]:
            distance = dist[startNode] + nextCost

            if dist[nextNode] > distance:
                dist[nextNode] = distance
                heapq.heappush(q,(distance,nextNode))

다음은 가장 거리가 먼 노드를 구하기 위해 다잌스트라 함수를 구현했습니다.

#임의의 점으로 부터 제일 먼 노드 X 구하기
startpos = random.randint(1,n)
dist[startpos] = 0
dijkstra(startpos)
index = dist.index(max(dist[1:]))

#X로부터 제일 먼 노드 Y 구하기
dist = [1E9] * (n+1)
dist[index] = 0
dijkstra(index)

#X-Y의 거리가 지름이 된다
print(max(dist[1:]))

그런 다음, 임의의점 하나로 부터 제일 먼 노드 X를 구해줍니다.

또, X로 부터 제일 먼 노드 Y를 구해줍니다.

이때, X로부터 Y까지의 거리가 트리의 지름이 되게 됩니다.

이 아이디어 발상에 감탄한 문제였습니다.