Computer Science55 2️⃣Bipartite Graph intro 2️⃣ Bipartite Graph(이분 그래프)란, 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로 칠할 수 있는 graph를 뜻한다. 2️⃣ a graph in which the vertices can be divided into two disjoint sets, such that no two vertices within the same set are adjacent. In other words, it is a graph in which every edge connects a vertex of one set to a vertex of the other set. : 즉, graph 내의 모든 간선은 두 가지 다른 색깔의 정점으로 무조건 연결되어 있어야 하고, 반대로 말하.. Computer Science/Algorithms 2023. 12. 21. 🌳 Binary Tree 🌳 theory 🌳 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 : Binary Tree is defined as a tree data structure where each node has at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. 🌳 트리 관련 용어 ① root node: 부모가 없는 최상위 노드 ② leaf node: 자식이 없는 노드 ③ size: 트리에 포함된 모든 노드의 개수 ④ depth: 특정 노드에서 루트 노드부터의 거리(즉 위 1번 노드의 깊이는 0, 2번 노드의 깊이는 1) ⑤ h.. Computer Science/Data Structures 2023. 12. 19. Optimal Page Replacement Algorithm intro ▶ 운영체제 메인 메모리에 존재하지 않는 새로운 page가 있을 때 page fault가 발생. ▶ page fault가 발생할 때, existing page와 newly needed page replacement 진행 ▶ 이 때, page fault의 횟수를 최소화한 알고리즘이 Optimal Page Replacement Algorithm ▶ page hit & fault algorithm ▶ "when page fault, pages are replaced which would not be used for the longest duration of time in the future" ▶ ① referred page가 이미 main memory에 존재한다면, page hit count 1 증.. Computer Science/Algorithms 2023. 10. 18. 🚡Next Permutation / Previous Permutation Intro 1) Next Permutation ★ Combinatorics 조합론에서 흔히 볼 수 있는 대표 알고리즘 중 하나로, print the lexicographically next greater permutation of the given array. If there does not exist any greater permutation, then print the lexicographically smallest permutation of the given array. ★ 배열에 여러 수가 정렬되어 있다면, 사전 순으로 그 다음 수, 즉 현재 수보다 크되 큰 수 중 가장 작은 수를 구하는 알고리즘. 현재 수보다 큰 수가 존재하지 않는다면 permutation 중 가장 작은 수를 구함. ★ 예를 들.. Computer Science/Algorithms 2023. 8. 16. 👐 Primality Test ※ 소수(Prime Number) = 1과 자기 자신으로만 나누어지는 수 ※ 1. 약수의 개수 👐 ① 2~(N-1) 까지 모두 돌렸을 때 나머지가 0이 아니다 ② 약수의 개수가 2 def isPrime1(N): for i in range(2,N): if N%i == 0: return False return True def isPrime2(N): cnt = 0 for i in range(1,N+1): if N%i == 0: cnt += 1 if cnt == 2: return True else: return False → 위 두 풀이는 모두 O(N) 모든 범위를 돌며 일일이 확인 2. O(N^(1/2)) 👐 ③ 탐색 범위 N^(1/2)으로 줄이기 → 위와 동일하되 시간복잡도 O(N^(1/2)). 나누어지는 .. Computer Science/Algorithms 2023. 8. 8. set() & dict() - 집합과 맵 🏄🏽♂️ 대표 자료구조 '집합'과 '맵'이 있다. 두 개의 자료구조는 매우 효율적인 자료구조로 특별히 python에서 어떻게 코드로 구현하고, 관련 여러 연산 기능 및 time complexity까지 자세히 알아보자! 🏄🏽♂️ 시간복잡도 계산 상 효율적인 코드를 작성하기 위해 집합과 맵이라는 자료구조를 활용하는 경우가 많다(특히 어려운 PS 문제!) 각 자료구조의 특징을 정확히 알아보자 Sets overview "unordered collection of data types that is iterable, mutable and has no duplicate elements. The order of elements in a set is undefined though it may consist of va.. Computer Science/Data Structures 2023. 8. 3. 🪴Insertion Sort orders ★ 앞쪽에 있는 원소들이 이미 정렬되어 있다고 가정하고, 뒤 쪽에 있는 원소를 앞쪽에 있는 원소들 중에 들어갈 적절한 위치를 판단하고 삽입 ★ ① 정렬할 데이터 준비 (오름차순 가정) → 맨 왼쪽 첫번째 데이터 7은 그 자체로 정렬이 되었다고 판단하고, 두번째 데이터인 5가 7의 왼쪽으로 갈지, 오른쪽으로 갈지 판단(=5가 왼쪽의 어느 파트에 들어갈 지 판단) 7 5 9 0 3 1 6 2 4 8 ② 오름차순을 가정하였으므로 5가 7의 왼쪽으로 이동하겠다고 판단! 5 7 9 0 3 1 6 2 4 8 ③ 이어서 9가 어떤 위치로 들어갈 지 판단 → 9의 경우는 5의 왼쪽으로 들어갈 지, 5와 7사이에 들어갈 지, 아니면 7 오른쪽으로 들어갈 지 들어갈 수 있는 3개의 후보 중에서 판단 → 맨 왼.. Computer Science/Algorithms 2023. 7. 28. 🥭Selection Sort orders ★ 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꿈 (오름차순 정렬 가정) ★ ① 정렬할 데이터 준비 (7 5 9 0 3 1 6 2 4 8) ② 처리되지 않은 데이터(7부터 8 전체) 중 가장 작은 0을 선택해 맨 앞의 7과 바꾼다. 7 5 9 0 3 1 6 2 4 8 (0과 7을 바꾼다) 0 (5 9 7 3 1 6 2 4 8) ③ 처리되지 않은 데이터(위 괄호 5부터 8) 중 가장 작은 1을 선택해 가장 앞의 5와 바꾼다. 0 5 9 7 3 1 6 2 4 8 (1과 5를 바꾼다) 0 1 (9 7 3 5 6 2 4 8) ④ 처리되지 않은 데이터가 맨 오른쪽 1개가 있을 때까지 반복한다(맨 마지막 1개의 데이터는 자동 정렬됨) 0 1 2 3 4 5 6 7 8.. Computer Science/Algorithms 2023. 7. 26. Divide&Conquer(DAC) intro> 🍻 분할(Divide)하고 정복(Conquer)하는 이 알고리즘은 문제를 풀 때의 접근 방식으로 분할 → 정복 → 결합 크게 세 단계로 진행된다. 🍻 ① 분할(Divide): 주어진 문제를 더 작은 여러 개의 sub-problem으로 분할한다. ② 정복(Conquer): 재귀적으로 sub-problem들을 각각 해결한다. ③ 결합(Combine): 각각의 sub-problem 해결 결과를 묶어 전체 문제의 최종 솔루션을 도출! 🍻 divide & conquer 접근법을 사용하는 대표 알고리즘 모음(각각의 별도 포스팅 참조) ① Quicksort ② Merge Sort ③ Closest Pair of Points ④ Strassen's Algorithm ⑤ Cooley-Tukey Fast Fo.. Computer Science/Algorithms 2023. 3. 20. 중국인의 나머지 정리(CRT;Chinese Remainder Theorem) 🙆🏽♀️ 언젠가 한 번은 정확히 정리하고, 숙지해야 할 알고리즘 '중국인의 나머지 정리' 🙆🏽♀️ 이론을 정확히 알고, 여러 수학 문제에 적용해 복잡한 문제를 쉽게 풀어보자 합동식 🙆🏽♀️ 대수학에서 합동인 두 수는, 어떤 수로 나누었을 때 나머지가 같은 두 수를 뜻한다. → ex) 예를 들어 12와 26은 7로 나누었을 때 나머지가 5이므로 아래와 같은 기호로 쓸 수 있다. $$12\equiv 26\;(mod\;7)$$ 🙆🏽♀️ 즉, a를 p로 나눈 나머지와 b를 p로 나눈 나머지가 같다면, $$a\equiv b\;(mod\;p)$$ 🙆🏽♀️ 이를 식으로 표현한다면, $a=pn+b$ * 합동식의 성질 ① 덧셈은 언제나 성립 (동일한 수를 더하면 동일한 수의 나머지는 당연히 동일하므로 성립) $.. Computer Science/Algorithms 2023. 2. 26. jupyter notebook markdown *수시 업데이트 🫰 markdown에서 유용하다고 생각하는 부분 문법 내용 수시로 업데이트 🫰 ★ font color / 형광펜 ★ red green This is a green colored box This is a red colored box This is a yellow colored box This is a blue colored box ★ 하이퍼링크 ★ [Google](https://www.google.com/) ★ LaTex 수학 문법 ★ → $ 양쪽에 두 개는 가운데 정렬 → $ 양쪽에 한 개는 왼쪽 정렬 ※ latex 여러 기호 참조 (지속적 update) ※ 🧜🏻♂️ LaTex Grammers compilation * 까먹지 않으려고 모아둠 🌟 ⭐️ 분수 쓰기 (A 분자, B 분모) ⭐️ \cfrac{.. Computer Science/Basics 2023. 2. 7. Binary heap 👨🏫 우선순위 큐는 max-heap 또는 min-heap을 사용해 우선순위에 맞는 데이터를 뽑을 수 있는 자료구조임을 공부했다. (아래 포스팅 참조) priority queue - (binary) heap tree 1. concepts> ☝️ 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조' ☝️ 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가 sh-avid-learner.tistory.com ☝️ priority queue는 일종의 Abstract Data Structure(ADT)로, 추상화된 개념을 heap이라는 자료구조로 implement할 수 있다. (우선순위가 최대 먼저, 또는 최소 먼저일 경우 heap은 트리 구조를 .. Computer Science/Data Structures 2023. 2. 6. 이전 1 2 3 4 5 다음
