서론지난 포스팅에서는 다이나믹 프로그래밍을 이용한 문제풀이를 했다. 이번에도 dp를 이용한 문제를 풀 것이다. 원래 그리디를 이용해서 풀어야 되는데, 아무리 생각해도 그리디는 방법이 떠오르지 않는다. 하루를 이걸로 보낸 거 같다. 물론 책상에서 이거만 처다본건 아니지만 말이다. 이번 포스팅에서는 dp를 이용해 평범한 배낭(안 평범 하잖슴~) 문제를 파이썬을 이용해 풀어보도록 하겠다. BOJ 12865 문제는 여기로 가면 된다. BOJ12865 풀이 과정일단 문제 이해는 쉽다. 각 물품마다 가치와 무게가 있는데 k무게 안에서 가치가 가장 큰 물품들의 가치 총합을 알아내는 것이다. 주의해야 할 것은 우리가 가치가 큰 순서대로 넣는다거나, 혹은 무게가 작은 순서대로 정렬을 하는 것은 쓸모가 업다는 것이다. 문..

서론 지난 코딩 포스팅에서는 백준 2566을 풀었다. 이번 포스팅에서는 다이나믹 프로그래밍(DP)을 이용한 1로 만들기를 풀어보고자 한다. 난이도는 백준 실버3에 해당한다. 풀이 과정에 대해서 설명을 하고 하단에는 BOJ 1463 코드를 첨부하겠다. 다이나믹 프로그래밍에 대한 포스팅을 보려면 아래 포스팅으로 가면 된다. 다이나믹 프로그래밍 DP 알고리즘 파이썬 코딩테스트 (11)목차  서론지난 포스팅에서는 그리디 Greedy 문제인 로프 문제를 포스팅했다. 풀긴 풀었지만 고전했기에 아쉬웠던 문제였다. 아무튼 오늘은 DP 문제를 풀어보고자 한다. DP는 다이나믹 프로그래quiseol.com 백준1463, 1로 만들기 풀이 과정비슷한 문제로는 피보나치 문제가 있다. 피보나치는 단순 재귀로도 구현 가능하다. ..

서론때는 올해 1월, 나는 예쁜 쓰레기'통'에 꽂혔다. 분명 오래된 브랜드고 다양한 국가에서, 높은 가격으로 팔고있음에도 구글링이나 유튜브에 후기라는것이 별로 없었다. 한국에서만 유행인가보다 싶다. 난 이런 쓰레기통에 꽂혔다. 바이럴에 걸려들은게 맞겠다. 살다보니 별 일이 다있다. 쓰레기통이라니. 그런데 한국에서는 비싼 가격대에 형성이 되었음에도 품절이라 예약을 하란다. 하지만 이미 마음만은 저걸 산 상태다. 우리집에 없을 뿐, 이 글을 쓰는 지금 돈도 내 마음도 어디에 있는지 모르는 그 쓰레기통과 함께하고 있다. 결론적으로는 샀다치고 전법을 사용중인 것이다. 그런데 내 방에 있는 가구들이 거슬리기 시작했다. 저 근처에 내 쓰레기통이 있을때의 이질감이 눈에 선하기 때문이다. 그래서 마이 브랜뉴 쓰레기통의..

서론친오빠가 여행을 다녀오면서 분쇄 원두를 사왔는데 집에 묵혀두고 있었다. 그런데 유튜브 알고리즘을 탄 동영상에서 원두 커피를 내리는 레시피를 보았다. 그리고 가성비로 유명한 제품을 알려줬는데 집에 있는 커피보다 더 싼거였다. 이걸 안산다면 집에 있는게 묵히는게 될테고 경험값이라면 충분하다는 판단하에 하리오 V6를 구매하게 되었다.하리오 V60 핸드드립 세트하리오 V6 핸드드립 세트에는 1.계량스푼 2. 여과지(40개) 3.드리퍼(플라스틱) 4. 서버(강화유리)가 들어있다. 쿠팡에서 주문했는데, 로켓배송 받고 16,400원이니까 거진 다이소급 가성비라고 판단된다. 로켓배송 버프로 설 연휴 직전 시켰는데 다음날인 공휴일에 도착했다. 그래서 가족들과 잘 나눠먹었다.핸드 드립 레시피이걸 사게 만든 영상에서 얻..

서론나는 원래 동아 크로닉스 3색펜을 쓴다. 리필심이 싸서 한번에 40~50개씩 쟁겨두면 든든하기 짝이 없기 때문이다. 이걸 만난게 2022년 하반기인데, 어느날 고무 그립 부분이 헐거워졌다해야되나.. 아무튼 잡는 순간 느낌이 드러웠다. 2.5년정도 쓴 셈인데 이정도 쓰니까 저렇게 된 것이었다. 그리고 어쩌다가 한번 떨궜는데 촉 부분 플라스틱이 살짝 날라가 버렸다. 당장은 쓸 수 있지만 바꿔야 될 때가 온 것이다. 결론적으로는 제트스트림 퓨어몰트 2+S를 구매했다. 가격은 배송비까지 13,100원이었다.제트스트림 퓨어몰트 2+S 구매 이유제트스트림 퓨어몰트 2+S를 선택했다. 2색+샤프가 있다는 건데, 사실 난 샤프가 필요 없다.. 그냥 3색으로 주지 2색에 샤프라니. 하지만 아무리 뒤져봐도 선택지가 없..

서론지난 포스팅에서는 백준 1316을 풀어보았다. 해당 포스팅이 궁금하다면 여기로 가면 된다. 이번에는 그거보다는 쉬운 백준 2566 문제를 풀어보고자 한다. 브론즈3에 해당한다. 이번 포스팅 역시 지난 포스팅과 같이 처음에는 문제에 대한 설명과 접근 방식을 얘기하고, 이후에는 접근 방식을 구현한 코드를 작성할 예정이다.백준 2566 풀이 과정9*9 격자판에 0 혹은 자연수가 등장한다고 한다. 최댓값을 찾고 몇 행 몇 열에 위치한 수 인지 구하라고 한다. 딱 문제를 보자마자 든 생각은 최대값을 업데이트해주면서, 갱신될 때마다 해당 행, 열을 따로 저장하면 된다는 생각이다. 인풋의 꼬라지를 보면,3 23 85 34 17 74 25 52 6510 7 39 42 88 52 14 72 6387 42 18 78 ..

서론오늘부터 차근차근 백준 문제를 풀어보고자 한다. 오늘 풀어볼 문제는 백준 1316이다. 이 문제는 실버 5에 해당하고 정답률은 현재 기준 58.855%다. 리스트를 사용한 문제로 리스트 관련 포스팅은 여기로 가면 되며, 문제를 직접 보고 싶다면 여기로 가면 된다. 백준 링크를 걸어 놓았다. 이번 포스팅에서는 어떻게 접근했고, 코드는 어떻게 했는지 적을 예정이다.  백준 1316 풀이과정 연속해서 나타나는 경우에서 연속의 정의가 애매해서 처음에 뭐지 싶었는데 여기서 연속이라함은 a,b,c와 같은 알파벳의 연속이 아니라(하지만 이 역시 문제로 충분히 나올법하다.) 기존에 사용된 알파벳이 있는지에 대한 연속 여부다. 그래서 abd인 경우는 연속, aaza는 불연속이다. 아무튼 난 이 문제를 보고 크게 세가..