알고리즘고찰

배낭 문제는 쉽다! 라고 생각했었다. 워낙 유명한 문제이기도 하고 dp 문제 기본 예제 단골 손님이다... 하지만 직접 풀어보려니 어떻게 점화식을 짜야 할 지 쉽게 떠오르지 않았다. 누구나 맞기전에는 계획을 가지고 있다... ㅠ 디피는 항상 어려운 듯 하다..

https://www.acmicpc.net/problem/1208문제는 여기에 있다.같은 문제인 BOJ 1182번 문제와 비교해서 다른점은 딱 하나인데 바로 N의 개수이다. 2의 40승이니 이것은 브루트 포스로 풀지 못하겠다는 생각을 떠올렸다. 하지만 dp로

🤔 왜 최적화를 못했을까? 백트래킹 대표적인 문제로 백트래킹 구현도 중요했지만, 최적화가 더욱 중요한 문제였다. Pypy3로도 시간초과가 나서 여러 고민을 해보았지만, 방법이 전혀 떠오르지 않았다. 내 생각은 단순하게 반드시 전체 탐색을 해서 전에 탐색한 다음 로

이번 문제는 사실 완전 탐색으로는 해결했지만, 어떻게 메모이제이션을 적용할지 모르겠어서 결국 풀이를 본 문제였다. 그래도 종만북 공부하고 나서는 dp, 완전탐색 문제들을 어떻게 풀어야 할지는 조금은 보인다는 점에서 아주 다행이라고 느꼈다. 하지만 이런 메모이제이션을 적

이 문제를 보고서는 쉽게 이분 탐색이라는 것이 떠오르지 않는다. 입력 값이 워낙 크니까 의심은 해볼 수 있지만 역시 방법은 쉽게 떠오르지 않았다. 심지어 이 문제는 1년전에 풀었던 문제였다..!(그 때도 못풀어서 답을 보긴 했지만) 그 때 당시에 풀지 못해서 대충 넘어

사실 이 문제는 백준에서 먼저 본 것이 아니라 알고스팟 문제를 풀어보려다가 백준 문제도 있나 찾아보았다. 처음 보았을 때는 간단한 문제라고 생각했다, 그래서 재귀적으로 호출해 주면 되겠다라는 생각으로 무작정 문제에 달려들었다. 하지만 InOrder index와 Pre

먼저 문제 링크https://www.acmicpc.net/problem/1738또 내가 작성한 답안 링크이다.https://github.com/Deserve82/KK_Algorithm_Study/blob/master/Kangho/BOJ_1738.py간

사실 간단한 백트래킹 문제였지만, 조합을 탐색해야 하는 데 자꾸 순열을 탐색하는 실수를 했기 때문에 시간초과가 났고, 답이 틀린 것이 아니었기 때문에 어디가 많은 시간이 걸리는 지 찾가기 어려웠다. (나는 조합을 탐색하고 있다고 생각했고, 다른 전처리가 부족해서 생긴

우선 영화 수집 문제를 세그먼트 트리를 이용해 만들어야 하는 것을 알고 문제풀이를 시작했다. 세그먼트 트리를 이용하려고 보니... 이게 왠걸 이게 세그먼트 트리 문제인가도 헷갈릴 정도였다. 이 문제를 풀면서 세그먼트 트리를 활용해야 할 때는 대놓고 "나 세그먼트 트리요

문제 풀이 자체는 간단히 떠올렸다. 각 숫자를 기준으로 그것 보다 앞에 있는 숫자가 더 작으면 그것을 삭제 하는 방법으로 풀었다. 하지만 del을 사용하느라 자꾸 시간초과가 났는데 이것을 개선하려 이것저것 고민해보았지만 테스트 케이스 10번 하나만 계속해서 통과를 하지

위상정렬은 나름 자신있다고 생각하고 있었다. 많은 문제를 풀어보기도 했고 acm craft는 기본 문제라고 생각해서 풀지 않고 있었는데, 오늘 생각이 나서 풀어보았다. 나는 time이라는 전역변수 하나만으로도 문제가 쉽게 해결 될 것이라 생각했지만, 그렇지 않았다. 고

이번 문제는 다른 문제들과 다르게 dfs와 함께 그리디 알고리즘이 결합된 형태의 문제였다. 처음 보는 유형에 많이 당황도 했지만 설마 이 방법으로? 라는 생각에 알고리즘의 정당성을 증명하지 못했다.여기서 그리디 적으로 생각한다는 것은 8방향중에 어차피 갈 수 있는 방향