태야

<내 코드>

N, M = map(int, input().split())
visited = [0 for _ in range(N)]
arr = []

def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1  # 중복 제거
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색
            arr.pop()  # 탐사한 내용 제거

            # 순열 부분과의 차이점
            for j in range(i+1, N):
                visited[j] = 0

dfs(0)

처음 i의 DFS 탐색에 사용 된 i값을 제외시키는 것이 순열과 다른 조합의 차이다.

파이썬 itertools 모듈의 combinations를 사용한 방법

from itertools import combinations

N, M = map(int, input().split())

p = combinations(range(1, N+1), M)
for i in p:
    print(*i)

<내 코드>

N, M = map(int, input().split())
visited = [0 for _ in range(N)]
arr = []


def dfs(cnt):
    if cnt == M:
        print(*arr)
        return

    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1  # 중복 제거
            arr.append(i+1)

            dfs(cnt+1)  # 다음 깊이 탐색

            visited[i] = 0  # 탐사 완료 후 다시 초기화
            arr.pop()  # 탐사한 내용 제거


dfs(0)

DFS와 백트래킹을 이용해 푸는 문제다. 재귀가 사용되다 보니 이해를 하는데 꽤 힘들었다.. 

파이썬 itertools 모듈을 사용한 방법

from itertools import permutations

N, M = map(int, input().split())

p = permutations(range(1, N+1), M)
for i in p:
    print(*i)

<내 코드>

from collections import deque


def bfs():

    while q:
        s, c = q.popleft()
        # 복사, 붙여넣기, 삭제 후 1초씩 증가 && 다녀간 곳 q에 추가
        # 복사
        if check[s][s] == -1:
            check[s][s] = check[s][c] + 1
            q.append((s, s))
        # 붙여넣기
        if s+c <= S and check[s+c][c] == -1:
            check[s+c][c] = check[s][c] + 1
            q.append((s+c, c))
        # 삭제
        if s-1 >= 0 and check[s-1][c] == -1:
            check[s-1][c] = check[s][c] + 1
            q.append((s-1, c))


S = int(input())
q = deque()
MAX = 1001
check = [[-1]*MAX for _ in range(MAX)]

check[1][0] = 0
q.append((1, 0))

bfs()

ans = -1
for i in range(S):
    if check[S][i] != -1:
        if ans == -1 or ans > check[S][i]:
            ans = check[S][i]
print(ans)

처음에 문제를 복사 - 붙여 넣기 - 복사- 붙여 넣기... 하는 것으로 잘못 이해했었다. 실제로는 클립보드에 들어있는 이모티콘은 여러 번 화면에 붙여 넣기가 가능한 것이다.

이 문제는 기존의 BFS 문제랑 조금 차이가 있다. 기존에는 입력을 그래프 형태로 주어졌는데, 이 문제는 본인이 새로 그래프를 만들어야 했다. 복사, 붙여넣기, 삭제 부분을 작성하고 현재 s,c에 대한  시간 check [s][c] 값에 +1초씩 해준다.  그리고 찾고자 하는 입력 값 check [s] 중 최솟값을 찾아 출력하면 된다.

<내 코드>

import heapq
import sys


def bfs():
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    while(q):

        cnt, x, y = heapq.heappop(q)  # (0,0,0)형식
        done[x][y] = 1

        if x == N-1 and y == M-1:
            return cnt

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (0 <= nx < N) and (0 <= ny < M) and done[nx][ny] == 0:
                done[nx][ny] = 1

                # 길이 있는 경우 우선순위(최소힙)가 가도록 한다.
                if maps[nx][ny] == '0':
                    heapq.heappush(q, (cnt, nx, ny))
                elif maps[nx][ny] == '1':
                    heapq.heappush(q, (cnt+1, nx, ny))
                


M, N = map(int, sys.stdin.readline().split())
maps = [list(str(sys.stdin.readline())) for _ in range(N)]
q = []
done = [[0]*M for _ in range(N)]

heapq.heappush(q, (0, 0, 0))

print(bfs())

BFS와 우선수위 큐를 이용하는 독특한 문제이다. 처음에는 BFS로만 문제를 풀려고 했지만 어려웠다.

heap을 사용하는 이유는 '벽을 가장 적게 부수고 이동하는 경우'가 항상 우선순위에 있는 채로 BFS를 해야하기 때문이다.

여기서 길(0)이 있다면 우선순위를 줘서 그 길부터 가도록 한다. 만약 길이 없고 벽(1)만 있다면 cnt+1을 해줘 벽을 부순다. 우선순위가 낮은 값부터 탐색하게 되서 원하는 동작이 구현된다.

<내 코드>

import heapq
from sys import stdin

N = int(stdin.readline())
heap = []

for i in range(N):
    num = int(stdin.readline())
    if num == 0:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)

    else:
        heapq.heappush(heap, [abs(num), num]) # 절댓값 처리해 작은 값부터 힙에 넣는다.(우선순위, 값)

push 할 때는 절댓값을 기준으로 최소 힙으로 정렬해주면, pop의 경우에 절댓값이 작은 값이 먼저 pop 되고 절댓값이 작은 경우가 여러 개일 경우에는 기존 값이 작은 수가 먼저 출력되게 된다.

<내 코드>

import heapq
from sys import stdin
N = int(stdin.readline())
heap = []
for i in range(N):
    num = int(stdin.readline())
    if num == 0:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)

    else:
        heapq.heappush(heap, [num, num])

<내 코드>

import heapq
from sys import stdin

N = int(stdin.readline())
heap = []

for i in range(N):
    num = int(stdin.readline())
    if num == 0:
        if heap:
            print(-heapq.heappop(heap))  # 음수된 값에서 가장 작은 것 빼서 다시 음수하면 최대값임
        else:
            print(0)
    else:
        heapq.heappush(heap, -num)  # 음수처리해 최대힙처럼 구성

파이썬에서는 최소 힙만 제공해준다. 따라서 이 문제에서는 최대 힙을 활용해야 하기에 기본 힙 모듈을 최대 힙으로 구현했다.

방식은 여러 가지가 있는 것 같다. 내가 사용한 방법은 우선 heappush를 할 때 넣어주는 값을 음수 처리를 해준다.

그다음 heappop으로 값을 꺼내면 최솟값이 나오는데 이것을 다시 음수를 해주면 최댓값이 된다.

아래는 튜플, 리스트 형식을 활용한 방식이다.

import heapq
from sys import stdin
N = int(stdin.readline())
heap = []
for i in range(N):
    num = int(stdin.readline())
    if num == 0:
        if heap:
            print(heapq.heappop(heap)[1])  # 값은 리스트or 튜플형태로 나오기에 1번째 요소를 뽑으면 값이 된다.
        else:
            print(0)

    else:
        heapq.heappush(heap, [-num, num])  # 값을 넣을 때 반대로 우선순위 처리해준다. (우선순위, 값)

<내 코드>

N = int(input())
nums = list(map(int, input().split()))

k = N-2
check = False
while k > -1:
    if nums[k] > nums[k+1]:
        for i in range(k+1, len(nums)):
            if nums[i] < nums[k]:  # k 이후에서 nums[k]보다 작은 것중 가장 큰 인덱스 찾음
                m = i
                check = True
    if check == True:
        break

    k -= 1


if check == False:
    print(-1)
else:
    # k, m 값 바꾸기
    nums[k], nums[m] = nums[m], nums[k]

    # k 이후 값 내림차순 정렬
    tmp = nums[k+1:]
    tmp.sort(reverse=True)

    ans = nums[:k+1] + tmp
    print(*ans)

진짜 짜증나는 문제였다..