티스토리

늅이컵이

검색하기

블로그 홈

늅이컵이

kirbnewbie.tistory.com/m

컵이의 PS 공부

구독자: 9

방명록 방문하기

주요 글 목록

파라메트릭 서치(Parametric Search) 오늘은 파라메트릭 서치입니다. 이진 탐색을 응용하여 최적화 문제를 결정 문제로 바꾸어서 풀이하는 방법입니다. 사실 문제 상황을 살짝 변형하여 이진 탐색을 사용하는 것일 뿐입니다.. [백준 1654: 랜선 자르기] 문제를 통해 파라메트릭 서치가 무엇인지 알아봅시다. 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는.. 공감수 3 댓글수 2 2021. 3. 18.
완전 탐색(Brute-Force Search) / 이진 탐색(Binary Search) 오늘은 완전 탐색과 이진 탐색에 대해 다뤄볼까 합니다. [완전 탐색(Brute-Force Search)] 사탕 바구니에 10개의 사탕이 들어있다고 합시다. 그중에 포도 사탕을 찾아서 먹고 싶은데, 포도 사탕을 어떻게 찾아야 할까요? 답은 어렵지 않습니다. 하나씩 꺼내서 포도 사탕인지 확인해보면 되겠죠. 이러한 탐색 방법이 완전 탐색입니다. 모든 요소에 대해 자기가 찾고자 하는 대상인지 확인해보는 방법이죠. 그럼 이 방법이 어떻게 프로그래밍에서 쓰일까요? [0,3,2,5,6]의 배열이 주어집니다. 여기서 5가 몇번째 수인지 알고 싶은데, 어떻게 해야할까요? 답은 간단하죠. 4번째 수입니다. 처음의 수부터 비교하여 언제 5가 나오는지 찾아내면 쉽게 알 수 있겠죠. 이것을 프로그램으로 만든다면 다음과 같습니다.. 공감수 3 댓글수 3 2020. 9. 27.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.