컴공생의 개인공부일지

1. 파이썬의 변수명 네이밍 컨벤션은 스네이크 케이스를 따른다. Ex.) snake_case : int = 1 2. 타입 힌트, 리턴값 등 명시적으로 선언 시 가독성이 좋아지고 버그 발생 확률을 줄일 수 있다. 또한 mypy를 사용해서 타입 힌트에 오류가 없는지 확인 가능하다. Ex.) def fn(a : int) -> bool: $pip install mypy를 통해 설치 가능 3. 리스트 컴프리헨션 Ex.) 홀수인 경우 2를 곱해 출력하는 리스트 컴프리헨션 [n * 2 for n in range(1, 10 + 1) if n % 2 == 1] 4. 제네레이터 루프의 반복 동작을 제어할 수 있는 루틴의 형태 yield 구문 사용 시 제네레이터 리턴 생성해두고 필요할 때 언제든지 숫자를 만들어 낼 수 있음..

문제: 금지된 단어를 제외한 가장 흔하게 등장하는 단어를 출력하라. 대소문자 구분을 하지 않으며, 구두점(마침표, 쉼표) 또한 무시한다. 예제: Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"] Output: "ball" Explanation: "hit" occurs 3 times, but it is a banned word. "ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. Note that words in the paragraph are not..

문제: 로그를 재정렬하라 . 기준은 다음과 같다 1. 로그의 가장 앞 부분은 식별자 2. 문자로 구성된 로그가 숫자 로그보다 앞에 온다. 3. 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일한 경우 식별자 순으로 한다. 4. 숫자 로그는 입력 순서대로 한다. 예제: Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"] Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"] Explanation: The letter-log contents are all different, so their orde..

문제 : 문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라. 예제: 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》 스택과 큐, 데크 등의 선형 자료구조로는 표현할 수 없는 자료를 표현하기 위해 만들어진 것 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조 즉, 부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조를 말한다. 💡 부모노드 : 루트 노드 방향으로 직접 연결된 노드 자식노드 : 루트 노드 반대방향으로 직접 연결된 노드 루트노드 : 트리에서 부모가 없는 최상위 노드, 트리의 시작점 트리의 종류 이진트리 이진트리 이진탐색트리 완전이진트리 ..