손가락놀이터

문제 후기

1. 문제를 보고 DFS나 BFS로 풀어야되는 것을 파악했다. 먼저 DFS로 풀어봤다.
2. 처음에 DFS로 풀면서 set을 활용해서 했다. 칸을 넘어갈때마다 set에 add, remove를 하면서 하니 시간초과가 발생했다. -> 그래서 메모이제이션으로 각 알파벳의 활용 여부를 1, 0으로 나타내야했다.
3. BFS로 풀어볼때는 deque를 활용해서 풀려고 했다. deque를 활용하니 이번에는 메모리초과....... 확인해보니 2가지 경우가 동시에 같은 칸으로 가는 경우가 있고 알파벳 역시 동일한 경우였다. 혼자 해결을 하지 못해 찾아보니 deque가 아닌 set을 활용....😥 BFS를 할 때 항상 deque만 활용하던 것이 잘못된 것이었다. 다음부터는 확실하게 이해하고 어떤 것을 써야할지 생각하자.

문제링크

from sys import stdin
from _collections import deque

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

# dfs로 풀 경우 메모이제이션으로 각 알파벳 visit 체크해야함.
def dfs(y, x, ans):
    global answer, chk

    answer = max(ans, answer)

    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        if 0 <= ny < R and 0 <= nx < C:
            # print(ny, nx, matrix[ny][nx], chk)
            if matrix[ny][nx] not in chk:
                chk.add(matrix[ny][nx])
                dfs(ny, nx, ans+1)
                chk.remove(matrix[ny][nx])

# bfs로 풀 경우 deque로 할 경우 중복되는 경우 때문에 메모리 초과 발생. set으로 해결해야함.
def bfs(y, x, chk):

    answer = 1
    queue = set([(y, x, chk)])

    while queue:
        ay, ax, chk_val = queue.pop()
        answer = max(answer, len(chk_val))

        for i in range(4):
            ny, nx = ay + dy[i], ax + dx[i]
            if 0 <= ny < R and 0 <= nx < C and matrix[ny][nx] not in chk_val:
                queue.add((ny, nx, chk_val + matrix[ny][nx]))
    
    return answer

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

matrix = [list(map(str, input())) for _ in range(R)]
chk = matrix[0][0]

print(bfs(0,0,chk))

문제리뷰

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)))