소피it블로그

https://leetcode.com/problems/daily-temperatures/ Daily Temperatures - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 자체는 그렇게 어렵지는 않다. 인덱스 값들을 저장해둘 필요가 있다는 점만 파악하면 스택으로 쉽게 구현이 가능하다. 그런데 enumerate로 값과 함께 저장하려고 하니 시간 제한에 걸린 반면, 인덱스만 저장했을 때는 잘 풀렸는데 도대체 이유가 뭔지 아직도 잘 모르겠다. enumerate..

자료 출처: https://youtu.be/aOhhNFTIeFI 1. 서로소 집합 자료구조 공통 원소가 없는 두 집합으로, Union Find 자료구조라고도 한다. 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합침 찾기(Find): 특정 원소가 속한 집합이 어느 집합인지 알려줌 2. 여러 개의 합치기 연산 합집합(Union) 연산을 확인하고 서로 연결된 두 노드 A, B를 확인한다. A, B의 루트 노드인 A', B'를 각각 찾는다. A'를 B'의 부모 노드로 설정한다. 모든 합집합 연산이 처리될 때까지 위의 과정을 반복한다. 3. 무방향 그래프 내에서 사이클을 판별하기 위한 용도 (방향 그래프에서는 DFS를 이용) 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다 루트 ..

자료 출처: https://youtu.be/i5yHkP1jQmo 1. 트리 계층적인 구조를 표현할 때 사용할 수 있는 자료구조로, 다음과 같은 요소를 갖는다. 트리의 크기가 n일 때 전체 간선의 수는 n-1 개이다. 루트 노드 (root node) 단말 노드 (leaf node) 크기 (size): 트리에 포함된 모든 노드의 개수 깊이 (depth): 루트 노드부터의 거리 높이 (height): 깊이 중 최댓값 차수 (degree): 각 노드의 자식방향의 간선의 개수 2. 이진 탐색 트리 (Binary Search Tree) 이진 탐색을 쉽게 할 수 있게 해주는 트리로, 다음을 만족한다. 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 데이터의 조회 과정은 다음과 같다. 루트 노드부터 방문하여 탐색을..

자료 출처: https://youtu.be/AjFlp951nz0 1. 우선순위 큐 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 단순히 리스트를 이용하여 구현하는 방식: 삽입시 O(1), 삭제시 O(N)의 시간복잡도 힙(heap) 자료구조를 이용하여 구현하는 방식: 삽입, 삭제시 각각 O(logN)의 시간복잡도 2. 힙 (Heap) 완전 이진 트리의 일종인 자료구조로, 항상 루트 노드를 먼저 제거한다. 최소 힙 (Min Heap) 루트 노드가 가장 작은 값을 가짐 값이 작은 데이터가 우선적으로 제거됨 따라서 최소 힙에 넣었다 빼면 오름차순으로 정렬됨(작은 데이터부터 제거되므로) 최대 힙 (Max Heap) 루트 노드가 가장 큰 값을 가짐 값이 큰 데이터가 우선적으로 제거됨 따라서 최대 힙에 ..

https://leetcode.com/problems/add-two-numbers/ Add Two Numbers - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 아주 간단한 링크드 리스트 문제인데, 나는 링크드 리스트에 대한 개념 정도만 있지 실제로 구현해서 문제풀이에 사용해본 경험은 거의 없었기 때문에 이 문제로도 꽤나 많은 오류를 거쳤다. 애초에 문제 자체는 연결 리스트를 숫자로 바꿔서 더한 후 다시 연결 리스트로 바꾸라는 의도는 아니었던 것 같으나, 나는..

https://leetcode.com/problems/valid-parentheses/ Valid Parentheses - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 스택 클래스를 따로 구현하여 pop, push 메서드를 구현해줘도 되나 편의상 솔루션 클래스 안에 리스트 형식의 스택을 구현했다. class Solution: def isValid(self, s: str) -> bool: stack = [] for c in s: if c == "[" or c =..