본문 바로가기

알고리즘

 (60)
백준(BOJ) 1495: 기타리스트 https://www.acmicpc.net/problem/1495 곡=아이템, 볼륨=무게 와 대응된다는것을 눈치채지 못했다. 왜? 0-1배낭문제는 dp의 안에들어가는 것이 보석의 가치이지만 기타리스트 문제에서는 dp안에 들어가는 값을 무엇으로 해주어야 할지 막막했다. 구하라고 하는 것이 최대볼륨인데 볼륨을 그냥 X축으로 사용해 버리리라고는 생각도 못했다.(문제를 정리해 나아가야 한다) 이문제는 점화식이라고 할게 없다. 그저 가로축, 세로축에 각각 어떤소재가 들어가는지 그리고 dp의 각 슬록값이 무엇이 되는지가 더 중요하다.(하지만 최적해를 구성하는데 부분해가 간접적으로는 쓰이고 있다) 점화식보다는 이것들을 파악하는 것이 더 중요한 문제가 있다. 그게 이 문제다. 문제를 정리해 나가야 한다. 어떻게 해서든..
백준(BOJ) 2579: 계단 오르기 https://www.acmicpc.net/problem/2579 이 문제를 풀게 되면서 하게 되는 생각이지만 2개이상의 선택지 중에 선택을 해야 하는 상황이 오면 DP는 탐욕적 알고리즘의 사고를 포함하게 된다. (이것은 0-1배낭문제 등 여러문제에서 확인할 수 있다) (아래는 0-1배낭문제 에서 나온 말이다. 2개이상의 선택지 중에 최선을 선택해야 하는 상황이 0-1배낭문제에는 존재하고 dp[i][j]는 그때의 무게에서 배낭에 넣을 수 있는 최대가치가 들어가게 된다. ) (나는 가끔가다 0-1배낭 문제에서 이런 걱정을 하곤한다. 점화식으로 dp 테이블을 채워나가던중 중간단계쯤에서 어떤 아이템이 등장하고 그 아이템의 무게는 이전 아이템들에 비해 정말 가볍고 가치는 엄청나다. 그런데 그 가벼운 무게를 담을..
백준(BOJ) 1904: 01타일 https://www.acmicpc.net/problem/1904 무조건 "나는 답을 모른다. 하지만 정답은 어찌됐든 최적의 원리가 적용되어 최적해는 부분해를 이용하여 이미 정의되어 있다"는 것을 기억하고 최적해를 부분해로 정의하기 위해 관계를 찾기 위해 그림도 그리고 그림간의 관계를 살피기 위해 시간을 써야 한다는 것이다. 일종의 영감은 어찌 됐든 그 후다. 이 문제에서 영감이라 함은 0두개가 붙어있으므로 길이가 2인 "00" 타일하나와 길이가 1인 "1"타일 하나, 총 2종류의 타일만이 존재한다는 것이다. 이는 곧 An은 An-1에서 앞에 "1"블럭 하나를 더한 경우와 An-2에서 앞에 "00"블럭 하나를 더한 An=An-1+An-2와 같은 점화식을 생각할 수 있게구나 하는 생각으로 이어진다. DP문..
백준(BOJ) 11726: 2×n 타일링 https://www.acmicpc.net/problem/11726 최적해의 부분해가 또다시 그것의 부분문제의 최적해가 되는 점화식을 쉽게 찾을수 있어 하급문제다. 왜 이와 같은 점화식이 성립할까? 물론 일일히 다 그려가면 왜 가능한지 알수 있지만 글로 풀자면 애초부터(N=1, N=2일때)다른 모양의 타일을 쌓는데서 시작하므로 타일의 모형은 서로 겹치지 않게 되는 것이다. 이문제에 관련된 해설이 넘쳐나는데 그거 보고 있자면 혼동만 가중된다. 분명 나는 훗날에 이 문제를 다시 보고 다른 문제와 비교할 것이다. 그 때 문제들을 잘 정리하기 위해선 기준이 필요하다. 지금 생각하는 이 기준이 나중에도 맞다고 생각할지 모르겠지만 그래도 글로 남겨본다. "부분해로 이루어지는 최적해의 점화식을 찾아야 한다. 그럼 부..
S-algo10 동적프로그래밍(1) countSum 보호되어 있는 글입니다.
S-algo10 동적프로그래밍(1) howSum 보호되어 있는 글입니다.
(풀어야함), 기말 문제 중복 문자 제거하기 B. 중복 문자 제거하기 - 탐욕적 알고리즘으로 해결하는 문제 * 전수조사하기에는 경우의 수가 너무 많음 def solve(S, included, i, freq, done, ret): if i == len(S): ret.append(''.join(S[i] for i in range(len(S)) if included[i])) return included[i] = False if S[i] in done: solve(S, included, i+1, freq, done, ret) else: if freq[S[i]] > 1: freq[S[i]] -= 1 solve(S, included, i+1, freq, done, ret) freq[S[i]] += 1 included[i] = True done.add(S[i]..
leetcode[735] Asteroid Collision https://leetcode.com/problems/asteroid-collision/ 735. Asteroid Collision(행성 충돌) import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Deque; import java.util.LinkedList; import java.util.stream.Collectors; public class Main { public static Deque solve(int[] asteroids) { Deque deque = new LinkedList(); for(var ast: asteroids){ boolean flag = t..

티스토리툴바