본문 바로가기

분류 전체보기137

백준 10816번 C++ & upper_bound, lower_bound https://www.acmicpc.net/status?user_id=jjune0461&problem_id=10816&from_mine=1 채점 현황 www.acmicpc.net 이번 문제는 처음에 그냥 생각나는 가장 쉬운 방법은 프루트포스로 시작을 했습니다. 솔직히 난이도에 맞지 않는 것은 확실하지만 그냥 해보았고 역시나 시간초과가 발생했습니다. 그 다음에 생각을 한 방법은 이진 탐색이었습니다. 이진탐색으로 하려고 생각을 하다가 만약에 상황이 다음과 같다고 가정을 해봅시다. 1 2 3 3 3 3 3 3 4 5 이렇게 되어있다면 같고 싶은 값이 3이라고 했을 때 이진 탐색을 통해서 3을 찾는다면 중앙값이 3인데 앞, 뒤로 얼만큼 더 가야하는지 코딩하기가 너무 어려울 것 같다는 생각을 하게되었습니다. 다양.. 2021. 8. 18.
백준 10814번 C++ 이 문제를 완벽하게 이해하고 풀기 위해서 vector cotainer, pair, sort, stable_sort를 공부하였습니다. pair를 제외하고는 다 제 블로그 안에 글들이 있으니 혹시 잘 모르신다면 한번 보시고 문제를 푸시는 걸 추천드립니다. https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 이 문제에서 중요한 사항중에 하나는 sort와 stable_sort의 차이점을 아는 것이 중요했던 것 같습니다. 불안정정렬을 사용할 경우 나이가 같다면 .. 2021. 7. 7.
C++ sort & stable_sort sort는 불안정정렬이고 stable_sort는 안정정렬입니다. 이 두가지의 차이점을 먼저 말씀드리겠습니다. 배열이 다음과 같이 나와있을 수 있습니다. 이게 정렬 전 배열입니다. 같은 숫자는 자신의 앞과 뒤의 순서를 알아볼 수 있도록 색깔을 빨강(선) - 주황(후)로 하겠습니다. 일반적인 stable_sort(안정정렬)은 다음과 같이 정렬이 완성됩니다. 순서가 바뀌지 않고 정렬이 완성이 됩니다. 하지만 정렬이 되지 않은 배열을 sort로 정렬하면 다음과 같이 됩니다. 위의 결과와 같이 먼저 왔다고 해서 배열의 앞순서로 온다는 보장이 없습니다. 그렇기에 불안정정렬이라고 합니다. 물론 78의 순서도 서로 달라질 수 있고 25의 앞, 뒤 순서가 올바르게 될 수도 있습니다. 이러한 요소를 잘 고려해서 코딩을 만.. 2021. 7. 7.
퀵소트 VS 머지소트 C++의 헤더에 있는 sort와 stable_sort를 공부를 하다가 sort의 내부적인 sort인 '퀵소트' vs stable_sort의 내부적인 sort인 '머지소트' 가 궁금해져서 이렇게 알고리즘에 대해 살짝 공부를 해보기로 했습니다. https://penpen.tistory.com/entry/Algorithm-Quick-Sort-Merge-Sort-%EB%B9%84%EA%B5%90%EC%B2%B4%ED%97%98 [Algorithm] Quick Sort, Merge Sort 비교체험 ! 이전글에 계속하여.. Quick Sort vs Merge Sort 알고리즘 수업시간에 귀가 따갑도록 들었던 이 두 정렬방법. 당연히 퀵이 빠른거 아니야? 했지만, 누군가는 데이터가 커질수록 Merge가 좋다하고.... 2021. 7. 7.

티스토리툴바