ORTHODOX

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 사진이 너무 길어질까봐 오늘은 링크를 남깁니다. 안녕하세요 오늘은 이분탐색을 이용하여 문제를 풀어보겠습니다. 전략: 1. string타입의 vector와 int, string을 페어로 하는 pair타입의 vector를 선언해주고, input을 받아줍니다. 2. p를 정렬해줌으로 문자열 순서대로 정렬합니다. 3. 만약 들어오는 것이 index이면, v[index]를 출력..

안녕하세요 오늘은 이분탐색을 이용한 문제를 풀어볼 것입니다. 전략: 1. long long int type으로 vector를 선언해줍주고 입력을 받는다. 2. l(low)를 1로, h(high)를 vector의 최댓값으로 선언해주고, while문을 만든다. 3. while문이 시작되자마자 l가 h보다 크면 while문이 끝나도록 코드를 짜고, long long int타입의 mid라는 변수를 들어서 l, h의 평균을 입력해준다. 4. 나무를 자른 길이를 cnt에 더해주고, cnt가 M보다 크면 max변수와 mid를 비교하여 더 큰 값을 max에 넣어준다. 코드: #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); co..

안녕하세요 오늘은 이분탐색, 매개변수 탐색 알고리즘을 이용하여 풀어야하는 문제를 풀어보겠습니다. 전략: 1. 벡터에 랜선의 길이를 대입하고 sort를 해줍니다. 이때 sort해서 가장 뒤에 있는 원소가 max 변수에 대입됩니다. 2. 매개변수로 l(left), r(right)를 선언해줍니다. l은 1, r은 max로 선언해줍니다. 3. 갖고있는 랜선의 개수를 mid로 나눈 몫의 총합이 K보다 크거나 같으면 result와 sum을 비교해서 더 큰 값을 result에다가 대입해줍니다. 그리고, l = mid+1을 해줍니다. 4. 만약 아니라면 r = mid-1을 해준뒤, 만약 l>r이면 break하도록 if문을 설정해줍니다. 코드: #include #include using namespace std; int..

안녕하세요 오늘은 이분탐색으로 풀면 빨리 풀리는 문제를 풀어보겠습니다. (다른 방식으로 푼 저는 엄청난 메모리와 시간을 맛봤지요 맞긴했지만..) 두가지 방법으로 문제를 풀어보겠습니다만, 2번째 방법을 추천드립니다. 전략1 1. 범위를 확인한 후, 20000001길이의 벡터를 선언해준다(어레이로 선언하면 배열 길이 제한때문에 안된다) 2. x+= 10000000을 해준후, x+1번째 배열의 원소 값에 1을 더해준다. 3. 2번째 입력때 x+= 10000000을 해준다음 그 위치에 있는 원소값을 출력한다. 코드1(내가 한 번에 풀었던 방식): #include #include using namespace std; int main(){ vector arr(20000001); ios::sync_with_stdio..

안녕하세요 오늘은 이진탐색함수 및 정렬함수를 사용하는 문제를 풀어보겠습니다. 전략: 1. 두개의 벡터를 세운다(v, temp) 각각 입력을 받은 벡터, 입력받은 벡터에서 중복값을 삭제시키고 정렬한 벡터 2. 입력을 받는 for문을 세운다. 3. sort함수를 이용하여 sort를 이용하여 temp 벡터를 정렬시켜준다. 4. 정렬된 temp벡터에 erase 함수와 unique함수를 이용하여 중복을 찾아서 지워준다. 5. for문을 작성하고, 그 안에 이진탐색 방법으로 v[i]값들의 위치를 찾는 변수를 선언해서 출력해준다. 코드: #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ..