All Good

Computer Science/Algorithms35

🦜 Pigeonhole Principle intro 🦜 총 19개의 구멍이 있는 비둘기집에서 20마리의 비둘기가 들어가려고 할 때, 적어도 한 곳의 비둘기집에는 적어도 2마리 이상의 비둘기가 반드시 있을 수 밖에 없다는 원리. ① theorem I: 각 구멍에 A마리의 비둘기가 평균적으로 들어가 있다면, A가 정수가 아니라면, 적어도 한 곳에는 ceil(A)마리의 비둘기가 있다는 뜻. 나머지 비둘기 집에는 최대 floor(A)마리의 비둘기가 있다. ② theorem II: n+1개의 물건을 n개의 상자에 넣으려고 할 때, 적어도 한 개 이상의 상자에는 2개 이상의 물건을 넣을 수 밖에 없다. 🦜 generalization ①) 만약 Kn+1마리의 비둘기가 n개의 비둘기집에 들어가려고 할 때, (Kn+1)/n은 K + 1/n이므로 적어도 한 곳의.. Computer Science/Algorithms 2024. 2. 2.
🙃 Backtracking intro 🙃 backtracking이란, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. 구현력을 필요로 한다. 현재에서 나올 수 있는 모든 경우의 수를 모아 둔 decision space를 만들고, decision space의 각 부분마다 뻗어 나가며 그 다음으로 나오는 deicision space에서 계속해서 뻗어나가며 탐색. 만약 뻗어나간 결과 문제 상황에 맞지 않으면, 그 자리에서 중단하고 다시 뒤로 후퇴하면서 올라가 또 다른 경우의 수로 뻗어나가며 탐색. 🙃 즉, 요약하자면 재귀적으로 가능한 모든 case를 incrementally하게 탐색해나가면서 해당 문제 조건에 만족하지 않는 경우는 이전으로 돌아가(backtrack) 계속 솔루션을 찾는 기법(결론: 백트래킹은 그냥 .. Computer Science/Algorithms 2024. 1. 18.
🧿 Dijkstra's (Shortest Path) Algorithm intro 🧿 다익스트라 알고리즘이란 '방향 그래프 또는 무방향 그래프에서 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘'이다. 플로이드 알고리즘은 모든 정점 쌍 사이의 최단 거리를 일일이 구하는 알고리즘. 플로이드 알고리즘은 음수인 간선 존재는 괜찮지만 음수인 사이클이 있을 때만 문제이나, 다익스트라는 음수인 가중치를 가지는 간선이 있으면 아예 사용 불가능. 음수인 간선이 있다면 벨만포드 알고리즘 사용. 또한 정확한 최단거리가 아닌 근사치를 원할 경우 A* 알고리즘을 사용함. 다익스트라는 네트워크에서도 많이 사용. 🧿 일명 '최단 경로 알고리즘' 중 하나로, 최단 경로 문제 상황은 (1) 한 지점에서 다른 한 지점까지의 최단 경로 (2) 한 지점에서 다른 모든 지점까지의 최단 .. Computer Science/Algorithms 2024. 1. 14.
🍝LIS(Longest Increasing Subsequence) O(n^2)/O(nlogn) LIS(O(n^2))「1」 LIS의 길이만 구할 경우 🍝 주어진 수열에서 가장 긴 증가하는 부분 수열을 구하는 문제. 이 때 부분 수열은 연속적일 필요 없고 unique할 필요도 없다. 띄엄띄엄 떨어진 원소 모음의 subsequence가 increasing하기만 하면 되며, increasing subsequence 중 최대 길이를 찾으면 된다. 예를 들어 [3, 10, 2, 1, 20]이 있다면 longest increasing subsequence는 [3, 10, 20] / [3,2]에서는 [3]과 [2] / [50, 3, 10, 7, 40, 80]에서는 [3, 7, 40, 80]이 있다. 이는 dp를 이용해서 쉽게 구할 수 있다. D[i]를 i번째 index에서 끝나는 LIS 길이라고 정의. .. Computer Science/Algorithms 2024. 1. 6.
📡Kadane's Algorithm 🔊 주어진 배열에서 '부분연속수열합'의 최댓값을 구하는 알고리즘이다. DP로도 구할 수 있고, well-known Kadane's Algorithm을 활용해서도 매우 간단히 해결할 수 있다. 🔊 각 element traversing할 때마다 max() 두 번 사용. max_till_now로 최종 최댓값 update하고, cur_max는 현재위치의 원소 only & 현재위치의 원소 포함 그 전의 cur_max 합 두 개중 최댓값 update. 즉 cur_max로 각 원소를 포함한 부분연속수열합 최댓값을 계속 구해나가는 dp 방식이나 마찬가지. 다만, dp는 최종적으로 max() 한 번 사용이지만, Kadane's algorithm에서는 max()를 그 때 그 때 update하는 방식만 차이점. 핵심은 '현.. Computer Science/Algorithms 2024. 1. 3.
🔬 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.
🐝 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.
🪴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.

티스토리툴바