GW LABS

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

깊이 우선 탐색을 복습해보면서 재미있는 제약조건을 해결하는 문제였다. 나를 포함한 많은 사람들이 비가 안오는 경우를 놓쳐 정답률이 낮은 것 같다. 깊이 우선 탐색을 하면서 한 번 함수가 종료될 때마다 카운트 변수를 하나씩 늘려주면 조건에 해당하는 영역을 셀 수 있다. 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..

앞서 포스팅한 이진 트리에서 특별한 속성을 갖고 있는 이진 탐색 트리는 어떤 값을 검색하는 데에 좋은 성능을 보여주는 자료구조이다. 직접 구현해보면서 어려웠던 점이 많았었는데 하나씩 모르던 부분을 알게 되는 기분이다. 그럼 이진 탐색 트리에 대해 자세히 알아보자. 1. Binary Search Tree 이진 탐색 트리는 루트 노드를 기준으로 왼쪽에는 작은 값을, 오른쪽에는 큰 값을 갖는 이진 트리의 한 종류이다. 모든 노드는 자신을 기준으로 왼쪽 자식값은 자신보다 작고, 오른쪽 자식값은 자신보다 큰 구조를 갖고 있다. 2. 검색, 삽입, 삭제 이진 탐색 트리에서 검색을 수행하는 방법은 지난 포스팅의 재귀적 탐색방법을 사용하면 되는데 로직이 하나 추가된다. 검색하고자 하는 값이 현재 노드보다 크다면 오른쪽..

네번째 포스팅은 이진트리이다. 나는 실제로 기술면접과 코딩테스트에서 트리관련 문제를 받았었는데 준비를 더 했었더라면 하는 아쉬움이 있었다. 알고리즘과 자료구조의 기본을 많이 물어보는 회사라면 꼭 숙지해가자! 1. BinaryTree 막상 이진트리에 대해 설명을 작성하려고 할 때 쉽게 설명할 수 있는 정의가 떠오르지 않는다. 내 머리 속에는 정말 '나무처럼 생긴 자료구조'(...)라고 박혀있다. 위키백과에서는 트리 구조를 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조라고 정의하고 있다. 따라서 순환하는 싸이클이 존재할 수 없고 서로 다른 두 노드를 잇는 길이 하나 뿐인 그래프를 트리라고 부른다. 트리에서는 최상위 노드를 루트 노드라고 부르고, 부모에서 자식 노드로만 길이 이어져있다. 이진..