전체 글145 [백준 11728] 배열 합치기 / 자바 /투 포인터 문제 레벨: S5알고리즘: 투 포인터풀이시간: 30분힌트 참조 유무: 무https://www.acmicpc.net/problem/117281 번째 시도 1. 두 개의 포인터가 각각의 패열 최근 원소 지목하기2. 포인터가 지정하는 값들 비교해서 작은 값 넣기 import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); String.. 2024. 6. 14. [백준 1806] 부분합 / 자바 / 투포인터 && 누적합 문제 레벨: G4알고리즘: 투포인터 && 누적합풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/18061 번째 시도 입력값을 보면 O(NS)의 시간복잡도는 안 된다는 것을 알 수 있다.그렇다면 가능성 있어 보이는 건 최대 O(NlogN) 정도이다.(일종의 꼼수) 여기서 얻을 수 있는 점은 배열을 1 ~2번 순회(적은 순회라고 생각하면 됨)정도로 답을 구해야 한다. [아이디어]나는 한 번의 배열 순회로 알아낼 수 없을까 라는 생각에서 출발했다.배열을 전부 순회할 때까지 이 과정을 반복한다.1. 15이하라면 다음 숫자를 합에 포함시킨다.2. 15이고 기존 값보다 작다면 값을 갱신한다.3. 15이상이라면 시작숫자를 합에서 제외시키고 시작숫자+1을.. 2024. 6. 13. [백준 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. 이전 1 2 3 4 5 ··· 17 다음
