이분탐색 (Binary search) 이분탐색은 결과적으로 나오는 index의 값을 기준으로 upper_bound와 lower_bound로 나뉜다. 단,이분탐색으로 접근하기 위해서는, 데이터가 연속적으로 이어져있어야 하기때문에 반드시 sorting을 하고 나서 진행해야 한다. 일반적으로 중복되는 수가 없는 경우 중간값이 compare하는 값보다 작을 때는, start부터 mid값까지의 값은 compare하는 값보다 무조건 작을 수 밖에 없으므로 판단해야하는 범위는 (mid + 1, end)로 이동하게 된다. 반면에, compare하는 값보다 클 때는, mid부터 end까지의 값은 compare하는 값보다 무조건 클 수 밖에 없으므로 판단해야하는 범위는 (start, mid -1)로 이동하게 된다. 만약,..

이 문제에서 가장 중요한 지점은, 입출력이 최대 200000 까지 되므로, 빠른 입출력을 활용하여 시간을 출여야 한다. 왜 그렇게 해야하는지에 대해서는 입출력 스트림 관련해서 상당히 복잡하므로, 실력을 키우기 전까지는 그냥 받아들이고 쓰는 것으로 하자. 방법은 다음과 같다. 메인함수에 해당 내용을 최상단에 쓰면 된다. ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 단, 이 방법을 쓰는 경우에는 getchar 같은 것들을 못쓴다는 점은 유의해야 한다. 추가적으로 이 문제의 경우에는, 존재하는지 아닌지만 판단해주면 되므로 정렬 후에 이분탐색으로 판단하는 것이 쉽다. 해당하는 알고리즘으로 코드를 구현하면 다음과 같다. #include #in..

이 문제를 요약하자면 1. 데이터를 받고 2. 자기보다 작은 숫자의 갯수를 출력한다. 라고 볼 수 있다. 즉, 이 문제를 풀기 위해서는 다음의 과정을 겪어야 한다. 1. 정렬을 한다. 2. 자기보다 작은 숫자의 갯수만 카운트 하되, 서로 다른 좌표의 갯수이므로 중복되는 것은 제거한다. 이때, 정렬하는 과정에서 O(nlogn)이고, erase까지 하는데 O(nlogn)가 사용된다. 추가로 자기보다 작은 숫자의 갯수를 전부 다 고려하려면 O(n^2)인데, 이 경우에는 시간 초과가 나므로 이분탐색을 활용해서 진행을 해주면 O(nlogn)이므로 충분히 2초안에 통과할 수 있음을 확인할 수 있다. 위의 방식을 활용하여 코드를 짜주면 다음과 같다. #include #include #include #include u..

이 문제를 보고 분할정복으로 느껴야하는 이유는 다음과 같다. 전체 횟수는 각 배열을 4등분 한 것의 합으로써 구성이 되기에 결과적으로는 각 분할된 것들을 처리해주고 한번에 더해주는 방식으로 몇번째로 방문하는지를 체크해주면 된다. 단, 이 상황에서 시작점의 x좌표와 y좌표를 기록을 하면서 길이를 게속해서 고려해야하므로 재귀함수의 인자에 x좌표, y좌표, 길이가 들어가 있어야 한다. 추가적으로 4개의 조각 중에 어느 곳에 해당하는지를 찾기 위해서 문제에서 주어진 r와 c 값을 parameter로 가지면 된다. Recursion function에서 base case는 length가 2인 케이스를 기준으로 구분해 주면 된다. 해당하는 방법으로 코드를 구현하면 다음과 같다. #include #include #in..

가장 쉽게 생각할 수 있는 것은 브루트 포스이다.(전부 다 해보는 것) Brute force방법으로 하기 위해서는 숫자를 작은 것부터 계속해서 숫자를 키워나가면서 각 랜선을 해당 숫자로 나눈 몫의 합이 n보다 크거나 같으면 계속해서 숫자를 키워나가다가 n보다 작은 타이밍이 오면 그 직전까지의 숫자를 출력하는 방식으로 이해할 수 있다. 다만, 이 방식으로 진행하게 되면 시간초과가 나게 된다. 왜냐하면, 고려해야할 숫자의 범위가 maximum이 최대 랜선의 길이 x k(랜선의 숫자만큼 몫을 구해야하므로)가 된다. 이때 시간제한이 2초이므로 대략 10^8 * 2의 연산을 훨씬 초과한다. 즉, 단순히 연산하는 방식으로는 처리할 수 없음을 파악할 수 있다. 그 다음으로 생각할 수 있는 것은 이분탐색이다. 이분탐색..

python의 경우에는 바로 sort함수를 쓸 수 있는 것과 달리 (Built in function이므로) c++의 경우에는 sort함수가 algorithm 헤더 안에 속해 있으므로 이를 사용하기 위해서는 초반부에 반드시 algorithm을 선언해주어야 한다. 위 함수에서의 인자는 다음과 같다. sort(시작지점의 주소, 끝나는 지점의 주소, (정렬의 기준)) 예를 들어 5칸짜리 int형 배열 test을 첫번째에서 3번째 인자만 정렬하고 싶다면 sort(test, test + 3)를 해주면 된다. 단, 끝나는 지점은 열린구간이므로 그 주소는 포함하지 않는다. 마지막 인자인 정렬의 기준의 경우에는 반드시 포함될 필요는 없으나, 일반적인 기준인 오름차순으로 정렬하지 않는다면 삽입해주어야 한다. 이를 위해서는..

처음에 이 문제를 보고 세운 전략은 string 자료형으로 그룹 단어를 받고, 앞 index부터 바로 앞 단어와 글자가 같으면 pass하고, 다르면 앞 index에서 등장한 문자인지를 확인하여 그룹단어 여부를 확인한다. 다만, 이 상황에서 이미 등장한 문자열을 string자료형에 concat을 시키는 방식으로 코드를 구현하였다. 해당하는 방식으로 코드를 구현한 결과는 다음과 같다. #include #include #include using namespace std; int main(void){ int how_many_repeat; cin >> how_many_repeat; string checker; string non_pass_element; int count = 0; // how many group ..

Python에서는 2의 3승을 그냥 쉽게 2 ** 3으로 나타낼 수 있지만, c++의 경우에는 그러한 방식으로는 제곱승을 처리할 수 없다. 따라서 c++에서는 함수를 활용하여 제곱승의 값을 처리해야 하는데 이를 위해서는 pow 함수를 활용해주면 된다. 반면 제곱근을 구하기 위해서는 두 언어 모두 sqrt 함수를 이용해야한다는 점에서는 공통적이다. 각각의 함수에 대해서 알아보도록 하겠다. 1. pow 함수 사용방법은 다음과 같다. cmath를 헤더에 호출해주고, pow(밑, 진수)를 활용해서 호출해 주면 된다. 2. sqrt 사용방법은 다음과 같다. cmath를 헤더에 호출해주고, sqrt(제곱근을 구할 수)를 활용해서 호출해 주면 된다. 이 중, pow 함수를 활용한 문제를 살펴보도록 하겠다. #incl..