GW LABS

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

이번 포스팅에서는 큐를 연결리스트를 이용해서 손쉽게 구현하는 방법을 알아보려고 한다. 큐는 그래프 탐색 방법 중 넓이 우선 탐색에서도 주로 사용되는 자료구조로 꼭 알아둬야 할 자료구조이다. 스택과 마찬가지로 내용은 쉬우나, 큐를 이용해서 문제를 풀이하는 방법을 떠올리는 연습을 해야한다. 1. Queue 큐는 이전 포스팅과 같은 선형자료구조로 First-in, First-out 형태를 지니고 있다. 큐는 일상생활에서도 많이 볼 수 있는 형태이다. 매표소에서 표를 받기위해 기다리는 사람들도 큐 형태이다. 큐도 스택처럼 연결리스트를 이용하면 매우 쉽게 구현할 수 있다. 메모리를 아끼는 방법으로 배열을 이용해서 환형으로 구성하는 방법도 있다. 2. Queue의 기능들 큐 자료구조를 지원하는 대부분의 언어들은 공..

C++로 구현하는 자료구조 6번째 포스팅이다. 스택은 앞서 구현한 동적배열, 연결리스트를 이용하면 간결하게 구현할 수 있다. 동작원리는 간단하나, 알고리즘 문제들에서는 스택을 사용해서 해결해야겠다는 아이디어를 떠올리기가 어렵다. 이번 포스팅에서 스택을 이해하고 활용할 수 있도록 노력해보자. 1. Stack 스택은 First in, Last out 형태의 선형 자료구조이다. 스택의 경우 구현은 쉬운 편이다. 앞서 구현한 연결리스트 혹은 동적배열 등을 이용해서 구현이 가능하다. 연결리스트를 이용해 구현할 때에는 맨 뒤의 노드에 추가, 삭제만 해주는 형식으로 구현하면 된다. 동적배열의 경우에도 가장 뒤의 요소에 추가, 삭제하는 형식으로 접근하면 손쉽게 구현할 수 있다. 2. Stack의 기능들 스택 자료구조를..

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

문제 조건을 제대로 파악하지 않고 우선순위 큐이겠거니 접근한 결과, 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__":..