GW LABS

백준 4963번 섬의 개수 문제는 전형적인 그래프 탐색 문제이다. BFS, DFS 두 방법 모두 풀이가 가능하고 인접 행렬 형태의 자료구조를 탐색하는 연습을 하기에 좋은 문제이다. 문제를 풀면서 BFS로 접근했지만 메모리 초과, 시간 초과 문제로 DFS로 변경해서 풀이했다. 소스구조에 어떤 문제가 있는지는 차후에 분석해봐야 한다. 아래의 소스코드는 DFS로 풀이한 솔루션이다. import sys sys.setrecursionlimit(10**6) def dfs(row, col): dx = [0, 0, 1, -1, 1, -1, 1, -1] dy = [1, -1, 0, 0, -1, 1, 1, -1] board[row][col] = 0 for idx in range(8): nx = col + dx[idx] n..

백준 18044번 쉬운 계단 수 문제는 전형적인 백트래킹, 동적계획법 문제였다. 처음 문제를 접했을 때 당황했지만, 천천히 의사코드로 먼저 로직을 구성하고 나서는 어렵지 않게 풀이할 수 있었다. 하향식으로 문제를 풀었지만 상향식 해결법으로 풀이하는 고수들도 많다. 의사코드를 적어놔서 독자 여러분들도 어렵지 않게 로직을 이해할 수 있을 거라고 생각한다. import sys def find_step_number(length, last_num, container, cache): # 컨테이너 길이가 N이라면 if length == 0: return 1 if cache[length][last_num] != -1: return cache[length][last_num] # 숫자 0-9까지 반복 count = 0 f..

1932번 문제인 정수 삼각형은 동적 계획법으로 풀 수 있는 문제이다. 맨 처음 접근할 때 상향식 동적 계획법으로 풀이하려고 했으나, 그리디 방식으로 설계를 해버려서 시간을 낭비했다. 아에 하향식으로 접근해서 재귀적으로 풀이해 문제를 맞출 수 있었다. 그러나 상향식으로 풀이하면 실행속도를 아주 빠르게 가져갈 수 있으니, 계속 상향식으로 접근하는 연습을 해야겠다. 아래의 코드는 하향식 접근법이다. import sys sys.setrecursionlimit(10**6) def find_sum(idx_row, idx_selected, triangle, cache): if idx_row == len(triangle): return 0 if cache[idx_row][idx_selected] != 0: retur..

백준 단계별 문제란 백트래킹에 수록되어 있는 문제이다. 재귀함수를 이용해서 백트래킹을 해나가면 풀 수 있다. 많은 분들이 재귀함수, 그래프 탐색 등을 이용해서 푼 것 같다. 그러나 파이썬을 이용하면 combinations 모듈을 통해 간단하게 구현할 수 있다. import sys from itertools import combinations if __name__ == "__main__": player_count = int(sys.stdin.readline()) ability_table = [] for _ in range(player_count): ability_table.append(list(map(int, sys.stdin.readline().split(" ")))) answer = sys.maxsiz..

그래프 탐색문제에서는 어떤 방식으로 탐색해야 문제를 빠르게 풀 수 있을지 판단하는 것이 문제의 관건이다. 7576번 토마토 문제는 DFS보다 BFS로 푸는 것이 좀 더 빠르고 쉽게 해결할 수 있는 방법이었다. 문제의 핵심은 그래프를 탐색하기 전에 탐색을 해야하는 위치를 미리 큐에 넣어두고 탐색을 시작하는 것이다. 아래는 파이썬 풀이이다. import sys from collections import deque answer = 0 def print_table(tomato_table): print() for row in range(row_count): for col in range(col_count): print(tomato_table[row][col], end=" ") print() def bfs(toma..

프로그래밍 문제 중에서 나한테 부담이 큰 부분은 구현 문제들이다. 여러 조건들을 차례대로 구현하기만 하면 되는 문제들이지만 긴장된 상태에서 허겁지겁 문제를 읽다보면 실수가 많이 발생한다. 이번 문제를 풀 때에도 실제 테스트도 아닌데 그런 묘한 긴장감이 있었다. 구현 문제를 접근 할 때에는 반드시 주석으로 의사코드를 작성하고 접근해야한다. 이번 문제도 그런 접근이 효과적이었다. 문제의 조건은 아래와 같다. - 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. - 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. - 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 자칫 겁먹을 수도 있는 문제인데 가만히 ..

문제 조건을 제대로 파악하지 않고 우선순위 큐이겠거니 접근한 결과, 1시간 가량을 날려먹었다. 최소, 최대 힙으로 구현한 우선순위 큐에 대한 이해가 낮아서 이런 문제가 발생했다. 문제 조건만 제대로 파악하고 파이썬을 활용하면 아주 손쉽게 풀 수 있는 문제였다. 초기 인덱스를 값과 함께 묶어준 다음 큐 연산을 수행하는 게 핵심 아이디어이다. import sys from collections import deque def rotate_documents(ziped_documents): zip_max = max(ziped_documents)[0] while ziped_documents[0][0] != zip_max: ziped_documents.rotate(-1) if __name__ == "__main__":..

깊이 우선 탐색을 복습해보면서 재미있는 제약조건을 해결하는 문제였다. 나를 포함한 많은 사람들이 비가 안오는 경우를 놓쳐 정답률이 낮은 것 같다. 깊이 우선 탐색을 하면서 한 번 함수가 종료될 때마다 카운트 변수를 하나씩 늘려주면 조건에 해당하는 영역을 셀 수 있다. import sys sys.setrecursionlimit(10 ** 6) def dfs(row, col, limit_height, table, visited): if visited[row][col]: return dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] visited[row][col] = True for idx in range(4): row_next = row + dy[idx] col_next = col + dx..