본문 바로가기

전체 글

 (401)
백준(BOJ) 1932: 정수 삼각형 정수삼각형: https://www.acmicpc.net/problem/1932 기타리스트: https://www.acmicpc.net/problem/1495 정수삼각형문제는 최종 결과값들을 조회할 수 있는 틀이 있다. 하지만 기타리스트 문제는 최종 결과값들을 조회할 수 있는 정수삼각형 문제에서말하는 그 틀이 없고 입력으로 주워지는 최댓값이 있어 제한될 수 있는 범위라는 것이 있고 그 범위를 조회하면 답이 구해진다. 위에서 말하는 정수 삼각형 문제에서 틀이라는 것은 아래 그림과 같이 1,2,3,4,5...n 행을 거치는 누적 값들이 결국은 최하위행의 열중 어느 하나의 열에 결국은 들어가게 된다는 것이다. 기타리스트 문제는 이런 틀이 없다. 다만 결과로 얻을 수 있는 값을 제한하고 그로부터 조회할 수 있는 ..
백준(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) 9461: 파도반 수열 출처: https://www.acmicpc.net/problem/9461 최적해를 어떻게 하면 부분해를 이용해서 점화식으로 세울수 있을지를 고민해야 한다. 만약 수열이라는 것이 주워지면 문제가 다 풀린것이나 마찬가지다. 최적해와 부분해의 관계를 가진 점화식을 세우기가 한결수월해 진다. 그리고 주워진 그림과 그 수열을 함께 가지고 생각한다면 점화식은 더 쉽게 얻어진다. 처음에는 예외가 존재하지만 나중으로가면 결국은 최적해는 이전의 두개의 삼각형의 변을 합한 것이 된다는 것을 쉽게 찾을 수 있다. 즉 n=6이상에서 점화식은 An=An-1+An-5가 된다. 마지막으로 주의할 것은 자료형이 커버할 수 있는 범위이다. n=100일때 그답은 int 형으로 커버할수 없어 틀렸다고 나왔다.(Overflow나 다른 에러..
백준(BOJ) 11726: 2×n 타일링 https://www.acmicpc.net/problem/11726 최적해의 부분해가 또다시 그것의 부분문제의 최적해가 되는 점화식을 쉽게 찾을수 있어 하급문제다. 왜 이와 같은 점화식이 성립할까? 물론 일일히 다 그려가면 왜 가능한지 알수 있지만 글로 풀자면 애초부터(N=1, N=2일때)다른 모양의 타일을 쌓는데서 시작하므로 타일의 모형은 서로 겹치지 않게 되는 것이다. 이문제에 관련된 해설이 넘쳐나는데 그거 보고 있자면 혼동만 가중된다. 분명 나는 훗날에 이 문제를 다시 보고 다른 문제와 비교할 것이다. 그 때 문제들을 잘 정리하기 위해선 기준이 필요하다. 지금 생각하는 이 기준이 나중에도 맞다고 생각할지 모르겠지만 그래도 글로 남겨본다. "부분해로 이루어지는 최적해의 점화식을 찾아야 한다. 그럼 부..
CQS(Command Query Separation)에 대해서 참고: https://velog.io/@yena1025/CQS-Command-Query-Separation 강의도중 아래와 같은 save메서드에서 왜 반환값을 그냥 회원객체로 반환하는것이 좋지 않은지에 대한 설명이 있었다. 결론만 말하면 save의 기능은 저장의 기능이기 때문에 굳이 회원객체를 반환하여 그 객체를 수정할 수 있는 여지가 아예 없도록 CQS패턴을 적용하여 save메서드를 구현하는 게 좋다는 것이다. 아래는 CQS에 대한 소개이다. CQS는 'Command Query Separation', 즉 Command와 Query를 분리하자는 개념을 말한다. Command는 상태를 변경하는 메서드이며, Query는 상태를 반환하는 메서드를 지칭한다. CQS는 패턴이다 CQS는 디자인 패턴 중에 하나이다..
@PersistenceContext와 EntityManager, 그리고 영속성(Persistence) https://flexyduck.tistory.com/178 https://colevelup.tistory.com/21 이전에 위 링크에서 JPA에 대해서 배웠던 것중 "JPA는 영속성 컨텍스트를 가진다." 라는 특징이 있었다. 정말 이 JPA특징을 생각하면 @PersistenceContext 라는 어노테이션은 오직 JPA의 EntityManageer 클래스만을 위한 어노테이션 같다는 느낌을 받는데 정말 그럴까? JPA와 ORM에 대한 간략한 정의와 JPA에서 중요한 영속성 컨텍스트(Persistence Context)와 엔티티 매니저(Entity Manager), 영속성 컨텍스트 타입(Persistence Context type), 영속성 컨텍스트(Persistence Context)의 장점등에 대해서..

티스토리툴바