알고리즘

탐색(search)많은 양의 데이터 중에서 원하는 데이터를 찾는 과정그래프(graph)노드(node)와 간선(edge)으로 표현되며 이때 노드를 정점이라고 한다그래프 탐색하나의 노드를 시작으로 다수의 노드를 방문하는 것대표적인 그래프 탐색 알고리즘dfs와 bfs가 있음

피보나치 수열피보나치 수열은 n번째 값이 (n-2)번째 값과 (n-1)번째 값을 더한 값임을 만족하는 수열임즉, 1, 1, 2(1+1), 3(1+2), 5(2+3), 8(3+5), 13(5+8), 21(8+13), 34(15+24), 55(21+34) …결국 일반 반복

gcdgreatest common divisior두 수(혹은 그 이상) 의 공통 약수 중 최대인 것lcmleast common multiple두 수(혹은 그 이상) 의 공통 배수 중 최소인 것약수(divisor)a를 b로 나누었을때 나머지가 0이면 b는 a의 약수gcd

소수prime number1과 자기자신 외에는 어떠한 수로도 나누어 떨어지지 않는 수특정 수 N이 소수인지 아닌지 구하는 법2부터 n-1까지의 수로 해당 수를 나눠보고, 이 과정에서 어떠한 수에 의해 나누어 떨어지는 지 확인나누어 떨어진다면 합성수, 한 번도 나누어 떨

itertools 의존 말고 이젠 그냥 외워보자... 🛠🔩⚙️

이코테 최단 경로 알고리즘 강의를 보고 정리한 것입니다.

우리는 이미 이전 포스팅(https://velog.io/@rhdmstj17/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%94%8C%E

서로소 집합이란 공통 원소가 없는 즉, 교집합이 없는 두 집합을 의미한다. (1,2)와 (2,5)는 서로소 집합이 아니지만 (1,2)와 (4,5)는 서로소 집합이다. 따라서 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 데이터를 처리하기 위한 자료구조를 의미힌다

💡 크루스칼 알고리즘을 완전히 이해하기 위해선 서로소 집합 자료구조의 동작원리(find 연산, union 연산)에 대해 필수적으로 알아야한다. 아직 서로소 집합 자료구조의 개념을 잘 모른다면 해당 포스팅 을 보고 숙지해보자 !크루스칼 알고리즘은 최소 신장 트리를 찾기

최소 신장 트리의 대표 알고리즘인 Prime 알고리즘에 대해 알아보자. 최소 신장 트리 개념은 이전 포스팅에 정리해두었으니 아직 잘 모르겠다면 이전 포스팅 을 보고 숙지해보자대표적인 최소 신장 트리 알고리즘이다.크루스칼 알고리즘프림 알고리즘프림 알고리즘시작 정점(노드)

사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열 하는 것을 의미한다.예를 들어 아래와 같이 선수과목을 고려해 수강신청을 해야한다고 했을 때,세 과목을 모두 듣기 위한 적절한 학습 순서는 자료구조 -> 알고리즘 -> 고급 알고리즘이 될것이

모든 kmp 알고리즘 포스팅 중 가장 쉽고 자세하게 kmp 이해해보기 🤗⚙️🦾

비트 마스크를 알아보기 전에 비트 연산자 먼저 훑고 가보자.& (AND)비교하는 비트가 둘 다 참일 때 만족0011 & 0110 = 0010| (OR)비교 하는 비트 둘 중 하나라도 참이면 만족0011 | 0110 = 0111^ (XOR)비교 하는 비트가 서로 달라야

동적 계획법 으로도 불린다🙋🏻‍♀️ 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미일까?자료구조에서 동적 할당(Dynamic allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 을 의미한다.그러나 다이나믹 프로그

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정한 가치의 무게가 정해진 짐들을 배낭에 담을 때, 가치의 합이 최대가 되는 조합을 찾는 알고리즘이다.Fractional Knapsack Problem말 그대로 물건을 쪼갤 수 있는 배낭 문제로이다. 가치가 높은 순

(다들 이미 알고 있는 내용이겠지만) python으로 코테 풀이할 때 숙지해두면 좋을 7가지를 선정해보았다. 한 번 정리해두면 유용하니까 나를 위해서 😎파이썬의 복사에는 깊은 복사와 얕은 복사가 존재한다. 알고리즘 문제를 풀다보면 그래프나 리스트 등 mutable한

선형 자료구조에 해당하는 배열, 연결리스트, 스택, 큐, 데크, 우선순위 큐에 대해 간단히 알아보고 자료구조, 자료형, 추상 자료형의 차이점에 대해 명확히 알아보자 선형 자료구조 데이터 요소가 순차적으로 배열되는 자료구조를 선형 자료구조라고 함 즉, 선형 자료구조는

[ ] 그리디 [ ] BFS [ ] DFS 및 백트래킹 [ ] 정렬 알고리즘 [ ] 이진 탐색 [ ] DP [ ] 최단 경로 알고리즘 [ ] 다익스트라 [ ] 플로이드-와샬 알고리즘 [ ] 벨만포드 알고리즘 (음수간선 o) [ ] 기타 그래프 이론 [

Longest Common SubSeqeunce 와 Longest Common SubString

선형공간인 1차원 배열에서 특정 조건을 만족하는 연속 구간의 합을 구해야 한다고 가정해보자. 가장 먼저 떠오르는 방식으로는 배열의 인덱스를 처음부터 끝까지 돌면서 완전 탐색을 할 수 있을 것이다. 하지만 이는 O(N^2)의 시간복잡도가 걸리므로 효율성 면에서 좋지 않다

지난 글에 이어서 구간합을 구하는데 자주 활용되는 바이너리 인덱스 트리에 대해 알아보겠다. 시간복잡도를 O(logN)까지 줄일 수 있는 효자 알고리즘이다.필자는 바이너리 인덱스 트리를 Prefix Sum의 업데이트 버전이라고 생각하는 편인데, Prefix Sum으로 구