이진 탐색 검색 결과

해당 글 3건

[BOJ] 1654번 | 랜선 자르기 (C++)

🔗문제 보러가기 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 🧑🏻‍💻풀이 과정 K개의 랜선들을 잘라, 동일한 길이로 N개 이상을 만든 경우의 수들 중 가장 긴 단위 길이를 찾으면 되는 문제입니다. 매개변수 탐색(Parametric Search)을 이용하여 풀 수 있습니다. 사실 매개변수 탐색이란 용어를 오늘 처음 들어봤는데, 내용을 보니 제가 알게 모르게 사용했던 방법이더군요. 알고리즘은 간단합니다. 배열(arr)에 저장되어 있는 K개의 랜선들을 오름차순 기준으로 정렬합니다. ..
🤖Algorithm/BOJ 2023. 9. 2. 18:59

[BOJ] 11053번 | 가장 긴 증가하는 부분 수열 (C++)

🔗문제 보러가기 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 🧑🏻‍💻풀이 과정 최장 증가 부분 수열(LIS) 알고리즘은 저에겐 처음 접해보는 개념이었습니다. 그래서 해당 개념에 대해 먼저 공부하였고, 기존 \( O(n^2) \)의 시간복잡도를 가지는 알고리즘을 이진 탐색(Binary Search)을 활용하여 \( O(nlogn) \)으로 줄이는 방법에 대해서도 알게 되었습니다. (🔗참고 블로그) 방법은 다음과 같았습니다. 최장 증..
🤖Algorithm/BOJ 2023. 8. 29. 16:50

[BOJ] 16139번 | 인간-컴퓨터 상호작용 (C++)

🔗문제 보러가기 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 🧑‍💻풀이 과정 나의 멍청한 실수 이전 문제에서 누적 합을 잘 구해놓고, 여기에서는 왜 적용을 못했나 싶습니다.. 처음에는 DP[26][S.length()] 배열을 선언하여, 각 알파벳마다 등장한 횟수를 누적하여 저장하는 방식으로 접근하였습니다. const int ALPHABET_COUNT = 26; const int LOWER_A_ASCII = 97; string S; vector DP(ALPHA..
🤖Algorithm/BOJ 2023. 8. 27. 17:46