GW LABS

백준 11497번 통나무 건너뛰기는 그리디 문제로 정렬을 해서 적절한 순서로 통나무들을 배열시키는 문제이다. 기본 아이디어는 우선 통나무들을 정렬시키고 큰 통나무들을 가운데에, 나머지 통나무들을 배열 양쪽 끝쪽으로 배열시키면 되는 것이다. 그 후 가운데서부터 왼쪽 끝, 오른쪽 끝으로 차이를 계산해서 가장 큰 값을 리턴하면 된다. 처음 접근방법은 가운데 값에서 한 개의 차이값들만 계산해서 [1, 2, 3, 4, 5, 100, 101, 102, 103, 104] 같은 예외에서 실패했다. 다른 그리디 문제들을 통해 예외를 생각해보는 연습을 계속해야겠다. import sys cases = int(input()) for _ in range(cases): length = int(input()) lumbers = l..

14891번 톱니바퀴는 구현 및 시뮬레이션 문제로 좋은 연습이 된 문제다. 4개의 기어들이 회전방향에 따라서 옆에 붙어있는 기어들도 회전시킨다. 그런데 서로 맞물린 극성이 다르다면 회전시킬 수 없고, 회전시킬 수 없는 기어에 맞물린 기어들도 회전시킬 수 없다. 문제를 읽어가면서 부담감이 컸는데 천천히 구현해가면 충분히 풀이할 수 있는 문제였다. 구현과 시뮬레이션 관련한 문제를 좀 더 연습을 많이 해야겠다. import sys from collections import deque if __name__ == "__main__": gears = [] for _ in range(4): gears.append(deque(list(map(int, list(sys.stdin.readline().replace("\n"..

백준 2437번 저울 문제는 정렬을 이용해서 풀 수 있는 그리디 알고리즘 문제이다. 주어진 추들을 정렬하고 추들을 이용해서 만들 수 없는 무게의 최소값을 찾는 문제이기 때문에 역순으로 정렬하여 접근했다. 처음 풀이에서는 최소값을 1씩 늘려가면서 순회하느라 시간초과가 발생했다. 그러나 추들의 무게를 더해주면서 최소값을 찾으면 정답을 얻을 수 있다. 아래는 풀이법이다. import sys if __name__ == "__main__": cases = int(sys.stdin.readline()) weight = list(map(int, sys.stdin.readline().split(" "))) weight.sort(reverse=True) num_check = 1 while True: target = nu..

백준 2583번 영역 구하기 문제는 그래프 탐색 문제의 응용으로, 주어진 좌표로 탐색할 수 없는 영역을 표시하는 부분을 구현하는 것이 핵심인 문제이다. 처음에 접근할 때에는 좌표의 오른쪽 끝점을 포함해서 표시했는데, 이렇게 구현하면 훨씬 큰 영역을 잡게된다. 오른쪽 끝 점에서 1을 빼주고 영역을 표시하고 DFS로 탐색하면 쉽게 풀 수 있는 문제였다. DFS로 구현했을 때 PyPy3 환경에서는 재귀깊이 초과로 런타임 에러가 발생할 수 있다. Python3 환경에서 실행하자. import sys sys.setrecursionlimit(10**6) def dfs(row, col, table): if table[row][col] == 1: return 1 table[row][col] = 1 dx = [0, 0,..

문자열을 뒤집는 문제는 프로그래머의 기본이 되어있는지 판단할 수 있는 문제라고 한다. 17413번 단어 뒤집기 2는 단순히 배열을 뒤집는 것에서 넘어 특정 조건에 맞는 문자열만 뒤집는 문제이다. 투 포인터와 큐를 이용해서 풀면 되겠다고 생각했고, 깔끔하지 못한 코딩이였지만 한번에 정답을 맞출 수 있었다. 다른 사람들의 풀이를 보면 문자열을 문자단위로 분해해서 순회하는 방법, 스택을 이용하는 방법들도 있었다. 아래는 소스코드이다. import sys from collections import deque if __name__ == "__main__": q = deque() target_string = sys.stdin.readline().replace("\n", "") idx_start, idx_end = ..

백준 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..