손가락놀이터

문제리뷰

1. 한번만 상하좌우를 계산하여 지우면 되는 간단한 문제이다. 주의해야할 점으로는 입력값을 matrix로 구현한 다음 deepcopy를 써야하는 것인데 2차원배열부터는 copy나 [:]로 복사가 안되기 때문이다.
2. dy와 dx를 통해 상하좌우를 검색하고 범위를 넘어가는 경우도 바다로 처리하기 때문에 이것도 처리해야한다.
3. 이후 바다만 있는 row와 column을 빼고 print하면 끝이 난다.

문제링크

from sys import stdin
import copy

R, C = map(int, stdin.readline().split())

matrix = [list(input()) for _ in range(R)]
result = copy.deepcopy(matrix)

dy = [-1,0,1,0]
dx = [0,-1,0,1]

for y in range(R):
    for x in range(C):
        count = 0
        if matrix[y][x] == '.':
            continue

        for i in range(4):

            ny = y + dy[i]
            nx = x + dx[i]

            if 0 <= ny < R and 0 <= nx < C:
                if matrix[ny][nx] == '.':
                    count += 1
            else:
                count += 1
        if count >= 3:
            result[y][x] = '.'

start_y, end_y = 0, 0
for i in range(R):
    if 'X' in result[i]:

        start_y = i
        break
for i in range(R-1, -1,-1):
    if 'X' in result[i]:       
        end_y = i
        break

tmp = []
for j in range(C):
    for i in range(start_y, end_y + 1):
    
        if 'X' == result[i][j]:
            tmp.append(j)
            break


for y in range(start_y, end_y+1):
    print("".join(result[y][tmp[0]:tmp[-1]+1]))

문제 후기

1. 처음 접하는 백트래킹 문제로 어떻게 해야하는지 몰라 해당 사이트를 참고했습니다.

문제 링크

www.acmicpc.net/problem/9663

from sys import stdin

def find_queen(sol, n):
    global answer

    # sol 갯수가 N개가 되면 + 1
    if len(sol) == N:
        answer += 1
        return  0
    # 후보자 리스트.
    candidate = [i for i in range(n)]
    for i in range(len(sol)):
        # sol의 i번째와 현재 열의 거리.
        distance = len(sol) - i
        # 같은 열의 후보 제거
        if sol[i] in candidate:
            candidate.remove(sol[i])
        # 해당 퀸의 대각선의 +방향 확인
        if sol[i] + distance in candidate:
            candidate.remove(sol[i] + distance)
        # 해당 퀸의 대각선의 -방향 확인
        if sol[i] - distance in candidate:
            candidate.remove(sol[i] - distance)
    
    if candidate != []:
        for i in candidate:
            # 후보를 추가하여 재귀 실행
            find_queen(sol + [i], n)
    # 후보가 없는경우 종료
    else:
        return 0


N = int(stdin.readline())
answer = 0

for i in range(N):
    find_queen([i], N)
print(answer)

문제 리뷰

1. DFS와 BFS를 매트릭스를 통해 구현되는 방식이다.
2. DFS와 BFS의 정석으로 기초인 문제같다.

문제 링크

import sys
from collections import deque

n, m, v = map(int, sys.stdin.readline().split())
matrix = [[0] * (n+1) for _ in range(n+1)]

for _ in range(m):
    # 입력값 매트릭스로 구현
    line = list(map(int,sys.stdin.readline().split()))
    matrix[line[0]][line[1]] = 1
    matrix[line[1]][line[0]] = 1

# DFS 구현
def dfs(start, visited):
    # stack 활용
    visited += [start]
    for c in range(len(matrix[start])):
        # start에서 c로 갈 수 있으면서 아직 방문하지 않은 경우에 방문.
        if matrix[start][c] == 1 and c not in visited:
            dfs(c,visited)
    return visited

# BFS 구현
def bfs(start):
    # Queue로 구현
    visited = [start]
    queue = deque([start])

    while queue:
        # popleft로 0에 값 뽑기
        n = queue.popleft()
        for c in range(len(matrix[start])):
            # n에서 c로 갈 수 있으면서 아직 방문하지 않은 경우에 방문.
            if matrix[n][c] == 1 and c not in visited:

                visited.append(c)   # 방문처리
                queue.append(c)     # Queue에 추가
    return visited

문제 후기

1. 이전에 프로그래머스에서 푼 순위라는 문제와 비슷하다고 생각했습니다. 아래에 링크를 남기겠습니다.
2. 순위에서 푼 방식대로 모든 사람의 해쉬를 만들고 비교한 값을 통해 갱신하는 방식으로 하니 메모리 초과로 틀렸고 알고리즘을 변경하기로 했습니다.
3. 알고리즘을 생각하다 DFS로 생각했고 문제를 풀었습니다.
4. DFS외에, 위상정렬이라는 것이 있는 것을 알게 됐고 모르는 방식이라 공부를 했습니다. terms.naver.com/entry.nhn?docId=3579618&cid=59086&categoryId=59093를 보고 위상정렬이 어떤 것인지 파악했습니다.
5. 위상 정렬 알고리즘으로 비교에서 큰 적이 없는 값부터 시작해서 DFS 방식으로 하나씩 차례대로 나아가는 방식으로 해결했습니다.

