전체 글
-
2021 KOI 2차 후기PS일지 2021. 7. 26. 17:30
문제도 잘 기억이 안나고 잘 풀지도 못해서 후기라고 하기에는 좀 뭐하지만 일기장 느낌으로 써보기로 했다 [1. 헬기 착륙장] DP 문제였다. 문제를 처음에 제대로 안읽고 풀어서 답이 조금 이상했는데, 고치고나니 답이 어느정도 나왔다. 처음엔 Naive하게 DP 식을 만들려고 했는데, 테스트해보니 역시 메모리 초과가 났다. 약간의 트릭을 통해 메모리를 줄일 수 있는 방법을 구상해냈고, 90점을 받을 수 있었다. 마지막 10점을 받기 위해서는 전처리를 하면 될 것 같다는 생각이 들었지만, 뭔가 끄적여보다가 그렇게 전처리를 하면 안된다는 결론이 나와버렸다...;; 그래서 90점으로 마무리.. [2. 그래프 균형 맞추기] 문제를 해석하는데 시간이 조금 걸렸는데, 그래프와 연립 방정식을 섞어놓은 듯한 문제였다. ..
-
파라메트릭 서치(Parametric Search)알고리즘 정리 2021. 3. 18. 13:51
오늘은 파라메트릭 서치입니다. 이진 탐색을 응용하여 최적화 문제를 결정 문제로 바꾸어서 풀이하는 방법입니다. 사실 문제 상황을 살짝 변형하여 이진 탐색을 사용하는 것일 뿐입니다.. [백준 1654: 랜선 자르기] 문제를 통해 파라메트릭 서치가 무엇인지 알아봅시다. 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는..
-
완전 탐색(Brute-Force Search) / 이진 탐색(Binary Search)알고리즘 정리 2020. 9. 27. 23:33
오늘은 완전 탐색과 이진 탐색에 대해 다뤄볼까 합니다. [완전 탐색(Brute-Force Search)] 사탕 바구니에 10개의 사탕이 들어있다고 합시다. 그중에 포도 사탕을 찾아서 먹고 싶은데, 포도 사탕을 어떻게 찾아야 할까요? 답은 어렵지 않습니다. 하나씩 꺼내서 포도 사탕인지 확인해보면 되겠죠. 이러한 탐색 방법이 완전 탐색입니다. 모든 요소에 대해 자기가 찾고자 하는 대상인지 확인해보는 방법이죠. 그럼 이 방법이 어떻게 프로그래밍에서 쓰일까요? [0,3,2,5,6]의 배열이 주어집니다. 여기서 5가 몇번째 수인지 알고 싶은데, 어떻게 해야할까요? 답은 간단하죠. 4번째 수입니다. 처음의 수부터 비교하여 언제 5가 나오는지 찾아내면 쉽게 알 수 있겠죠. 이것을 프로그램으로 만든다면 다음과 같습니다..