algorithm16 지수법칙 & 모듈러 연산 알고리즘 문제를 풀다가 지수법칙과 모듈러 연산에 관한 수학적인 문제가 나와 기억하기 위해 작성한다.지수법칙(거듭제곱의 곱)지수법칙은 다음과 같다.$$x^{n} \ast x^{m} = x^{n+m}$$ ex) $x^8$ 지수가 짝수일 때 즉, $x^8 = x^{4+4}$= $x^4 * x^4$= $(x^2 * x^2) * (x^2 * x^2)$= $((x^1 * x^1) * (x^1 * x^1)) * ((x^1 * x^1) * (x^1 * x^1))$ ex) $x^9$ 지수가 홀수일 때 즉, $x^9 = x^{4+4} * x$= $x^4 * x^4 * x$= $(x^2 * x^2) * (x^2 * x^2) * x$= $((x^1 * x^1) * (x^1 * x^1)) * ((x^1 * x^1) * (x.. 2025. 2. 13. 누적합(Prefix Sum) 누적합(Prefix Sum)누적합은 요소들의 누적된 합의 의미를 얘기합니다.배열의 첫 번째 0번째 배열의 요소부터 누적시키면서 더한 배열을 활용합니다. 일부 구간에 대한 합을 구하는 문제에서 사용이 됩니다. 단, 배열의 값들이 변하지 않는다는 전제가 필요합니다. $ N = 5 $ 인 N 크기의 정수 배열 arr이 있을 때 여러 개의 구간 [a, b]에 대해 합을 구하려고 합니다. $ 1\leq a\leq b\leq N $$$ arr[a]+arr[a+1]+\cdots+arr[b] $$Index i01234arr[i]16425 간단하게 생각할 수 있는 방법은 반복문을 돌려서 각 요소를 더하는 것입니다. 이 방법은 각 쿼리에 대해 최대 $ O(N) $ 시간 복잡도를 가지고, 만약 M개의 쿼리가 주어지면 시간 .. 2025. 1. 19. DFS (Depth-First Search) BFS가 궁금하면 아래 글을 참조 BFS (Breadth-First Search) ✔ DFS(Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며, 그래프를 탐색하는 방법 중 하나이다. 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것으로 즉, 시작 노드에서 출발해 인접한 노드(가까운 노드)를 먼저 탐색하고 그 정점의 최대 깊이까지 탐색을 마친 후 돌아와 다른 분기로 다시 탐색하는 알고리즘이다. 넓게 탐색하기 전에 깊게 탐색 스택 or 재귀를 사용하여 구현 모든 노드를 방문할 때 사용 ※ 중요한 점은 방문한 정점은 다시 방문하지 않아야 한다. DFS는 스택으로도 구현할 수 있지만 재귀로 구현하는 편이 더 깔끔해서 재귀로 더 많이 구현하는 것 같다. DFS와 BF.. 2023. 6. 25. BFS (Breadth-First Search) DFS가 궁금하면 아래 글을 참조 DFS (Depth-First Search) ✔ BFS(Breadth-First Search) BFS는 너비 우선 탐색이라고도 부르며, 그래프를 탐색하는 방법 중 하나이다. 하나의 정점으로부터 시작해서 차례대로 모든 정점들을 한 번씩 방문하는 것으로 즉, 시작 노드에서 출발해 인접한 노드(가까운 노드)를 먼저 탐색하고 현재 깊이의 모든 노드를 탐색하면서 가는 알고리즘이다. 깊게 탐색하기 전에 넓게 탐색 두 정점 사이의 최단 경로를 구할 때 사용 같은 가중치를 가진 그래프에서 사용 큐(queue)를 사용하여 구현 ※ 중요한 점은 방문한 정점은 다시 방문하지 않아야 한다. 만약 가중치가 다른 그래프일 때 최단거리를 구하는 알고리즘은 다익스트라, 벨만포드 등으로 구현해야 한다.. 2023. 6. 17. 큐(Queue) ✔ 큐(Queue) 큐도 스택과 마찬가지로 알고리즘보단 자료 구조에 해당하고 컴퓨터에서 많이 사용되는 자료 구조이다. 큐는 먼저 집어넣은 데이터가 먼저 나오는 선입선출(FIFO: First In First Out) 구조로 저장하는 형식을 말한다. 즉, 가장 처음에 넣은 값이 먼저 나오는 것을 FIFO 구조라고 한다. 나중에 넣은 값이 먼저 나오는 스택과는 반대되는 개념이다. 쉬운 예시로 파이프 혹은 드라이브 스루를 생각하면 된다. 드라이브 스루는 가장 먼저 들어가는 사람이 먼저 주문을 하게 되고 그 뒤로 차례로 줄을 서게 된다. 먼저 들어간 사람이 주문을 끝내고 가지 않는 이상 그 뒤로는 계속 기다려야 하는 구조이다. 이 구조가 큐 자료 구조에 해당한다. ✔ 큐의 연산 큐는 양쪽이 뚫려 있는 구조로 한쪽.. 2023. 5. 2. 스택(Stack) ✔ 스택(Stack) 스택은 알고리즘보단 자료 구조에 해당하고 컴퓨터에서 아주 많이 사용되는 자료 구조이다. 스택은 제한적으로 접근할 수 있는 나열 구조로 한쪽 끝에서만 자료를 넣고 뺄 수 있는 후입선출(LIFO : Last-In First-Out) 구조이다. 즉, 가장 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. 쉬운 예시로 프링글스 과자를 생각하면 된다. 프링글스 과자를 포장할 때 처음 과자가 통 맨 밑으로 들어가게 되고 그다음부터 위로 쌓이게 되고 구매자는 과자를 먹을 때 통 맨 위에서부터 하나씩 꺼내서 먹게 된다. 이 구조가 스택 자료 구조에 해당한다. ✔ 스택의 연산 스택은 가장 윗부분을 "top"이라 명칭 한다. top(): 스택의 가장 윗 데이터를 반환 pop(): 스택의 가.. 2023. 4. 15. 이전 1 2 3 다음
