20210622 알고리즘 문제 풀이

백준 1874번 스택 수열

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

풀이

n = int(input())
stack = []
op = []
count = 1
temp = True
for i in range(n):
    num = int(input())
    while count <= num:
        stack.append(count)
        op.append('+')
        count += 1
    if stack[-1] == num:
        stack.pop()
        op.append('-')
    else:
        temp = False
if temp == False:
    print('NO')
else:
    for i in op:
        print(i)

• n을 입력값으로 받는다.
• stack과 op라는 빈 리스트를 만들고 count라는 변수를 1으로 선언한다.
• True값을 가진 temp를 선언한다.
• n번 반복하는 for문을 돌리면서 num으로 입력값을 받는다
• count가 num보다 작거나 같은 범위에서 반복:
  s에 count를 추가한다.
  op에 '+'를 추가한다.
• 만약 s의 마지막 값과 num이 같다면
• s의 마지막 값을 꺼내고
• op에는 '-'를 추가한다.
• s의 마지막 값과 num이 같아지지 않는 경우에는
• temp에 False로 저장하고 NO를 출력한다.

백준 1260번 DFS와 BFS

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

풀이

from sys import stdin
n, m, v = map(int, stdin.readline().split())
matrix = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    line = list(map(int, stdin.readline().split()))
    matrix[line[0]][line[1]] = 1
    matrix[line[1]][line[0]] = 1
def bfs(start):
    visited = [start]
    queue = [start]
    while queue:
        n = queue.pop(0)
        for c in range(len(matrix[start])):
            if matrix[n][c] == 1 and (c not in visited):
                visited.append(c)
                queue.append(c)
    return visited
def dfs(start, visited):
    visited += [start]
    for c in range(len(matrix[start])):
        if matrix[start][c] == 1 and (c not in visited):
            dfs(c, visited)
    return visited
print(*dfs(v,[]))
print(*bfs(v))

• 인접행렬 방식으로 행과 열을 통해서 값을 해당 숫자들이 연결되어 있는지 확인하도록 한다.
• N개의 숫자가 있으므로 N+1 X N+1의 행렬을 리스트를 통해서 만들고 0으로 채워준다.
• 인덱스와 값을 일치시키기 위해서 N+1개의 숫자를 사용한다
• 0행 0열은 숫자가 없으므로 0 값으로 비어있다.
• 연결된 숫자들 값을 입력받아서 해당 행과 열의 값을 1로 바꿔준다.
• 이를 통해서 행의 숫자와 열의 숫자가 연결되어 있다는 표시를 해준다.
• DFS와 BFS를 구현한 후 해당 값을 출력한다.

백준 2630번 색종이 만들기

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

풀이

from sys import stdin
zero = 0
one = 0
li = []
def check(li):
    global one, zero
    li_one = sum(li, [])
    num = sum(li_one)
    if num == len(li_one):
        one += 1
    elif num == 0:
        zero += 1
    else:
        for i in split(li):
            check(i)
def split(li):
    side = int(len(li[0]) // 2)
    start = [(0, 0), (side, 0), (0, side), (side, side)]
    result = []
    for p in start:
        result.append([[li[p[0] + i][p[1] + j] for j in range(side)] for i in range(side)])
    return result
N = int(stdin.readline().strip())
for i in range(N):
    li.append([int(i) for i in stdin.readline().strip().split()])
check(li)
print(zero)
print(one)

• 간단한 분할정복 문제로 나누기전 0,1,전체인지 확인해준 후 아닌 경우에는 4등분을 해서 재귀를 이용하면 된다.

백준 15650번 N과 M

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

풀이

import sys
N,M = map(int, sys.stdin.readline().split())
check_list = [False] * N
output = []
def dfs(depth,N,M):
    if depth == M:
        print(' '.join([str(x) for x in output]))
        return
    for i in range(N):
        if check_list[i]:
            continue
        check_list[i] = True
        output.append(i+1)
        dfs(depth+1, N, M)
        output.pop()
        for j in range(i+1, N):
            check_list[j] = False
dfs(0,N,M)

• False가 N의 길이만큼 있는 check_list를 만들어준다. 이는 확인할 숫자인지 아닌지 분별해줄 역할을 하는데 사용될 것이다.
• output 리스트는 출력할 때 사용할 리스트이다.
• for문을 보면, 만약 check_list의 i번째가 True라면, 다음 loop로 넘어간다는 것이다. 만약 아니라면, 해당 i번째는 True로 지정해주고,
  output 리스트에 i+1을 추가해준다.(i=0부터 시작하기 때문) 이후, 다시 재귀로 dfs함수를 다시 실행한다.
• 이렇게 하면, 이전에 check_list[i]=True라고 지정해놓은 부분은 건너뛰고 그 다음의 i부터 시작하게 된다.

백준 2798번 블랙잭

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

풀이

N,M = map(int,input().split())
arr = list(map(int,input().split()))
result = 0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if arr[i] + arr[j] + arr[k] > M:
                continue
            else:
                result = max(result, arr[i] + arr[j] + arr[k])
print(result)

• 모든 경우의 수를 다 뒤져봐야 하는 완전 탐색 문제
• N,M을 입력받아 int로 변환
• 카드에 쓰여 있는 수들을 list로 만들어 저장한다.
• 문제 조건에 적합한 수를 저장하여 반환하기 위한 변수 result 선언
• 3개의 카드를 뽑아야 하며 이에 대한 모든 경우의 수를 살펴보기 위해 3중 for문을 이용한다.
• 첫 for문에서는 0
• N, 세번째 for문에서는 2~N을 순회하면서
• 모든 경우의 수를 확인하며 각각의 값을 더한 뒤, 세 카드의 값이 M보다 클 경우에는 continue
• M보다 크지 않을 경우, 일단 정답의 가능성이 존재하므로 result에 저장
• 이렇게 모든 경우를 반복하면 결국, result 변수에는 M의 값 또는 M에 가장 가까운 값이 저장된다.

백준 2231번 분해합

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

풀이

N = int(input())
result = 0
for i in range(1,N+1):
    A = list(map(int,str(i)))
    result = i + sum(A)
    if result == N:
        print(i)
        break
    if i == N:
        print(0)

• N을 입력값으로 받는다.
• 입력값과 비교하기 위한 변수 result
• str 함수를 통해 i의 각 자리수를 A 리스트에 넣기
• i와 각 자리수가 들어간 A 리스트의 합을 더하면 분해합(result)이 된다.
• 분해합(result)과 N이 같다면 i를 출력한다 >> 가장 작은 생성자
• i와 N이 같다면 0을 출력한다 >> 생성자가 없는 경우