josolha

계기 Softeer의 슈퍼바이러스 문제에서 거듭제곱을 계속 하는 로직을 구현했지만 시간초과 에러를 만나게 되어서 정리하게 되었다. 일반 거듭제곱 알고리즘 일반 거듭제곱 알고리즘은 기본적으로 주어진 수 a를 b번 곱하는 것을 의미한다. 즉, ab의 값을 계산하는 것이다. 간단한 방법으로는 반복문을 사용하여 a를 b번 곱하는 것이다. public static long power(long a, long b) { long result = 1; for (long i = 0; i < b; i++) { result *= a; } return result; } 이 방법의 시간 복잡도는 O(n)이다. 왜냐하면 반복문이 b번 실행되기 때문이다. 이는 b가 커질수록 매우 비효율적이 될 수 있다. 하지만 분할 정복을 사용한 ..

동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제 들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다. 동적 계획법의 핵심 이론 동적 계획법의 원리와 구현 방식은 다음과 같다. 동적 계획법의 원리와 구현 방식 ① 큰 문제를 작은 문제로 나눌 수 있어야 한다. ② 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결값은 항상 같아야 한다. ③ 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. (이를 메모이제이션memiozation 기법이라고 한다.) ④ 동적 계획법은 톱-다운 방식top down과 바텀-업bottom up 방식으로 구현할 수 있다. 동적 계획법의 가장 대표적인 문제인 피보나치 수열을 ..

해설 1. 그래프 인접 리스트로 저장, 방문 배열 초기화. 방향이 없는 그래프 라서 양쪽 방향으로 에지를 모두 저장한다. 2.임의의 시작점에서 DFS를 수행한다. 현재의 경우 1을 시작점으로 정함. 탐색을 마친 이후 방문한 곳은 1,2,5가 된다. 3.아직 방문하지 않은 노드가 있으므로 시작점을 다시 정해 탐색을 진행. 현재의 경우 3,4,5, 순서로 탐색을 마침. 모든 노드를 방문했으니 전체 탐색을 종료. 4.1~3 과정을 통해 총 2번의 DFS가 진행되었다. 즉 연결 요소 개수는 2개이다. 모든 노드를 탐색하여 탐색 종료 -> DFS 총 2회 수행 *연결 요소 개수 = 2 만약 그래프가 모두 열결 되어있었다면 DFS는 1번 실행되었을 것이다. 다시말해 모든 노드를 탐색하는 데 실행한 DFS의 실행 횟..

프렉탈 구조 프랙탈은 자연에서 발견되는 복잡한 패턴을 수학적으로 모델링한 구조로, 재귀적인 자기 유사성을 특징으로 한다. 프랙탈은 간단한 규칙이 반복 적용되어 복잡하고 상세한 패턴이나 구조를 생성한다. 이러한 특성 때문에 프랙탈은 수학, 자연과학, 예술 등 다양한 분야에서 활용된다. 본 코드에서 구현된 프랙탈 별 패턴은 이러한 프랙탈의 개념을 바탕으로 한다. 각 단계마다 3x3 그리드를 기반으로 중앙을 비워두는 규칙을 재귀적으로 적용함으로써, 복잡하면서도 규칙적인 별 모양의 패턴을 생성한다. 이 패턴은 각 단계마다 하위 그리드로 나누어지며, 각 하위 그리드 내에서도 동일한 패턴이 반복되어 전체적인 프랙탈 구조를 형성한다. 문제 설명 2차원 배열과 행을 x, 열을 y 로 생각해보면 된다. N = 3 일 때..