wonseok.log wonseok.log

이 글은 C++로 풀이를 작성하였습니다. 문제 예시 풀이 이 문제를 3중 for문을 사용하면 합을 구하고 합이 존재하는지 판단하여 시간복잡도가 O(N4)이기 때문에 시간초과가 발생하게 됩니다. 마지막 합이 존재하는지를 이분탐색을 사용하더라도 시간복잡도가 O(N3logN)이라서 시간초과가 불가피합니다. 문제를 해결하기 위해서는 이분탐색을 사용하되, 새로운 기법을 활용해야 합니다. 즉 2개의 숫자의 합을 하나의 배열을 만듭니다. 이 때의 시간복잡도는 O(N2)입니다. 이후 처음 배열의 두 개의 차이가 2개의 숫자의 합 배열에 존재하는지 확인하면 됩니다. O(N2logN)으로 해결할 수 있습니다. ex) a1+a2+a3 = a4 ->, a4 - a3 = a1+a2 #include #include #includ..

이 글은 C++로 풀이를 작성하였습니다. 문제 예시 풀이 이 문제는 이분탐색을 활용한 Parametric Search 알고리즘을 사용해야 합니다. 1부터 최대 길이를 양쪽으로 하여 절반씩 길이일 경우에 원하는 랜선의 갯수가 되는지 확인하여 s와 e를 조정합니다. #include #include #include using namespace std; int main(){ int n,k; cin>>n>>k; int arr[10000]; for(int i=0;i>arr[i]; } long long s = 1; long long e = 1; for(int i=1;i

이 글은 C++로 풀이를 작성하였습니다. 문제 예시 풀이 처음 생각했을 때 정렬 후 map을 통해 중복제거하고 값을 key로 0부터 하나씩 담기는 count를 value로 하여 추가한 풀이를 작성하였습니다. 이렇게 하면 map은 insert의 시간복잡도는 O(logN), 이후 정렬에 대한 시간복잡도 O(NlogN)이 걸려 전체 수에 대해서 탐색할 때의 시간복잡도는 O(N2logN)입니다. 다음 풀이는 무조건 시간초과가 나타나게 되는데 map이 아닌 unordered_map을 사용하면 이진 검색 트리가 아닌 해쉬 테이블로 구현이 되어 O(1)만에 통과할 수 있습니다. #include #include #include #include using namespace std; int main(){ int arr[1..

이 글은 C++로 풀이를 작성하였습니다. 문제 예시 풀이 다음 문제는 이분탐색으로도 해결할 수 있습니다. 해당 수열을 정렬 후 처음 인덱스부터 끝까지 탐색을 하되 해당 인덱스의 값보다 M이 큰 값을 이분탐색을 하여 삽입할 인덱스를 찾을 수 있습니다. 즉, 정렬을 무너뜨리지 않고 해당 값을 추가할 인덱스(lower_bound)를 반환합니다. 하지만, 투 포인터 라는 알고리즘을 사용해서 풀이를 하려고 합니다. 이 문제에서 투 포인터를 사용하면 정렬할 때 O(NlogN)과 수를 고르는 방법 O(N)으로 시간복잡도는 O(NlogN)이 됩니다. #include #include #include using namespace std; int main(){ int arr[100000]; int n,m; cin>>n>>m..

이 문제는 C/C++로 풀이를 작성하였습니다. 문제 예시 풀이 부분합을 구하는 방법을 3중 for문을 이용해서 하나씩 덧셈을 하여 s를 넘었는지 확인하는 방법이 기본적으로 떠올릴 수 있습니다. 그리고 부분합 구하는 방법을 조금 배우신 분이라면 새로운 배열을 만들어 처음부터 해당 인덱스까지의 원소들의 합을 나타내는 배열을 만듭니다. 이후 2중 for문을 이용하여 sum(j) - sum(i)가 s가 넘었는지 확인하면 시간복잡도를 낮출 수 있습니다. 하지만 N의 크기는 10만이라 O(n2)이여도 시간초과가 발생하기 때문에 투 포인터 라는 알고리즘을 사용해서 풀어야 합니다. 투 포인터 를 사용하면 O(N)으로 해결할 수 있습니다. #include #include #include using namespace st..

이 글은 C++의 Next_permutation API 사용법입니다. Next_permutation C++에서 순열과 조합을 구현하기 위해서 대표적인 방법으로 백트래킹(backtraking) 기법을 사용합니다. 백트래킹 기법을 이용하는 것 이외에도 C++에서는 순열, 조합을 구현하기 위한 API인 Next_permutation 함수가 존재합니다. 보다 빠르게 작성할 수 있기 때문에 순열, 조합으로도 충분히 통과할 만한 문제인 경우 다음 API를 사용하면 좋습니다. next_premutation 함수를 사용하기 위해서는 #include을 선언하여야 합니다. Example int main(){ int arr[3] = {3,1,2}; sort(arr, arr+3); /** 1 2 3 1..

c++ STL 중 하나인 Deque에 대한 설명입니다. Deque Deque는 Double-ended queue의 약자로 양쪽 어디에서든 추가, 삭제가 가능한 구조인 큐입니다. Queue 에서는 원소를 접근하기 위해서 front를 통해 하나씩 가져왔다면, Deque는 iterator와 index 접근이 모두 가능합니다. push_back, push_front, pop_back, pop_front와 같은 API를 사용하여 어디에서든 추가가 가능하고 front, back 함수를 통해 원소를 쉽게 가져올 수 있습니다. API 형태나 index 접근이 가능한것만 보면 Queue 보다는 Vector의 형태처럼 보이고, 오히려 vector보다 양쪽 끝 원소는 쉽게 가져올 수 있기 때문에 상위호환처럼 보일 수 있습니..

이 글은 c++로 풀이를 작성하였습니다. 문제 예시 풀이 거꾸로 뒤집는 함수를 실제로 수행하지 않고 거꾸로 뒤집었을 경우는 맨 뒤의 원소 반환, 원래 순서일 때는 앞의 원소 반환으로 바꾸면 됩니다. deque를 사용하여 맨 앞의 원소와 맨 뒤의 원소를 쉽게 접근할 수 있습니다. 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.