본문 바로가기

전체 글

 (68)
[파이썬 알고리즘] 23. 이진 탐색 트리(BST)를 더 큰 수 합계 트리로 1. 문제 leetcode 1038. Binary Search Tree to Greater Sum Tree 이진 탐색 트리(BST)의 루트가 주어지면, 해당 트리의 값을 트리에서 자기 자신보다 큰 수의 합 + 자기 자신의 값으로 바꾸어라. 2. 풀이 과정 먼저 이진 탐색 트리는 다음과 같은 특성을 가지고 있다. 1. 왼쪽의 서브트리에 노드 값이 자신 이하이다. 2. 오른쪽의 서브트리에 노드 값이 자신 이상이다. 3. 왼쪽과 오른쪽의 서브트리가 모두 이진 탐색 트리이다. 이처럼 이진 탐색 트리는 정렬된 트리라고 할 수 있고, 탐색 시 시간 복잡도가 O(logn)에 불과하다. 주어진 문제에서는 트리를 큰 값부터 차례대로 탐색해야 한다. 따라서 재귀함수를 이용해 오른쪽 노드를 먼저 탐색하고, 자기 자신, 왼쪽..
[파이썬 알고리즘 인터뷰] 22. 배열의 이진 탐색 트리 변환 1. 문제 leetcode 108. Convert Sorted Array to Binary Search Tree 주어진 정렬된 배열을 모든 서브트리의 높이 차이가 2 이상 나지 않는 이진 탐색 트리로 바꾸어라. 2. 해결 방법 재귀 방식의 dfs로 문제를 풀었다. 함수는 인자로 자신과 자식노드들의 값이 될 배열의 값을 전달받고, 노드를 만들어 리턴한다. 먼저 배열의 가운데 위치한 값을 루트노드의 값으로 지정한다. 가운데 값은 몫을 계산하는 // 연산자를 이용해 계산한다. 그리고 그 값 기준으로 왼쪽에 있는 값들의 리스트는 왼쪽노드를 생성할 재귀함수의 인자로, 오른쪽에 있는 값들의 리스트는 오른쪽 노드를 생성할 재귀함수의 인자로 전달한다. 각 함수의 실행이 끝나면 node.left, node.right에 ..
[파이썬 알고리즘] 21. 균형 이진 트리 1. 문제 leetcode 110. Balanced Binary Tree 이진 트리가 높이 균형인지 판단하라. 높이 균형은 모든 노드의 서브 트리 높이 차이가 1이하인 것을 말한다. 2. 내 풀이 재귀 방식의 dfs를 이용했다. dfs 함수가 자기자신부터 시작하는 트리의 높이를 리턴하도록 했다. 리프노드에 도달하면 1을 리턴하고, 노드가 존재하지 않으면 0을 리턴했다. 리프노드를 제외한 다른 노드에서는 자식 노드의 값 중 큰 값에 1을 더해서 리턴했다. 두 자식 노드에서 리턴한 값 차이가 2 이상이 나면 class 변수 answer을 False로 바꿨다. 탐색이 종료되면 answer를 리턴한다. 3. 전체 코드
[파이썬 알고리즘] 20. 이진트리 직렬화 & 역직렬화 1. 문제 Leetcode 297. Serialize and Deserialize Binary Tree 주어진 TreeNode root를 string으로 직렬화시키는 함수 serialize, 다시 TreeNode로 역직렬화시키는 deserialize 함수를 구현하여라. 2. serialize 구현 덱을 이용한 BFS로 탐색한다. root를 넣어 다음에 탐색할 노드들을 넣을 덱을 만들고 덱에 남아있는 노드가 없을 때까지 탐색을 진행한다. 매 탐색 때마다 덱의 왼쪽에서 노드를 하나씩 뺀다. 만약 뺀 노드가 None이 아니라면 node의 값을 result에 추가하고, 자식 노드들을 덱에 추가한다. 탐색이 종료되면 result를 콤마로 구분되는 문자열로 만들어 리턴한다. def serialize(self, ro..
[파이썬 알고리즘 인터뷰] 19. 가장 긴 동일 값의 경로 1. 문제 LeetCode 687. Longest Univalue Path 이진트리 root 가 주어지면 같은 값으로 이어진 경로 중 가장 긴 경로의 길이를 리턴하여라. 2. 풀이 dfs 방식을 이용해서 풀었다. 함수가 노드를 인자로 받으면 현재 노드부터 아래로 이어지는 같은 값을 가진 노드 경로 길이를 state에 저장해 리턴한다. 또한 클래스 변수 longest를 만들고, 경로를 탐색하는 중 가장 긴 경로가 새롭게 등장하면 longest의 값을 업데이트했다. 우선 리프노드가 state가 0을 가지게 하기 위해서 현재 노드가 존재하지 않는다면 -1을 리턴한다. 그리고 왼쪽/오른쪽 자식 노드에 대해 재귀호출을 실행하고, 그 결과로 return된 state 값을 right, left 변수에 저장한다. 모든..
역사란 무엇인가? -<역사의 역사>를 읽고 1. 책 소개 이 책은 헤로도토스의 , 사마천의 , 다이아몬드의 , 하라리의 등 각 시대를 대표하는 역사책을 소개한다. 그리고 이 책들의 관점을 바탕으로 “역사란 무엇인가?”라는 질문에 답을 찾아간다. 2. 역사의 고전, 사마천의 사마천의 는 신화의 시대부터 당시 사마천이 살던 기원전 1세기까지 천년이 넘는 시기를 재구성한 역사책이다. 사마천은 조정의 관리로 일하면서 방대한 서적을 통해 열정적으로 사실을 확인하고 기록했다. 의 특징은 단순히 전체적인 역사만 서술한 것이 아니라, 역사 속 인물에 대한 기록인 을 통해 역사 속의 인물 하나하나를 관찰하는 것이다. 사마천은 이를 통해 반복되는 사건의 패턴을 분석하며 인간 본성의 빛과 그늘, 삶의 의미를 찾으려고 노력했다. 그는 왕의 노여움을 사는 바람에 거세형..
RNN과 LSTM 이해하기 1. RNN의 정의 RNN(Recurrent Neural Networks, 순환신경망)은 음성, 문자 등 순차적 데이터 처리에 적합한 모델이다. 내부의 연결이 순환적이라는 특징을 가지고 있다. 2. RNN의 구조 RNN은 위 그림처럼 입력 벡터 $x$와 출력 벡터 $y$, 은닉층 cell로 구성되어 있다. 여기서 cell은 이전의 값을 기억하려고 하는 메모리 역할을 수행하므로 이를 메모리 셀이라고도 한다. 은닉층의 메모리 셀은 이전 시점 t-1에서 셀에서 나온 값을 현재 시점 t에서 자신의 입력으로 사용하는 재귀적 활동을 하고 있다. 여기서 메모리 셀이 출력층 $y$ 방향으로 보내는 값, 다음 시점의 자기 자신에게 보내는 값은 은닉 상태(hidden state)라고 한다. RNN을 표현할 때는 왼쪽처럼 ..
[파이썬 알고리즘] 18. 순열 1. 문제 leetcode 46. Permutations 서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라. 2. DFS를 이용한 풀이 이 문제는 재귀 dfs로 그래프를 탐색하여 풀 수 있다. 그래프는 []을 루트 노드로, [1,2,3], [2,1,3] 등 각 순열을 리프 노드로 삼고, 중간의 노드는 각 순열이 만들어지는 과정([1,2] 등)으로 가진다. DFS 함수의 인자로는 지금까지 만들어진 순열을 넣는 path, path에 아직 순열에 추가되지 않은 candidates를 준다. 주어진 수를 모두 순열에 사용해서 candidates가 남아있지 않다면, 지금까지 만든 순열인 path를 결과에 추가한다. 만약 순열 path에 추가할 candidates가 남아 있다면 남아있는 숫자를 모두 넣어서 DF..

티스토리툴바