GW LABS

문자열을 뒤집는 문제는 프로그래머의 기본이 되어있는지 판단할 수 있는 문제라고 한다. 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..

백준 단계별 문제란 백트래킹에 수록되어 있는 문제이다. 재귀함수를 이용해서 백트래킹을 해나가면 풀 수 있다. 많은 분들이 재귀함수, 그래프 탐색 등을 이용해서 푼 것 같다. 그러나 파이썬을 이용하면 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..

이번 포스팅에서는 트라이에 대해 알아보려고 한다. 생소한 이름 때문에 어떤 역사가 있는 지 찾아봤더니 재미있는 일화가 있었다. 트라이는 René de la Briandais에 의해 개념이 소개되고, Edward Fredkin에 의해 reTRIEval(검색)이라는 단어에서 trie라고 명명되었다. 처음 발음할 때에는 트리라고 불러졌는데, 트리(tree)와 구분하기 위해서 트라이로 발음하기 시작했다고 한다. 그럼 어떤 자료구조인지 자세히 알아보자. 1. Trie 트라이는 문자열을 빠르게 검색하기 위해 고안되었다. 기본적인 구조는 트리와 비슷한데 차이점은 노드에 문자열을 문자단위로 분해하여 저장한다는 점이다. 위의 그림과 같이 한 글자씩 트리를 따라가며 검색을 하는 구조이다. 한 글자씩 저장하지 않고 트라이의..

이번 포스팅에서는 힙 자료구조를 알아보려고 한다. 힙은 우선순위 큐로도 활용할 수 있으며, 정렬에도 사용할 수 있다. 힙에 대한 이해도가 낮아서 geeksforgeeks의 구현 예제를 많이 참고했다. 어떤 자료구조인지 함께 알아보자! 1. Heap 힙은 완전이진트리(complete binary tree)를 기본으로 한 트리형 자료구조이다. 최댓값과 최소값을 빠르게 찾아내기 위해 고안되었으며, 종류에 따라 다음과 같은 속성을 지닌다. 최소 힙이라면? 자식 노드의 값은 부모 노드의 값보다 크다. 최대 힙이라면? 자식 노드의 값은 부모 노드의 값보다 작다. 이런 속성을 만족하면 힙의 루트는 최대 혹은 최소값이 된다. 2. Heap 구현방법 처음 힙을 구현하려고 했을 때, 이번 포스팅에서 구현했던 이진탐색트리와..

그래프 탐색문제에서는 어떤 방식으로 탐색해야 문제를 빠르게 풀 수 있을지 판단하는 것이 문제의 관건이다. 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..