PS 1000문제 도전기 - 2일차 [백준]

오늘 공부한 내용 & 푼 주요 문제

1629 - 곱셈(실버 1)

https://www.acmicpc.net/problem/1629

오랫동안 이해하지 못했던 문제. 책을 보고 그제서야 이해하고 풀었다. 분할 정복이라는게 뭔가 쉬우면서도 어려운거같다.

 

12865 - 평범한 배낭(골드 5)(업로드됨)

https://www.acmicpc.net/problem/12865

주어진 무게의 최솟값을 맞추며 가치를 최대로 이끌어내는 문제. 이 또한 문제점을 오랫동안 찾지 못했던 문제이다. 내 풀이가 dp인줄 알았으나 완전 탐색이어서 dp의 형태로 변형하여 풀이를 이끌어냈다. dp의 개념을 잘못 알고 있었던거 같기도 하다.

 

15654 - N과 M (5)(실버 3)

https://www.acmicpc.net/problem/15654

백트래킹을 이용하는 문제. 앞 번호의 n과m을 기이한 방법으로 풀어왔는데 이번에는 정석대로 푸는 방법을 익혀보았다. dfs를 이용한 백트래킹으로 단순하게 풀린다.

 

11660 - 구간 합 구하기 5(실버 1)

https://www.acmicpc.net/problem/11660

사각형의 합을 구하는 문제. 누적합은 알았으나 직사각형으로 확장해 적용하는건 생각하지 못했다.

 

12851 - 숨바꼭질 2(골드 4)(업로드됨)

https://www.acmicpc.net/problem/12851

숨바꼭질 1(1697)의 변형 문제. 최솟값뿐만 아니라 경로의 개수도 세야하기에 visited를 잘 체크해줘야한다.

 

1026 - 보물(실버 4)

https://www.acmicpc.net/problem/1026

간단한 그리디 알고리즘. 가장 큰것과 작은것을 순서대로 곱해 나가면 최솟값이 된다.

 

오늘 푼 잔여 문제

9문제 풀었다.

현황

레이팅: 1088->1111(+23)

푼 문제 수: 431->446(+15)