내림차순 정렬된 배열을 뒤집는 행위는 정렬을 다시하면 되지만 리스트의 길이가 짧다면 짧은 코드로 쉽게 구현할 수 있다. 리스트의 왼쪽, 오른쪽 인덱스 변수를 선언해서 줄여나가면서 swap을 하는 로직으로 구현할 수 있다 #include #include using namespace std; void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector v(n); for (int i = 0; i > v[i]; } int left = 0, right = n - 1; ..

정렬 문제라고 되어있지만, 정렬을 이용하지 않아도 해결할 수 있다. N^2개의 조합을 모두 살펴볼 필요는 없는 것이 조합이라고 생각하고 구한 값에서 *2만 하면 된다. 따라서 1억번 연산을 반으로 줄일 수 있다. 문제: https://www.acmicpc.net/problem/2399 깃허브주소: https://github.com/surinoel/boj/blob/master/2399.cpp 위에는 2중 for문으로 해결해서 시간이 어느정도 걸리지만 좀 더 연구를 하다보면 for문 하나로 해결할 수 있다 [참고] https://aerocode.net/231

초반에는 체육복이 없는 사람 기준으로 맨 앞 사람만 탐색하면서 체육복을 가져오고, 다시 뒤를 탐색하면서 체육복을 가져오는 식으로 해결했지만 반례 하나가 존재했다 n=5 lost=[2, 4] reserve=[3, 5] 위 로직으로 진행하면 2는 체육복을 얻지 못하게 된다. 이 문제의 로직은 앞 사람들부터 앞뒤 순서를 탐색하면서 있는 체육복을 가져오는 것이다. 최적의 해같다고 생각이 들지는 않지만 무난한 답이 그리디한 알고리즘이다 문제: https://programmers.co.kr/learn/courses/30/lessons/42862 깃허브주소: https://github.com/surinoel/boj/blob/master/Programmers_체육복.cpp

오름차순 정렬을 가정했을 때, 피봇이라는 기준값으로 왼쪽에는 기준값보다 작은 부분집합을 형성시키고 오른쪽에는 기준값보다 큰 부분집합을 형성시킨다. 분할정복을 이용하기 때문에 lgN의 깊이만큼 재귀호출을 하고, 깊이마다 배열의 길이인 N만큼 비교하기 때문에 총 평균 시간복잡도는 NlgN만에 정렬시킬 수 있다 피봇을 잡는 기준은 다양하며 특정 피봇 위치를 잡았을 때 엄청 좋다라는 것은 없다. 다만 합병 정렬과 달리, 피봇에 따라 비균등하게 부분집합들이 나눠질 수 있기 때문에 unstable-sort로 분류를 한다. 만일 정렬된 배열에 대해서 퀵 소트를 한다고 하면, 퀵 정렬 알고리즘에 따라서 lgN의 깊이가 아닌 N의 깊이만큼 내려가게 된다. 따라서 최악의 시간복잡도 O(N^2)이 나오게 된다 1) 리스트 ..

탐색을 했을 때 lgN만에 찾기 위해서는 트리를 이용해야 한다. C++ 라이브러리에 있는 map을 이용할 수 있다. M 제한이 10만으로 시간복잡도 M*lgN만에 해결할 수 있다. 보다 쉽게 하기 위해서 map을 2개 만들어서 문자와 숫자가 key일 때를 나눠서 해결했다 문제: https://www.acmicpc.net/problem/1620 깃허브주소: https://github.com/surinoel/boj/blob/master/1620.cpp

위치한 알파벳에 대해서 left, right의 개수를 추가한다. 그리고 대문자, 공백에 대해서 rest라는 변수를 둬서 1씩 더해준다. 탐색이 끝나면 left, right의 차가 최소가 되도록하며, 문제 조건에 있듯이 left가 하나 더 크도록만 예외처리를 해주면 된다 문제: https://www.acmicpc.net/problem/17487 깃허브주소: https://github.com/surinoel/boj/blob/master/17487.cpp