알고리즘90 [백준 11660] 구간 합 구하기 5 / 자바 / 누적합 문제 레벨: 알고리즘: 누적합풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/116601 번째 시도 이 문제는 이차원배열의 누적합이다.알고 가야 할 것은 일차원 배열의 누적합과 배열에 담기는 값이 다른 거이다. 혹시 O 위치의 담길 값이 ---->를 다 더한 값이라고 생각할 수 있다. 그건 틀렸다. ----------->O우린 1,1,를 좌상 꼭지점으로 O을 우하 꼭지점으로 삼는 직각삼각형의 합으로 생각해야 한다.합을 화살표 표시하고 그림으로 나타내면 아래와 같다------ --->O 위 그림을 보면서 배열에 들어가는 값을 이해해보자.빨간색 위치에 배열값은 초록색 + 파란색 - 노란색(겹치는 부분)이다. 이 공식으로 배열을 채우면 된다. .. 2024. 6. 12. [백준 11659] 구간 합 구하기 4 / 자바 / 누적합 문제 레벨: S3알고리즘: 누적합풀이시간: 16분힌트 참조 유무: 무https://www.acmicpc.net/problem/116591 번째 시도 문제를 보고 엥 이거 너무 기초적인 문제 아니야? 라고 생각했다가 제한을 보고 생각을 바꿨다. 100,000(N의 최댓값) x 100,000(M의 최댓값) = 100,000,000,000(1억 초과)이기 때문에 O(n^2) 시간복잡도로는 풀 수 없다. [아이디어]O(N) 시간복잡도를 생각해봤다. 한번에 탐색으로 1 ~ arr[i]까지 담길 배열을 만드는 것이다. 만약 3~5까지 합을 구하고 싶다면 5인덱스에 있는 값(1~5) - 2인덱스에 있는 값(1 ~ 2)로 구하면 되는 것이다.import java.util.*;import java.. 2024. 6. 12. [백준 2133] 타일 채우기 / 자바 / dp 문제 레벨: G4알고리즘: dp(업데이트 기준x + 일차원 배열)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/21331 번째 시도 확실히 dp는 고급 알고리즘이다. 이 만큼 내 머리를 아프게 하는 알고리즘은 없다. 전에도 말했지만 dp의 시작은 점화식을 세우는 것이고점화식을 세우는 것은 직접 예시를 구해보는 것이다. 그리고 그 사이에 관계를 찾아내는 것이다.이문제는 너비가 4이후부터 특수모양의 경우의 수가 2개 생긴다는 것을 기억해야 한다.아래 링크에서 그림을 참고해봐라.찾아본 것 중 가장 이해가 쉽게 될 그림이다.https://january-diary.tistory.com/entry/BOJ-2133-%ED%83%80%EC%9D%BC-%.. 2024. 6. 11. [백준 2225] 합분해 / 자바 / dp ** 문제 레벨: G5알고리즘: dp(업데이트 기준 2개 + 이차원 배열)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/22251 번째 시도 [의문점]1. 바로 숫자 N까지 가졌을 때를 구하면 되지 않나? ....N-2,N-1,N 차례차례 누적합으로 구해야 하나? arr[N-1]가 arr[N] 만드는데 영향을 미치나? 2. 바로 K일 때를 구하면 되지 않나? ....K-2, K-1,K 차례차례 누적합으로 구해야 하나? 예를 들어 생각해보자 N = 3 K =3 K가 0인 상황을 먼저 구해보자면arr[0] = 0arr[1] = 0 arr[2] = 0 arr[3] = 0K가 1인 상황을 먼저 구해보자면 arr[0] = 1 {0} arr[1] = .. 2024. 6. 10. [백준 2294] 동전2 / 자바 / dp 문제 레벨: G5알고리즘: dp(업데이트 기준 1 개)풀이시간: 1시간힌트 참조 유무: 무https://www.acmicpc.net/problem/22941 번째 시도 동전1과는 다르게 dp배열에 만들 수 있는 가지수가 들어가는 것이 아닌 최소한의 동전 개수가 들어가야 한다.동전1과 마찬가지로 업데이트 기준은 1가지이다. dp는 점화식을 세우는 것이 시작이자 제일 중요하다 arr[j] = Math.min(arr[j], arr[j - coin[i]] + 1);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;public class Mai.. 2024. 6. 9. [백준 11054] 가장 긴 바이토닉 부분 수열 / 자바 /dp 문제 레벨: G5알고리즘: DP풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/110541 번째 시도 위 문제는 LIS와 LDS 합친 문제이다.참고로 LDS는 LIS를 거꾸로 구현하면 된다.[1. LIS 구하는 법: O(N^2)]dp배열에는 LIS 순서가 담긴다.dp[i]를 구할 때마다 i-1까지 탐색한다.// N은 배열의 크기for (int i = 0; i [2. LIS 구하는 법: O(NlogN)]dp배열에는 LIS 원소가 담긴다.아이디어 컨셉: 숫자마다 간격이 좁을 수록 가장 긴 LIS이다.원본 배열을 탐색할 때마다 이분 탐색(O(logN))을 해야한다. 그래서 O(NlogN)이다int len=0; int idx=0; for(int i=0;.. 2024. 6. 8. [백준 12865] 평범한 배낭/자바/dp ** 문제 레벨: G5알고리즘: DP ( dp 업데이트 기준 2개 + 이차원 배열)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/128651 번째 시도 시작에 앞서, 이 알고리즘을 이해하기 힘들 것임을 미리 말한다. 배열에 들어가는 것이 행과 열이 일치하는 값이 아니라 기존까지 구했던 것 중에서 최적의 답, 최대값(누적값)이 들어감을 알아야 한다.이 문제는 배낭 문제(knapsack)로 매우 유명한 문제다. 문제 설명처럼 배낭에 넣을 수 있는 최댓값이 정해지고 해당 한도 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 것이다. 즉, 조합 최적화 문제다. 배낭문제, 일명 냅색 알고리즘은 크게 두 가지 문제로 분류 될 수 있는데, 짐을 .. 2024. 6. 6. [백준 2293] 동전1 / 자바 / dp 문제 레벨: G4알고리즘: dp ( dp 업데이트 기준 1개 + 일차원 배열)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/22931 번째 시도 [잘못된 알고리즘]이문제는 dp문제이다. 왜 dp일까?1원일 때 경우의 수 dp =[1] 2원일 때 경우의 수 = {1,1}(1을 만들 수 있는 경우의 수 x 1을 만들 수 있는 경우의 수) {2,0}(2를 한 번에 만 들 수 있는 경우 수) .. 2024. 6. 5. [프로그래머스 LV3] 연속 펄스 부분 수열의 합 / 자바 / DP 문제 레벨: LV3알고리즘: DP(쉬운버전 / cause: 1차원배열 사용)풀이시간: 1시간힌트 참조 유무: 유https://school.programmers.co.kr/learn/courses/30/lessons/161988 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1 번째 시도 [문제 설명](1) 2 3 -6 1 3 -1 2 4 전체 연속배열 x -1 1 -1 1 -1 1 -1 1 펄스배열----------------------------- -2 3 6 1 -3 -1 -.. 2024. 6. 4. 이전 1 2 3 4 5 ··· 10 다음
