[DP] 행렬 연쇄 곱셈 문제 해결하기

행렬의 연쇄 곱셈이란여러 행렬의 곰센 순서를 최적화하여 문제를 해결하는 알고리즘이다. 이 알고리즘은 해열 곱셈 연산의 횟수를 최소화하기 위해 사용된다. 우선 행렬 곱셈부터 다시 점검해보면 아래와 같다. 행렬 곱셈의 결합법칙사전적으로, 행렬 A와 B의 곱이 정의되기 위해서는 위와 같이 A행렬의 열과 B행렬의 행의 크기는 같아야한다.(더불어 A*B 결과인 X행렬은 (A행렬의 열크기) x (B행렬의 행크기), 즉 p*r이 된다.)   열과 행의 조건을 성립한 행렬의 곱셈은 연산 순서자체는 결과에 영향을 미치지 않는다.  하지만 과정에서 차이가 있다. 연산 횟수에 대한 공식 자체는 위와 같다.A의 한 행과 B의 한 열이 곱해져서 C의 하나의 원소를 계산하기 때문에, 한 원소를 계산하기 위해선 'q'번의 곱셈이 ..

• format_list_bulleted Algorithm
• · 2024. 11. 28.
• textsms

[자료구조] 우선순위 큐의 자료구조는 뭘까

알다시피 힙을 쓴다기존의 Queue는 먼저 들어온 것이 먼저 나가는 FIFO 구조였다. 여기에 우선순위라는 조건이 더해져, 해당 우선순위가 높은 원소부터 나가는 것이 PriorityQueue다. 그렇다면 이 PriorityQueue(이하 PQ)는 원소의 추가가 일어날때마다 우선순위 조건에 대한 정렬상태를 잘 유지해야 할 것이고, .poll()을 진행할 시 최댓값이나 최솟값에 대해 빠르게 접근하여 가져와야 할 것이다.위와 같은 고려를 하고보니 Heap이 제일 적절하더라인데, 조금만 더 살펴보자. 배열로 구현하면 어디서 문제인가 최솟값에 따라서 정렬된 상태를 배열로 관리하고 있다고 치자, 당연히 배열이니까 최솟값인 첫 자리에만 접근하는 탐색 비용은 O(1)이다. 하지만 이제 '7'이라는 숫자가 들어와 정렬상..

• format_list_bulleted Algorithm
• · 2024. 11. 17.
• textsms

[JAVA] 1238. 파티

코드import java.io.*;import java.util.*;public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int N, M, X; static int[] toI; // [i][j]: i -> j로 갈 때의 비용 static int[] toX; static List> goTo; // 단방향 그래프 static List> goFrom; public static void..

• format_list_bulleted Algorithm
• · 2024. 11. 12.
• textsms

팰린드롬 DP로 풀어보기

https://www.acmicpc.net/problem/10942[10942. 팰린드롬?] 풀러가보자   기존의 투포인터 방식의 풀이 public static boolean isP(int lt, int rt) { while (lt   위의 경우, 이분탐색은 일반적으로 O(logN)의 빠른 시간 효율성을 가지지만 만약 주어진 배열의 모든 조합 (i, j까지의 부분 배열에 대하여) 확인한다고 치면 주어진 배열의 양 끝에서부터 중앙으로 비교하며 최악의 경우 O(N)을 갖게 될 수 있다.그렇게 되면 총 시간복잡도는 질문의수(M) * 수열의 길이(N) 만큼이므로 비효율적이다. 생각해보면 그 모든 케이스 안에서도 중첩된 경우의 수가 있으니, 이를 DP로 해결하고자 하는 아이디어가 나올 수 있다..

• format_list_bulleted Algorithm
• · 2024. 11. 10.
• textsms

2차원 배열 쉽게 돌리기 (90, 270도 회전)

알고리즘 논리*사각형이 N X N, 즉 정사각형이라는 가정을 한다1. 가장 가장자리의 테두리 영역부터 회전시킨다 (s, e)2. 가장 바깥 테두리의 시작점을 0, 끝점을 map.length-1 위치라고 생각하자3. 각 변을 Top, Left, Bottom, Right라고 할 때 각 변의 첫자리, 두 번째 자리, 세 번째 자리 순으로 교체시킨다 (i, j) static void rotate(int[][] map) { for (int s = 0, e = map.length - 1; s

• format_list_bulleted Algorithm
• · 2024. 11. 9.
• textsms

[자료구조] 정렬방법의 In-Place&Stable성질, (ft. Quick & MergeSort)

⚡참고: GitHub - VSFe/Tech-Intervicew 🤐 세부 질문 1️⃣ Quick Sort와 Merge Sort를 비교해 주세요.2️⃣ Quick Sort에서 O(N^2)이 걸리는 예시를 들고, 이를 개선할 수 있는 방법에 대해 설명해 주세요.3️⃣ Stable Sort가 무엇이고, 어떤 정렬 알고리즘이 Stable 한지 설명해 주세요.4️⃣ Merge Sort를 재귀를 사용하지 않고 구현할 수 있을까요?📢 키워드별 설명1️⃣ Quick Sort와 Merge SortQuick Sort: 하나의 Pivot을 선정 → 이 값을 기준으로 정렬을 해나감. 예를 들어 Pivot보다 작은 값은 좌측, Pivot보다 큰 값은 우측에 위치시키도록 한다 ( 우측 .gif은 1회의 작업만을 나타냄, 이후 ..

• format_list_bulleted Algorithm
• · 2023. 3. 23.
• textsms