반갑습니다!

12015번: 가장 긴 증가하는 부분 수열 2 www.acmicpc.net 풀이 LIS 알고리즘 문제이다. 일반적으로 LIS 문제는 동적계획법으로 풀 수 있는 전형적인 문제이지만, 이 문제에서는 N의 최댓값이 1,000,000이므로 다른 방법으로 해결해야한다. 아래의 코드는 이진 탐색을 이용한 LIS 알고리즘이다. C++ STL에 구현되어있는 lower_bound()를 이용해서 해결했다. 코드 #include #include using namespace std; int n; int a[1000001]; vector lis; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; i..

1072번: 게임 www.acmicpc.net 풀이 해당 문제는 이분 탐색으로 해결할 수 있다. mid 값을 '형택이가 앞으로 하게될 게임의 개수'로 잡고 이분 탐색을 하면 된다. 승률 Z는 (Y x 100) / X 로 구할 수 있는데, 이 때 주의해야할 것은 Y x 100이 int 범위를 벗어날 수 있기 때문에 long long형으로 선언해야한다. 코드 #include #include #include using namespace std; long long x, y; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> x >> y; int left = 1; int right = 1000000000; int ans = num..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 효율성 테스트가 있는 문제이다. 따라서 효율성이 중요한 문제인데, 이 문제는 이분탐색을 사용해서 해결할 수 있다. 이분 탐색에서 가장 중요한 것은 '어떤 값을 기준으로 정할 것인가'이다. 아래의 코드에서는 니니트 프렌즈를 번호를 기준으로 했다. m번째 인원이 건널 때 디딤돌의 숫자는 stones[i] - m 이 되고, 이를 통해 건널 수 있는지 없는지를 파악해 이분 탐색해서 해결해주었다. 코드 C++ #include #include #include using namespace std; // m번째 인원이..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제의 조건에 맞춰 구현해주면 되는 문제인데, 구현하기 상당히 까다로운 편이다. '*' 을 처리하기 위해서 이전 점수를 저장했고, 숫자 10을 따로 처리해주었다. 코드 C++ #include #include using namespace std; int solution(string dartResult) { int prev = 0; int num = 0; int sum = 0; bool option = false; bool ten = false; for (int i = 0; i

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 해당 문제는 숫자를 문자열로 변환한 뒤, 문자열끼리 합친 결과를 비교하는 방법으로 쉽게 해결할 수 있는 문제이다. 코드 C++ #include #include #include using namespace std; bool comp(const string& a, const string& b) { return a + b > b + a; } string solution(vector numbers) { string answer = ""; bool is_all_zero = true; // 모든 숫자가 0인지 체크..