All Good

Computer Science/Algorithms35

🎢 Topology Sort intro🎢 위상 정렬 = 사이클이 없는 방향 그래프(DAG; Directed Acyclic Graph)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것→ 위상 정렬은 DAG에 대해서만 수행할 수 있다→ 여러 가지 답이 존재할 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우(문제에서 오름차순, 내림차순 명시 없다면) 여러 가지 위상정렬 노드 결과가 존재 가능→ 모든 원소를 방문하기 전에 queue가 빈다면 사이클이 존재한다고 판단 가능(사이클에 포함된 원소 중에서 어떠한 원소도 queue에 들어가지 못한다) (또는 queue에서 노드를 뽑을 때마다 뽑은 노드의 개수가 카운트 되어서, 최종 카운트 된 노드의 개수와 그래프 전체 노드의 개수가 같은 지 다른 지 비교로도 알.. Computer Science/Algorithms 2024. 10. 11.
🫂 Prefix Sum 1D Prefix Sum✊🏻 구간 합 문제는 연속적으로 나열된 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 구간마다 해당 합을 구한다면 시.. Computer Science/Algorithms 2024. 9. 6.
🍣 Fibonacci Sequence 🍣 유명하고 유명한 피보나치 수열(Fibonacci Sequence)은 아래와 같이 표현할 수 있다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ...① Recursive Definition🍣 즉, Fn을 n번째 피보나치 수라고 한다면 재귀 방식으로 Fn을 아래와 같이 표현할 수 있다. F(n) = F(n-1) + F(n-2)with initial conditions F(0) = 0 and F(1) = 1 : 즉, Fn을 구할 때 Fn-1과 Fn-2를 사용해 재귀적 호출로 Fn을 정의할 수 있다. Fn을 재귀적으로 구하는 알고리즘의 시간복잡도는 O(2^n). Fn 호출에 동일 재귀함수 .. Computer Science/Algorithms 2024. 6. 26.
📲 Divide&Conquer * intro🍻 분할(Divide)하고 정복(Conquer)하는 알고리즘은 분할 → 정복 → 결합 크게 세 단계로 진행 🍻① 분할(Divide): 주어진 문제를 더 작은 여러 개의 sub-problem으로 분할한다.② 정복(Conquer): 재귀적으로 sub-problem들을 각각 해결한다. 문제들을 각각 독립적으로 해결. ③ 결합(Combine): 각각의 sub-problem 해결 결과를 묶어 전체 문제의 최종 솔루션을 도출! 🍻 큰 problem을 여러 개의 sub-problem으로 나누는 과정에서 recursion 재귀가 사용된다. 분할을 재귀로 구현하면서 나누고 더 이상 나눌 수 없는 sub-problem 각각 conquer(정복)한 다음 각 sub-problem별 conquer된 결과를 c.. Computer Science/Algorithms 2024. 6. 8.
🚀 Power by Divide and Conquer intro🅰️ 분할정복(divide & conquer)은 복잡한 문제를 해결할 수 있는 여러 쉬운 문제들로 쪼개서 해결하는 접근법. 정수의 거듭제곱을 구하는 과정에서 분할정복 기법을 활용해 더 효율적인 시간 내에 진행할 수 있다. '실수 a와 음이 아닌 정수 x에 대해 a^x를 구하는 문제'① x = 1이면 답은 a로 직접 해결→ 시간복잡도 O(1) ②  x > 1이면 sub-problems로 쪼개기.🅰️ x가 짝수라면 a^(x/2) x a^(x/2)🅰️ x가 홀수라면 a^((x-1)/2) x a^ ((x-1)/2) x a→ 시간복잡도 T(x) = T(x/2) + O(1). 즉 T(x) = O(logx)example 7^10🅰️ 예를 들어 7^10을 구하는 문제가 있다고 하자. 두 가지 접근법으로.. Computer Science/Algorithms 2024. 6. 6.
🛣️ Shortest Path in an Unweighted Graph intro🛣️ 그래프에서 최단거리를 구하는 알고리즘은 여러가지가 있다. 다익스트라, 플로이드-워셜, 벨만-포드와 같은 유명한 최단거리 TOP 3 알고리즘이 존재하는데, 간선의 가중치가 전혀 없는, 주어진 일반적인 그래프에서의 최단 거리를 구하는 방법은 BFS가 best. 이번 포스팅을 통해 주어진 그래프에서 BFS를 사용해 최단거리 구하기와 최단거리 내용 출력까지 알아본다.DFS는 안되고 BFS는 가능한 이유?🛣️ 그래프 순회의 대표적인 2가지 방법으로는 DFS, BFS가 있다. 그러나 shortest path in an unweighted graph를 찾기 위해서는 DFS보다는 BFS 방식을 적극 권장. 접근 방식에 차이가 있기 때문이다. : BFS의 경우 level-wise exploration .. Computer Science/Algorithms 2024. 5. 23.
⛆ Flood Fill intro⛆ 플러드 필(Flood Fill) 알고리즘 이란, 주어진 2차원 그래프에서 연결영역의 개수 및, 각 연결영역의 연결 노드 개수를 구하는 알고리즘이다. 즉, 플러드 필은 DFS / BFS 그래프 순회 알고리즘을 응용한 알고리즘으로, 주어진 2차원 배열에서 연결 영역 관련 문제를 풀 때 사용된다.  ⛆ 대표적인 케이스로, 연결 영역 개수 구하기, 가장 큰 영역 면적 구하기, 각 연결 영역 내의 노드 개수 구하기 등등이 나온다. ⛆ 시간 복잡도는 traverse할 2차원 그래프의 행 개수가 N이고 열 개수가 M이라면 O(NM), 공간 복잡도는 O(NM)이다.  1. 연결 영역 개수 구하기ex) BOJ 4963 S2 Q. 1과 0으로만 이루어진 2d array에서 1로만 이루어진 연결 영역, 즉 섬의.. Computer Science/Algorithms 2024. 5. 19.
🏘️Euler Sieve intro 🏘️ 소수 판정법으로 유명한 에라토스테네스의 체(Sieve of Eratosthenes)를 개선한 '오일러의 체(Euler Sieve)'에 대해서 소개한다. 에라토스테네스의 체는 소수 판별 시간 복잡도가 O(nloglogn)임이 알려져 있고, 이를 개선한 오일러의 체 시간 복잡도는 단 선형 시간만에 O(n)으로 판별이 가능하다. 🏘️ 에라토스테네스의 체의 시간 복잡도가 선형 시간(O(n))이 될 수 없는 이유는 합성수 210을 들면 쉽게 알 수 있다. 210은 2x3x5x7로 나타낼 수 있는데, 에라토스테네스의 체에 의해서는 2x3x5x7 / 2x3x5x7 / 2x3x5x7 / 2x3x5x7 와 같이 각각 빨간색 숫자일 때 210이 합성수임을 중복해서 알려주고 있다. 🏘️ 따라서, 이를 단 한.. Computer Science/Algorithms 2024. 4. 21.
🥐Counting Sort orders① 정렬할 데이터를 준비한다.7 5 9 0 3 1 6 2 9 1 4 8 0 5 2○ 이 때, 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 list를 생성 ○ ② 왼쪽부터 데이터를 하나씩 확인하며 데이터의 값과 동일한 index의 데이터를 1씩 증가시킨다. ③ 오름차순 결과를 확인하기 위해 각 원소의 계수가 저장된 list를 왼쪽 끝부터 돌려 해당 데이터의 값만큼 반복해 인덱스를 출력한다. - 출력 결과 -0 0 1 1 2 2 3 4 5 5 6 7 8 9 9about Counting Sort🥐 특정한 조건이 부합할 때만 사용할 수 있으나 매우 빠르게 동작하는 정렬 알고리즘. (*특정한 조건: 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용) 🥐 .. Computer Science/Algorithms 2024. 4. 17.
🗼Tower of Hanoi intro🗼 유명한 '하노이의 탑' 알고리즘에 대해 소개한다. 3개의 기둥이 있고, 다양한 크기의 n개의 원판(원판의 크기는 모두 다르다)이 존재한다. 퍼즐을 시작하기 전에는 한 기둥에 n개의 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 아래 3가지 조건을 만족 시키면서 다른 기둥으로 옮겨서 다시 쌓는 퍼즐이다. ① 한 번에 1개의 원판만 옮길 수 있다.② 가장 위에 있는 원판만 이동할 수 있다.③ 큰 원판이 작은 원판 위에 있어서는 안된다. 이 때, 최소 이동횟수로 맨 왼쪽 기둥에서 맨 오른쪽 기둥으로 n개의 원판을 순서에 맞추어서 쌓아주면 된다example demo (n=3)🗼 n=3일 때 Hanoi Tower를 쌓아보자!🗼 Hanoi Tower 문제는 크게 아래 3가지 순서로 진행된다.. Computer Science/Algorithms 2024. 4. 9.
➕Merge Sort orders ★ 원소를 개별적으로 나누고, 병합하는 두 과정이 수반되는 정렬 ★ (아래 과정 ②는 divide / ③은 merge) (따라서 merge sort는 나누고 + 합치고 두 과정) ① 정렬할 데이터 준비 (오름차순 가정) 7 3 1 5 6 4 2 ② 본격적인 merge sort를 하기에 앞서서 각각 원소가 1개씩만 있게끔 recursive하게 array를 절반으로 쪼갠다 (recursion 적용) 7 3 1 | 5 6 4 2 → 7 | 3 1 | 5 6 | 4 2 → 7 | 3 | 1 | 5 | 6 | 4 | 2 ③-1) 두 개씩 쪼개는 루트의 역 방향으로 작은 원소를 앞에, 큰 원소를 뒤에 놓는다. (1) 3 1 에서 3 | 1로 쪼갰으므로 1 3으로 정렬 (2) 5 6 에서 5 | 6으로 .. Computer Science/Algorithms 2024. 4. 6.
🍡 Two Pointers intro🍡 two pointers란 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 이중 for문으로 돌리면 i=0일때의 정보를 i=1일 때 전혀 쓰이지 않지만, two pointers는 i=0일 때의 작업이 i=1일 때의 작업에 쓰인다. 과거 정보를 기억한 채로 효율적이게 index를 O(N)으로 움직이는 알고리즘. 이분탐색 문제를 투포인터로도 풀 수 있는 경우가 많고, 그 반대도 많다. two pointers는 O(N)으로, 각각의 모든 case를 일일이 점검할 필요 없이, 일부 case는 점프하는 경우만 풀이가 가능.explanation🍡 위와 같은 배열이 있다고 할 때, a일때 b~i를 돌고 / b일 때 c~i를 도는 .. Computer Science/Algorithms 2024. 2. 11.

티스토리툴바