컴공생의 개인공부일지

문제 : 문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라. 예제: Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"] 솔루션: 투 포인터를 이용한 스왑 💡 투 포인터? 단어 그대로 2개의 포인터를 이용해 범위를 조정해가며 풀이하는 방식 def reverseString(self, s : List[str]) -> None: left, right = 0 , len(s) - 1 while left < right: s[left], s[right] = s[right], s[left..

문제 : 주어진 문자열이 팰린드롬인지 확인, 대소문자 구분하지 않으며, 영문자와 숫자만을 대상으로 한다. 예제: Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome. Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome. 💡 palindrome(팰린드롬)? 앞 뒤가 똑같은 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장 솔루션: 리스트로 변환 # 리스트 활용 시간 복잡도 : O(n²) def isPalindrome(self, s:str) -> bool: strs = ..

B - 트리란? 이진트리와는 반대로 자식 노드가 2개 이상인 트리 B - 트리의 조건 모든 단말노드는 동일한 높이 각 내부노드의 자식노드는 M/2 이상, M 이하 루트의 자식 수는 2개 이상 노드의 키가 x개라면 자식의 수는 x+1개 자료는 정렬된 상태로 저장 B-Tree의 장점 포인터의 접근 방식이 적어서 속도 이슈가 적음 B-Tree는 Balanced Tree로 트리내에 모든 데이터가 정렬된 상태를 유지하기 때문에 등호(=)연산 뿐 아니라 부등호()연산도 가능하다. 데이터의 삽입과 삭제, 탐색의 시간복잡도가 O(logN)으로 동일 B-Tree는 삽입과 삭제 후에도 균형 트리 유지로 균등한 응답 속도를 보장 B-Tree의 단점 삽입과 삭제 시 트리의 균형을 유지하기 위해 복잡한 연산을 수행 순차탐색시 ..

트리를 이용한 DB 설계의 장 / 단점 및 트리의 한계 해결 DB를 설계할 때 주로 사용되는 자료구조는 B-Tree이다. [ ] 다른 자료구조를 DB로 사용 할 수 없는 이유 1. 해시 테이블의 경우 해시 테이블은 단 하나의 데이터를 탐색하는데 O(1) (최악의 경우 O(N)이지만 평균적으로 O(1))의 시간복잡도를 가지만, DB에서는 등호(=) 뿐만 아니라 부등호()도 사용 → O(1)의 시간복잡도를 보장 할 수 없고, 비효율적 2. 레드-블랙트리의 경우 레드-블랙트리는 하나의 노드에 하나의 요소를 저장하지만, B - 트리의 경우 하나의 노드에 배열처럼 여러개의 데이터 요소를 저장 → 같은 공간의 노드를 참조 포인터로 접근 할 필요가 없음 → 동일 메모리에서 작동 → 두 트리 모두 O(logN)의 시간..

레드-블랙 트리란? 각각의 노드가 레드나 블랙인 색상 속성을 가지고 있는 이진 탐색 트리 이진 탐색 트리가 가지는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한 레드-블랙 트리이다. 노드는 레드 또는 블랙 루트 노드는 블랙 모든 리프 노드는 블랙 레드 노드의 자식은 모두 블랙 → 루트부터 리프 노드까지의 경로에 레드가 연이어 올 수 없다 어떤 노드에서 리프 노드까지의 모든 경로에는 같은 수의 블랙 노드가 존재 위 조건으로부터, 루트로부터 가장 긴 경로가 가장 짧은 경로의 길이의 두 배를 넘지 않는다. 이를 개략적으로 균형이 잡혀 있다(roughly balanced)고 한다. → 최악의 시간복잡도가 트리의 높이(깊이)에 따라 결정되므로 보통의 이진트리보다 효율적 💡 4와 5번째 규칙에 의해 ..

