GW LABS

깊이 우선 탐색을 복습해보면서 재미있는 제약조건을 해결하는 문제였다. 나를 포함한 많은 사람들이 비가 안오는 경우를 놓쳐 정답률이 낮은 것 같다. 깊이 우선 탐색을 하면서 한 번 함수가 종료될 때마다 카운트 변수를 하나씩 늘려주면 조건에 해당하는 영역을 셀 수 있다. 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 막상 이진트리에 대해 설명을 작성하려고 할 때 쉽게 설명할 수 있는 정의가 떠오르지 않는다. 내 머리 속에는 정말 '나무처럼 생긴 자료구조'(...)라고 박혀있다. 위키백과에서는 트리 구조를 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조라고 정의하고 있다. 따라서 순환하는 싸이클이 존재할 수 없고 서로 다른 두 노드를 잇는 길이 하나 뿐인 그래프를 트리라고 부른다. 트리에서는 최상위 노드를 루트 노드라고 부르고, 부모에서 자식 노드로만 길이 이어져있다. 이진..

이 문제를 두 번 풀면서 들었던 생각은 항상 내 접근방식이 규칙을 포착하고, 그 규칙을 코드로 구현하는 방식으로만 전개된다는 점이었다. 사실 입력이 크지 않다면 컴퓨팅 파워를 믿고 모든 경우의 수를 돌려보면 아주 간단한 방식으로 풀 수 있는 문제들이 많다. 항상 이 사실을 머리 속에 깊숙히 자리잡게 하도록 연습해야겠다. import sys if __name__ == "__main__": target = int(sys.stdin.readline()) index = 0 result = 0 for i in range(999999999): if "666" in str(i) : index += 1 if index == target: result = i break print(result)

그래프와 DFS, 위상정렬을 공부해볼 수 있는 아주 좋은 문제였다. 문제의 조건은 어떤 과목을 수강할 때 선수과목을 먼저 듣고 들어야한다. 주어진 강의 목록들을 모두 수강할 수 있다면 True를, 선수과목에 이상이 있어서 모두 수강할 수 없다면 False를 리턴하면 되는 문제이다. 접근방법은 우선 인접리스트 형태의 그래프를 만들고 깊이 우선 탐색을 하면서 위상정렬을 수행하는 것이다. 탐색 함수가 종료될 때마다 현재 위치를 기록하고, 탐색이 끝났다면 기록한 배열을 뒤집어주면 위상정렬이 수행된다. 위상정렬 배열을 보면서 수강목록들을 다시 보면서 이상이 있다면 False를 리턴하면 해결할 수 있다. from collections import deque class Solution: def canFinish(se..

세 번째 C++ 세 번째 포스팅은 해시맵이다. 해시맵은 실무에서도 다양하게 응용되는 친숙한 자료구조이다. 어떤 내부구조를 갖고 있는지 함께 알아보자! 1. Hashmap (해시 맵, 해시 테이블) 해시맵은 키를 통해 어떤 값을 찾기 위한 자료구조이다. 다양한 형태로 응용할 수 있고, 알고리즘 문제 뿐만 아니라 실무에서도 유용하게 사용한다. 해시맵은 읽기, 쓰기, 삭제 모두 평균적으로 O(1)에 수행할 수 있다. 어떻게 이런 시간복잡도가 가능할까? 2. Hasing 해시맵을 이해하기 위해선 먼저 해싱을 알아야한다. 해싱은 해쉬함수를 이용해서 키를 숫자로 변환하는 과정이다. 이렇게 생성된 키는 해쉬맵 내부에 있는 자료구조 방 번호가 된다. 얻어진 방 번호를 통해 값을 저장하고, 찾고, 삭제하면 되는 것이다...

LeetCode에 "Top 100 liked" 리스트에 수록되어 있는 문제이다. DFS 문제로 분류되는데 국내 기준으로는 구현 문제로 분류될 것 같다. 문제 풀이에 엄청난 시간이 들었는데, 그 만큼 구현 문제에 대한 연습과 대비가 안되어 있다는 걸 느꼈다. 알고리즘을 설계하기 전에 재귀적으로 접근하면 풀이가 가능할 것으로 예상하고, 재귀적으로 설계를 해나가면서 어려웠던 점은 문자열의 인덱스를 적절히 잘라주는 계산과 예외에 대한 처리였다. 다음에 이 문제를 복습할 때에는 재귀적 접근 뿐만 아니라 스택을 사용해서 접근하는 방법도 고려해봐야겠다. class Solution: def decodeString(self, s: str) -> str: return self.decode(s) def decode(self..

Palindrome string은 뒤집었을 때에도 같은 순서를 갖고 있는 문자열이다. 우리말로는 '회문'이라고 한다. palindrome을 가지고 다양한 문제를 만들어낼 수 있는데, 문자열 뿐만 아니라 연결리스트 등 다양한 자료구조의 기본지식을 판단할 수 있는 문제이다. 해당 문제는 부분 문자열에서 palindrome을 찾는 문제였다. class Solution: def countSubstrings(self, s: str) -> int: result = 0 for length in range(1, len(s) + 1): idx_start = 0 idx_end = length while idx_end