문제링크

from sys import stdin
from _collections import deque

N, M = map(int, stdin.readline().split())

num_dict = {}

for n in range(1,N+1):
    num_dict[n] = []


taller = [0] * (N+1)    # 큰 횟수
queue = deque([])       # 큐 생성


for _ in range(M):
    A, B = map(int, stdin.readline().split())
    # B에 큰 횟수를 저장
    taller[B] += 1
    # A에서 B로 갈 수 있도록 설정(DFS)
    num_dict[A].append(B)

# 비교에서 큰 적이 없는 값
for num in range(1,N+1):
    if taller[num] == 0:
        queue.append(num)
# 결과값
answer = []

# queue에 값이 있는 동안 반복
while queue:
    now = queue.popleft()
    # 결과값에 추가
    answer.append(str(now))

    # 간선 파악
    for i in num_dict[now]:
        # 1이면 queue에 추가
        if taller[i] == 1:
            queue.append(i)
        taller[i] -= 1
print(" ".join(answer))

문제 후기

1. 문제를 보고 이전에 프로그래머스에서 풀어본 풍선 터뜨리기와 비슷한 문제라고 생각을 했습니다. 아래에 링크를 남기겠습니다.
2. 풍선 터뜨리기 처럼 가장 큰 값을 이용해서 풀려고 했으나 반례가 있어서 다른 방법으로 풀어야했습니다.
3. 최악의 경우를 고려해봤을때 단순히 모든 배열을 탐색해도 된다 판단하여 모든 배열을 기준으로 찾기로 했습니다.
4. 각 인덱스 값을 기준으로 왼쪽부분과 오른쪽부분으로 나눠 스택과 이분탐색을 활용하여 스택을 만들었습니다.
5. 문제의 예시를 들면, 1 5 2 1 4 3 4 5 2 1이고 굵은 5가 기준이면 왼쪽 배열은 아래와 같은 순서로 이뤄집니다.
   1. [1]   비어있는 배열에 1 추가
   2. [1,2]   스택의 맨 위의 값 1보다 크므로 스택에 2 추가
   3. [1,2]   스택의 맨 위의 값 2보다 작으므로 이분탐색하여 1->1 교체 (이분탐색하면 idx가 0)
   4. [1,2,4] 스택의 맨 위의 값 2보다 크므로 스택에 4 추가
   5. [1,2,3] 스택의 맨 위의 값 4보다 작으므로 이분탐색하여 4->3 교체 (이분탐색하면 idx가 2)
   6. [1,2,3,4] 스택의 맨 위의 값 3보다 크므로 스택에 4 추가

문제링크

from sys import stdin
from bisect import bisect_left

N = int(stdin.readline())

arr = list(map(int, stdin.readline().split()))

# 만약 배열 크기가 1이면 1출력하고 종료
if len(arr) == 1:
    print("1")
else:

    answer = 0  # 결과값
    # 모든 인덱스 탐색
    for idx in range(len(arr)):
        # 왼쪽 부분과 오른쪽 부분 나눠서 실행
        # 값 부분은 stack으로 숫자 입력
        left_stack, right_stack = [], []
        
        # 왼쪽 부분
        for i in range(idx):
            # 해당값보다 큰 경우 넘어가기
            if arr[i] >= arr[idx]:
                continue
            # 첫번째 값.
            elif left_stack == []:
                left_stack.append(arr[i])
            else:
                # 만약 stack 마지막 값보다 큰 경우는 추가
                if left_stack[-1] < arr[i]:
                    left_stack.append(arr[i])
                # 만약 stack 마지막 값보다 작은 경우
                # 이분 탐색으로 해당 값이 들어갈 위치 찾아서 교체
                else:
                    left_stack[bisect_left(left_stack, arr[i])] = arr[i]

        # 오른쪽 부분
        for i in range(len(arr) - 1, idx,-1):
            # 해당값보다 큰 경우 넘어가기
            if arr[i] >= arr[idx]:
                continue
            # 첫번째 값
            elif right_stack == []:
                right_stack.append(arr[i])
            else:
                # 만약 stack 마지막 값보다 큰 경우는 추가
                if right_stack[-1] < arr[i]:
                    right_stack.append(arr[i])
                # 만약 stack 마지막 값보다 작은 경우
                # 이분 탐색으로 해당 값이 들어갈 위치 찾아서 교체
                else:
                    right_stack[bisect_left(right_stack, arr[i])] = arr[i]

        # 만약 오른쪽 부분이 있는 경우 해당값 추가
        if right_stack:
            right_stack.append(arr[idx])
        # 없는 경우에는 왼쪽 부분에 해당값 추가
        else:
            left_stack.append(arr[idx])
        # answer와 왼쪽, 오른쪽 배열 갯수 비교하여 큰 값 저장
        answer = max(answer, len(left_stack) + len(right_stack))

    print(answer)