AVL 트리란? 스스로 균형을 잡는 이진 탐색 트리 한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 사용 → 스스로 균형을 잡아 편향을 방지 → 트리의 높이가 h일때 시간 복잡도는 O(h) AVL트리의 특징 이진 트리의 속성을 가진다 왼쪽, 오른쪽 서브 트리의 높이 차가 최대 1이다 높이 차이가 1보다 커지면 회전을 통해 균형을 잡는다 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)이다 Balance Factor(BF) 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값 💡 Balance Factor BF(K) = left(K) - right(K) BF = 1 → 왼쪽 서브트리가 높음 BF = 0 → 양쪽의 높이가 같음 BF ..

트리란? 트리라는 용어는 아서 케일리의 논문에서 처음으로 사용 “A theorem on trees”. 《The Quarterly Journal of Pure and Applied Mathematics》 스택과 큐, 데크 등의 선형 자료구조로는 표현할 수 없는 자료를 표현하기 위해 만들어진 것 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조 즉, 부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조를 말한다. 💡 부모노드 : 루트 노드 방향으로 직접 연결된 노드 자식노드 : 루트 노드 반대방향으로 직접 연결된 노드 루트노드 : 트리에서 부모가 없는 최상위 노드, 트리의 시작점 트리의 종류 이진트리 이진트리 이진탐색트리 완전이진트리 ..

탐욕 알고리즘으로 최적해가 보장되지 않는 예시 탐욕 알고리즘은 대부분의 경우에서 최적해를 보장하지 못한다. 탐욕 알고리즘으로 최적해가 보장되는 예시 분할 가능한 배낭 문제 Prim 알고리즘 Kruskal 알고리즘 Dijkstra 알고리즘 회의실 배정 문제 허프만 암호화 알고리즘 동전 거스름돈 문제 문제 : 100원, 500원, 1000원이 있을 때, 1400원을 교환할 수 있는 최소 동전 개수를 구하라. 최적해인 경우 100원 : 100 x 14 = 14개 500원 : 500 x 2 + 100 x 4 = 6개 1000원 : 1000 x 1 + 100 x 4 = 5개 따라서 최소 동전 개수는 5개이다. 최적해가 아닌 경우 동전이 100원, 700원, 1000원일 경우 위와 같은 방법으로 실행 할 시 100..

매트로이드란? 탐욕 알고리즘이 최적 해를 가려낼 수 있는 경우인지를 판별할 수 있게 하며, 독립성이라는 성질을 만족하는 수학적 공간 단, Greedy한 방법을 적용할 수 있는 모든 경우를 판별해낼 수 있는 것은 아니라서, 어떤 문제의 공간이 매트로이드 구조를 이루면, 탐욕 알고리즘이 최적해를 도출해낼 수 있지만, 탐욕 알고리즘이 최적해를 도출할 수 있는 모든 문제가 매트로이드 구조를 띄는 것은 아니다. 탐욕 알고리즘은 꼭 최적해가 아니여도 최적해에 근사한 값을 찾아낼 수 있다는 점에서 유용한 알고리즘이다. 💡 어떤 유한 집합 n의 부분 집합들의 집합인 𝐼(즉, 𝐼⊆ 2ⁿ)가 아래 성질을 만족하면 집합 𝐼는 Matroid이다. 매트로이드의 특성 상속성(Heredity) A∈I이고, B⊆A이면 B∈I이다. ..

Prim 알고리즘이란? 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법 Prim 알고리즘의 동작 방법 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. (즉, 가장 낮은 가중치를 먼저 선택한다.) 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다. Prim 알고리즘을 이용한 MST(최소 신장 트리)를 만드는 과정 정점 선택을 기반으로 하는 알고리즘 이전 단계에서 만들어진 신장 트리를 확장하는 방법 Prim 알고리즘의 시간 복잡도 for 반복문이 정점의 수 n만큼 반복하고, 내부 반복은 n번 반복(Prim의 경우 O(n²), Kru..