All Good

Computer Science/Algorithms30

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.
🪴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.
🔸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.
🫂 Prefix Sum intro ✊🏻 구간 합 문제는 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 계산하는 문제 유형을 뜻한다. ✊🏻 예를 들면, 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정했을 때, 2번째 수부터 4번째 수까지의 합은 20 + 30 + 40인 90이 된다. ✊🏻 N개의 정수로 구성된 수열이 있고, M개의 query 정보가 주어진다. 각 query는 left와 right로 구성. 각 query에 대하여 [left, right] 구간에 포함된 데이터들의 합을 출력해야 한다. (수행 시간 제한은 O(N+M)) → 위 예와 접목하자면, 5개의 데이터 (N=5)로 구성된 수열에서 매번 새로운 query 구간마다 해당 합을 구한다면 시간 복잡도는 O(N.. Computer Science/Algorithms 2023. 1. 18.
Regular Expression 💚 정규 표현식은 '패턴 매칭 기반으로 특정한 규칙을 가지는 문자열을 검색&분리하고 교체하는 강력한 기능을 제공하는 형식 언어' 💚 python에서는 re library를 import import re 1. re.search() & re.match() & re.fullmatch() 💚 re.match() checks for a match ONLY at the beginning of the string, whereas re.search() checks for a match anywhere in the string ※ re.match는 문자열 처음부터 매칭 / re.search는 문자열 일부분 매칭) ※ 💚 re.fullmatch() checks for entire string to be a match. ①.. Computer Science/Algorithms 2023. 1. 11.
🛝Dynamic Programming🛝 intro 🐥 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함. 따라서 완전탐색의 비효율적인 시간 복잡도 성능 한계점을 해결해준다. 또한 '다이나믹 프로그래밍 = 동적계획법'이라고도 부른다. (동적(dynamic) 할당(allocation) - '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'). DP 알고리즘을 활용한다면 여러 sub-problem 포함 모든 문제의 정답이 들어가는 메모리 미리 배치(이 때 여러 문제들의 결과를 저장하는 저장용 list는 dp-table). DP 알고리즘을 활용하기 위해서는 아래 두가지 조건을 만족해야 한다. ① 최적 부분 구조(Optimal Subst.. Computer Science/Algorithms 2023. 1. 3.
bitmasking * intro> 💧 bitmask = '컴퓨터는 내부적으로 모든 자료를 이진수로 표현. 이 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법' (엄밀하게 자료구조는 아님) 💧 2진수 관련 bit 연산을 진행하면 웬만한 모든 연산의 time complexity가 $O(1)$로 표현되므로 매우 매우 유용하고 편리함! 💧 2진수와 10진수 간의 변환방법 (python) ① 10진수 → 2진수: bin() 함수 사용 (반환 결과 string) print(bin(100)) #0b1100100 #type 'str' ② 2진수 → 10진수 (1) 2진수가 0과 1로 구성된 숫자라면 앞에 0b를 붙이고 출력 (2) 2진수가 문자열 형태라면 int()에 문자열과 2를 지정해 변환 ※ bin의 결과가 문자열로 반환.. Computer Science/Algorithms 2022. 12. 20.

티스토리툴바