본문 바로가기

전체보기

 (180)
AVL 트리 (Adelson-Velsky and Landis Tree) 이진 탐색 트리의 문제점 상위 노드를 기준으로 작으면 왼쪽, 크면 오른쪽으로 보내기 때문에 들어오는 순서에 따라 한 방향으로 치우칠 수 있다. 우리는 이것을 치우친 이진 트리(Skewed Binary Tree)라고 부른다. AVL 트리란? 모든 리프 노드들의 레벨 차이는 1 이하 트리의 높이는 logN 삽입, 삭제, 탐색 연산에서 최악의 경우에도 O(logN)의 시간 복잡도를 보장한다. Balance Factor 각 노드는 아래 공식으로 balance factor 수치를 계산해 트리의 균형 유무를 판단한다. balance factor = 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이 balance factor > 1: 왼쪽 서브 트리에서 불균형 발생 balance factor < -1: 오른쪽 서브 트..
이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리란 이진 트리에서 데이터의 크기를 판단해 탐색하는 트리 부모 노드를 기준으로 작은 값은 왼쪽 서브 트리로, 큰 값은 오른쪽 서브 트리로 배치된다. 따라서 맨 왼쪽 리프 노드는 트리의 최솟값이고, 맨 오른쪽 리프 노드는 트리의 최댓값이다. 이를 이용해 값을 찾을 때 대소 비교를 통해 탐색 방향을 정한다. 매 탐색마다 경우의 수가 절반씩 줄어들기 때문에 삽입, 삭제, 탐색에서 logN의 시간 복잡도를 가진다. 이진 탐색 트리의 문제 오름차순 또는 내림차순 된 리스트를 순차적으로 저장하는 경우 트리의 방향이 한쪽으로 치우치는 편향 이진 트리가 된다. 이경우, logN의 시간 복잡도가 아닌 O(N)의 시간 복잡도가 발생한다. 노드 정의 private static class Node { int da..
트리, 이진트리 트리란? 노드들이 연결된 비선형 자료구조. 루트 노드라 불리는 최상위 노드에서 시작해 여러 하위 노드로 확장되는 계측정 구조. 한 노드가 여러 노드와 연결돼 있다. 트리는 사이클이 존재하지 않는다. 즉, 탐색을 수행할 때 시작 노드와 종료 노드가 동일한 경로가 없다. 트리의 용어 노드(Node): 트리의 기본 단위 루트 노드(Root Node): 트리의 최상위 노드. 트리는 하나의 루트 노드를 가진다. 부모 노드(Parent Node): 자식 노드를 가지는 노드 자식 노드(Childe Node): 특정 노드의 하위 계층에 있는 노드 리프 노드(Leaf Node): 자식 노드를 가지지 않는 노드 즉, 최말단 노드 형제 노드(Sibling Node): 같은 부모 노드를 둔 노드들 레벨(Level): 지정된 ..
백준[1113] 수영장 만들기 (Python3) 물을 채울 수 있는 조건은 다음과 같다. 현재 높이를 A라 할 때 높이 A와 이어지는 영역은 테두리에 닿으면 안 된다. (물이 땅으로 흐름) 상하좌우의 높이가 A보다 작으면 안 된다. (작은 쪽 높이가 테두리로 이어짐) 한번 채워진 영역은 다시 한번 더 채워질 수 있기에 (예제 2번 기준) 높이가 낮은 곳부터 탐색을 해야 한다고 생각했다. 코드의 흐름은 다음과 같다. 찾을 높이를 1 ~ 9까지 정하고 이 높이를 wall이라 한다. (main 함수) wall 값과 동일한 값을 가진 가진 좌표들을 구한다. (findWall 함수) 만약 테두리와 이어지면 무효 상하좌우로 탐색한 높이의 최솟값이 wall보다 낮으면 무효 wall 보다 큰 값이 없다면, 해당 영역에 물을 채울 수 없으니 무효 영역을 구하면 상하좌..
프로그래머스 - 인사고과 값을 여러 쌍을 준 뒤, 특정한 인덱스가 몇 번째로 위치하는지에 대한 문제를 프로그래머스에서 몇 번 본듯한 기억이 있었다. 지금 정리해두면 나중에 유용하다 생각해 글을 쓰게 됐다. 완전 탐색 1. 태도, 동료 점수 모두 자신보다 큰 사원이 있을 경우 해당 사원을 제외한다. 2. 각 사원들의 점수 총합을 구한 뒤, 점수를 기준으로 내림차순 정렬을 해 원호가 몇 번째로 큰지 본다. 만약, 원호가 제외됐을 경우 -1을 반환한다. 시간복잡도 계산 1번의 경우 모든 사원을 봐야 하기 때문에 N^2의 시간 복잡도 발생 2번의 경우 정렬에 Nlog(N), 원호의 위치를 찾는 과정에서 N의 시간 복잡도 발생 총 시간 복잡도는 N^2 + Nlog(N) + N으로, N = 100,000이기에 시간 초과가 발생한다. 틀린 ..
객체지향의 사실과 오해 책을 읽은 이유 토이 프로젝트를 하면서 고질적인 문제가 있었는데 어느 정도 구현이 끝나면 의미 없는 리팩토링 관련 커밋들만 계속 올라가는 것이었다. 어제는 이게 명쾌한 해답 같았지만, 다음 날 다시 보니 여전히 문제가 있는 코드였고, 이러다 보니 리팩토링만 하다 프로젝트에 흥미를 잃어 레포를 지우고 다른 프로젝트를 시작하는 일들이 빈번히 발생했다. 이렇듯 설계에서 계속 문제가 발생했기 때문에, 객체 설계 관련 책을 보면 어떨까 싶었다. 그래서 본 책이 객체지향의 사실과 오해란 책이었다. 책을 읽는 과정에서 어느 부분에서 설계가 꼬이게 됐는지 유추할 수 있었다. 모든 부분이 중요했지만, 그 중 나한테 있어 필요한 부분들에 대해 우선적으로 정리를 했다. 역할, 책임, 협력 이 책에서 가장 강조하는 3가지 단..
백준[1981] 배열에서 이동 (Python3) 완전 탐색 배열을 모두 순회하는데 O(100 * 100) 이 필요하다. 최대 - 최소의 경우, 차이가 1이라 할 때, 차이가 1이 되는 최대, 최소의 쌍은 (1, 2), (2, 3), (3, 4), ... (199, 200) 식이다. 차이가 최대 200까지 발생하니, 쌍을 구하는 것에 대한 시간 복잡도는 (199 + 198 + 197 + ... + 0) = 약 20,000 정도 된다. 총 시간 복잡도는 O(100^2) * O(199 + 198 + ... + 0) = 2억으로 시간 초과가 발생한다. 완전 탐색 최적화 배열을 일부만 탐색할 수는 없으니, 쌍을 구하는 과정에서 최적화를 수행해야 한다. 하지만, 어떤 최대, 최소의 차이 A를 구하기 위해선, 이를 만족하는 모든 경우를 확인해야만 한다. 따라서, ..
백준[1863] 스카이라인 (Python3) 어떤 것을 pop 할지를 잘못 생각해서 삽질한 문제 스택에서 없애야 할 것 건물이 더 이상 확장할 수 없는 경우, pop 한다. 입력으로 들어온 Y가 스택의 상단 T보다 작다면, (Y < stack.top()) 높이 T를 가지는 건물의 범위는 거기서 끝나기 때문에, 더 이상 스택에 있을 필요가 없어진다. 스택에 넣지 말아야 할 상황 건물의 영역이 이어지는 경우, 스택에 push 하지 않는다. (Y == stack.top()) 즉, 입력으로 들어온 Y가 스택의 상단 T와 같다면 스택에 넣지 않는다. 고층 건물에 대한 정보가 삭제된 후, 바뀐 스택의 상단 T가 N과 높이가 같다면, 높이 N의 건물이 계속되는 형태기 때문에, 따로 카운팅을 할 필요가 없어진다. 스택에 넣어야 하는 상황 스택이 비어있을 때와, ..

티스토리툴바