문제후기

1. 문제를 보고 이해하는데 오래걸렸습니다. 문제는 R, G, B 값이 하나씩 주어지는데 이때 앞뒤의 집과 달라야한다는 것과 R, G, B를 그리는데 사용되는 페인트의 양이 최소가 되도록 하는 것입니다. 문제를 보고 DP를 보고 풀면 되겠다고 생각했고 이전에 프로그래머스에서 푼 땅따먹기와 같다고 판단했습니다.
2. R, G, B값과 이전까지 더해진 값의 합을 다시 저장합니다. 이때 이전 위치와 같은 경우는 제외합니다.
3. 마지막 줄에서 가장 최소의 값을 찾습니다.

예시 풀이

문제 예시를 DP를 이용하면 최종적으로 아래의 값이 나온다.

프로그래머스에서 비슷한 문제

문제링크

from sys import stdin

# N 개의 줄
N = int(stdin.readline())

# 배열 RGB값 n개
arr = [list(map(int, stdin.readline().split())) for _ in range(N)]

# 초기 설정값
answer = 1e9

# 1번쨰 줄부터 시작
for n in range(1,N):
    for i in range(3):
        # 미니멈 초기값
        minimum = 1e9
        for j in range(3):
            # 이전과 같은 색인 경우 제외
            # 가장 작은 값 찾기
            if i != j and arr[n][i] + arr[n-1][j] < minimum:
                minimum = arr[n][i] + arr[n-1][j]
        # 가장 작은 값 기록
        arr[n][i] = minimum

print(min(arr[-1]))

문제후기

1. 처음 문제를 보고 BFS를 활용해서 문제를 풀려고 했습니다. 최악의 경우 500 * 500을 BFS로 탐색하는 경우이지만 시간제한이 2초로 애매하지만 통과할 수 있다고 생각하고 코드를 작성했습니다.
2. BFS로 제출한 결과 시간초과에서 걸려서 알고리즘이 틀린 것으로 생각하고 알고리즘을 변경했습니다.
3. 다시 생각해낸 알고리즘은 DP로 최대 Heap과 연관시켜 생각했습니다. 대나무가 많은 순서로 Heap 정렬을 해준 이후 pop을 하면서 메모이제이션을 했습니다. 상하좌우의 메모 중 가장 큰 값 + 1로 메모를 갱신했습니다.
4. Heap에 남은 값이 없으면 모든 메모가 끝났으므로 메모 중에서 가장 큰 값을 출력했습니다.

문제링크

from sys import stdin
import heapq
from itertools import chain

# 상하좌우
dy = [-1,0,1,0]
dx = [0,-1,0,1]

# n 개 매트릭스
n = int(stdin.readline())
# 매트릭스 값 입력
matrix = [list(map(int, stdin.readline().split())) for _ in range(n)]
# 메모이제이션
memoization = [[0] * n for _ in range(n)]
# 최대 힙정렬 할 배열
heap = []

# 최대 힙 정렬
for y in range(n):
    for x in range(n):
        # heapq는 최소힙정렬이므로 -1을 곱해서 최대힙정렬로 한다.
        heapq.heappush(heap, (-1 * matrix[y][x], y, x))


# heap에 값이 없을때까지
while heap:
    _, y, x = heapq.heappop(heap)
    chk_arr = []
    # 상하좌우 체크
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < n and 0 <= nx < n:
            # 만약 상,하,좌,우 값이 더 크다면 해당 메모값 배열에 추가
            if matrix[y][x] < matrix[ny][nx]:
                chk_arr.append(memoization[ny][nx])

    if chk_arr: # 만약 배열에 값이 있으면 가장 큰 값 + 1
        memoization[y][x] = max(chk_arr) + 1
    else: # 배열에 값이 없으면 1
        memoization[y][x] = 1
# 메모 중에서 가장 큰 값 출력
print(max(chain(*memoization)))

문제후기

1. 우선순위 큐를 활용한 문제로 Python은 우선순위 큐를 heap을 활용해서 해결합니다.
2. 절대값이 기준이고 그 다음 기준이 숫자이므로 (절대값, 숫자) 형식으로 heap에 push합니다.
3. 0이 나올 경우 heap에서 pop을 해서 출력합니다.

문제링크

from sys import stdin
import heapq

N = int(stdin.readline())
# 우선순위 큐
heap = []

for n in range(N):
    num = int(stdin.readline())
    if num != 0:
        # 0이 아닌 경우 우선순위 큐에 (절대값, 숫자) 삽입
        heapq.heappush(heap,(abs(num), num))
    # 0인경우
    else:
        # 큐가 비어있으면 0 출력
        if len(heap) == 0:
            print(0)
        else:
            # 큐에 값이 있으면 pop
            print(heapq.heappop(heap)[1])