'study money 👺' 카테고리의 글 목록

본문 바로가기

study money 👺

[백준] 2293번 : 동전1 ( 파이썬, 쉬운 설명, 코린이 버전 ) *이 문제가 너무 어려웠던 코린이는 오세요* 디피 자식 ..... 풀어도 풀어도 어려운 너란 유형 .... 자존감 떨어뜨리는 유형 www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 디피 문제를 많이 풀어보고 있지만, 풀이를 들었을 때는 솔직히 이해가 갑니다. 하지만, 아직 까지는 스스로 풀어볼 때, 디피를 적용하는 데에는 제 경험이 딸리나 봅니다. 어쩌겠습니까? 못풀면 그 풀이에 대한 해설을 제대로 익히고, 이해하고. 다음에 못풀어도, 또 경험을 쌓다보면, 디피를 조금씩 더 잘 할 수 있지 않을까요? 우선.. 더보기

[백준] 12865번: 평범한 배낭( 파이썬, 쉬운 설명, 코린이 버전 ) *비범한 배낭 주의 www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 매우 매우 매우 매우 어려운 문제였습니다. 저한테는. 문제 제목이 매우 역설적으로 자괴감 느끼게 하고 ㅋㅋㅋ 누가 이게 디피의 전형적인 문제라고 해서 더 자괴감을 느꼈습니다. 하지만, 자괴감을 느끼는 것도 이제 익숙해서, 저항이 생겨가네요. 많은 시간을 들여서, 결국 이해를 하고 여러분에게 전달드립니다. < 코린이를 위한 쉽게 설명한 핵심 아이디.. 더보기

[쉬운 설명] 백준 1912번 연속합(파이썬, dp) www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 사실 이 문제는 여느 동적프로그래밍 문제에 비해서 너무 너무 쉬운 편이에요. 그렇다고 해도, 제 딴의 풀이를 공유해볼게요. 베이스 아이디어 1. 주어진 정수 리스트에 대한 리스트를 만든다( 흔히 말하는 dp list ) 2. dp의 의미는 이 인덱스 입장에서 취할 수 있는 최대입니다. * 여기가 중요한데요. * 만약, 이 번 인덱스에 주어진 수에 의해서, 이전 인덱스까지의 dp를 감소하게 한다면, 그 이전 인덱스까지의 결.. 더보기

[쉬운 설명] 백준 9251 : LCS( Longest Common Substring ) 길이 찾기 www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 전체적인 이 문제 감상평 : DP문제는 진짜 문제를 많이 풀어봐야겠네요. 솔직히 말해서, 테이블을 만들어서, dp를 진행하는 아이디어를 쌩으로 떠올리기에는 어려움이 많죠. 많이 풀어보면서 감을 익혀야할 것 같아요. 이번 하반기에 코테를 9 ~ 10개를 보면서 느낀 거지만, 변별력을 만드는 문제로 꼭, 이 디피 문제가 나왔어요. 백준에 있는 단계별 풀어보기에 동적 프로.. 더보기

이전 1 다음

티스토리툴바