Computer Science65 🔬 Parametric Search 🐧 최적화 문제를 여러번의 결정문제(예 혹은 아니오)로 바꾸어 이분탐색으로 해결하는 기법 → 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 - 여기서 최적화란, 어떤 값을 최대한 높이거나 낮출 때 사용 🐧 ① Parametric Search로 구하고자 하는 값을 이분탐색으로 증/감 바꾸며 YES/NO 여부 확인 ② 결정문제를 만족하고 만족하지 않음에 따라 이분탐색 범위를 end를 mid-1 또는 start를 mid+1로 설정해 절반으로 줄임 ★ 탐색의 범위가 log2N씩 줄어드므로 1억이 넘어가는 범위라 하더라도 매우 효과적인 시간 내에 탐색 가능 ★ ① BOJ 3079 입국심사(골드5) : 입국심사대의 개수가 주어지고, 방문한 인원 M이 주어진 상태에서 입국심사를 받는 시간 x의 최.. Computer Science/Algorithms 2023. 12. 31. 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 & faultalgorithm ▶ "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. 📚 Map Mapfundamentals → dictionaries are indexed by keys, which can be any immutable type; strings and numbers can always be keys. / map data structure is defined as a data structure that stores a collection of key-value pairs, where each key is associated with a single value / maps provide an efficient way to store and retrieve data based on a unique identifier(the key) → Tuples can be used as keys .. 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. 중국인의 나머지 정리(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 / 형광펜 ★redgreen This is a green colored boxThis is a red colored boxThis is a yellow colored boxThis is a blue colored box ★ 하이퍼링크 ★[Google](https://www.google.com/) ★ LaTex 수학 문법 ★→ $ 양쪽에 두 개는 가운데 정렬→ $ 양쪽에 한 개는 왼쪽 정렬 ※ latex 여러 기호 참조 (지속적 update) ※ 🧜🏻♂️ LaTex Grammers compilation* 까먹지 않으려고 모아둠 🌟 ⭐️ 분수 쓰기 (A 분자, B 분모) ⭐️ \cfrac{A}{B.. Computer Science/Basics 2023. 2. 7. 🔸Coordinate Compression🔸 intro / implementation 🔸 넓게 퍼져 있는 값들을 문제 해결을 위해 좌표 압축. (위 그림의 경우 -6~5까지의 퍼져 있는 수들을 차례대로 0 - 1 - 2 - 3 - 4로 나열 가능) 🔸 주의점: 주어진 수들의 크기가 중요치 않고, 크기 순서만이 문제 해결에 필요할 때 좌표 압축 진행 🔸 구현 ex) 랜덤 크기 순으로 나열된 A[1], A[2], A[3], .... A[n]을 좌표 압축 ① A[1], A[2], ... , A[n]를 정렬한 새로운 배열 B[] 생성 ② 필요 시 중복된 원소들을 제거(중복 카운트 중요치 않을 경우만) ③ 각 A[i]를 B[]에서 이분탐색하여 B[]에서의 A[i] index를 계산 🔸 쉽게 말하자면, 랜덤하게 배치된 다양한 크기의 숫자들을 index의 크기.. Computer Science/Algorithms 2023. 1. 24. 이전 1 2 3 4 5 6 다음
