힙 정렬이란?최대 힙 트리나 최소 힙 트리를 구성해서 정렬하는 방법으로 기본적으로는 1차원 배열을 사용하여 구현하는 방식이다.내림차순 정렬을 할 때에는 최소 힙 트리를 구성하고, 오름차순 정렬을 할 때에는 최대 힙 트리로 구성한다.힙 정렬 알고리즘의 구현힙은 최상위 루트 노드로부터 시작하는 완전 이진 트리이다. 이 루트 노드에서 왼쪽과 오른쪽으로 각각 노드가 존재하고, 루트 노드를 부모 노드, 왼쪽 및 오른쪽 노드를 자식노드라고 말한다.부모노드의 인덱스가 i라고 한다면 왼쪽 자식노드는 2 * i 위치에 존재하고, 오른쪽 자식 노드는 2 * i + 1의 위치에 존재한다. 이진 트리를 만들면서 최대 힙, 자식 노드를 가지는 부모 노드를 구성해나가면서 점점 루트로 올라오는 순차적 단계를 이용하여 만들어 낼 수..

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=cpp정렬이지만, 조금은 다르다.원래는 왼쪽 기준으로 맨 처음 숫자를 고려해서 큰 수형식으로 배열하는 방식을 생각하였다.하지만 이는 코드상으로 구현하니 굉장히 복잡한 형식이기도 하고, 예외 처리 해야 할 것들이 많이 존재하였다.(ex. 자릿수가 같을 때 숫자비교, 다를 때 짧은 것이 먼저올 수도 있지만, 뒤에 오는 숫자들에 따라 긴 것이 먼저 올 수도 있음)그런 문제점이 존재해 다른 방식으로 이 문제를 풀 수 있었다.숫자들을 string으로 전환하여 각 숫자를 합쳐보았다.3 + 57과 57 + 3을 수행하면 각각 357, 573이 된다.합쳐보았을 때 573이 더 큰 수 이므로..

https://school.programmers.co.kr/learn/courses/30/lessons/42748정렬을 이용하는 문제이다.array의 값을 commands로 주어진 i, j, k값에 따라서 정리한 후, 그에 맞는 숫자를 return해주면 되는 간단한 문제이다. #include #include #include using namespace std;vector solution(vector array, vector> commands) { vector answer; vector temp; for (int n = 0; n

https://www.acmicpc.net/problem/10815 브루트포스 방식으로 모든 숫자 카드들을 비교하면 시간 초과로 해결하지 못하는 문제이다. 시간 단축을 위해 이분 탐색을 활용해 숫자 카드들을 비교할 것이다. 이분탐색은 한 리스트에 있는 데이터들의 탐색 범위를 점점 좁혀나가면서 구분하는 방식이다. 시작 노드 및 끝노드 인덱스를 더한 뒤 2로 나누어 중간 인덱스를 구하고, 그 값과 원하는 타겟값을 비교해서 targer > list[mid]인 경우 시작 노드값을 올리고, 반대인 경우는 끝 노드의 값을 올려가면서 찾는다. 이 이분 탐색은 반복문(while)을 사용한 방법과 재귀를 사용한 방법, 두 가지가 존재하는데 필자는 재귀를 좋아하기 때문에 재귀 방식을 사용하였다. #include #incl..

https://www.acmicpc.net/problem/1253 간단하게 생각하면 모든 수를 하나씩 더해봐서 할 수 있는 간단한 문제이다. 다만, N의 최대값은 2,000인데 시간복잡도에 따라 N^2 or N^3 등등 커질수록 많은 시간이 걸릴 것이다. 그렇게 되면 시간초과에 걸리게 된다. 즉, 이 문제를 풀기 위해서는 그 이하의 시간복잡도를 가지는 알고리즘을 사용하여 문제를 풀어야 한다. 두 개의 합으로 나타낼 수 있는 수를 찾는 문제이므로, 투 포인터 알고리즘을 사용한다. 시작 인덱스 0과, 끝 인덱스 N - 1에서 차례차례 더해서 확인해가며 값을 찾으면 시간복잡도 O(N)으로 값을 찾을 수 있다. 그 작업을 수행하기 위해서는 정렬을 먼저 수행하여 두 수를 더해 그 값을 비교하여 합이 작으면 시작 ..