알고리즘 오답노트 (~23.6.25)
2023. 6. 25.
이전 글들까지는 문제 하나 하나를 어떻게 풀었는지 정리해왔다. 그런데 점점 풀이를 직접 생각해낼 수 없는 문제들이 늘어나면서 기록에 대한 관점을 바꿔야겠다는 생각이 들었다.
한 번 못 푼 문제는 시간이 지나서 다시 풀려고 하면 또 못 풀 가능성이 있다. 그러니 기록해놓고 종종 들어와서 다시 풀어보자는 생각이다. 한마디로 오답노트다. 그래서 앞으로는 문제 자체에 대한 설명은 최소한으로 하고, 어떤 방법을 사용했는지와 참고한 링크는 무엇인지를 기록해나갈 것이다.
Baekjoon Online Judge - 12865. 평범한 배낭
유명한 문제다. 동적계획법으로 푼다. 그런데 점화식을 스스로 생각해내기가 어려웠다. 괜히 유명한 문제가 아니다 싶다.
풀이 참고
- [알고리즘 트레이닝] 5장 - 동적계획법과 냅색(Knapsack) (백준 12865번 평범한 배낭 문제로 살펴보기)
- Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem)
▲ 풀이 코드
✖ 닫기
Baekjoon Online Judge - 10986. 나머지 합
누적합을 사용한다. 라고 하는데 뭐야 이거 어떻게 누적합으로 푸는 거야? 라고 끙끙 싸맸던 문제다. 알고 보니 "나머지"와 관련된 수학적 응용이 필요했다.
풀이 참고
▲ 풀이 코드
✖ 닫기
BOJ Book - 세그먼트 트리 (Segment Tree)
바로 위 문제를 어떻게 풀어야하지 하고 해메다가 우연히 본 문서다. 세그먼트 트리에 대해 자세히, 시각 자료와 코드를 통해 잘 설명하고 있다. 그리고 관련 문제들의 링크도 포함되어 있다.
관련 문제
2042. 구간 합 구하기
▲ 풀이 코드
✖ 닫기
11505. 구간 곱 구하기
▲ 풀이 코드
✖ 닫기
10868. 최솟값
▲ 풀이 코드
✖ 닫기
2357. 최솟값과 최댓값
▲ 풀이 코드
✖ 닫기
14428. 수열과 쿼리 16
▲ 풀이 코드
✖ 닫기
14438. 수열과 쿼리 17
▲ 풀이 코드
✖ 닫기
Baekjoon Online Judge - 25682. 체스판 다시 칠하기 2
누적합을 사용한다. 라고 하는데 뭐야 이거 어떻게 누적합으로 푸는 거야? 라고 또, 끙끙 싸맸던 문제다. 풀이 방법을 찾아 보니 "조금 더 고민했으면 풀 수도 있지 않았을까?" 싶었다.
풀이 참고
▲ 풀이 코드
✖ 닫기