투 포인터 (Two Pointers Algorithm) 투 포인터 알고리즘은 배열/리스트를 탐색하는 알고리즘 중 하나로, 배열에 두 개의 포인터를 두고 위치를 기록하며 계산을 처리합니다. 간단한 문제로 예시를 들어보겠습니다. https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 문제를 보면 배열의 연속된 원소의 합이 M이 되는 경우의 수를 구하라고 합니다. 이 문제는 대놓고 투 포인터를 사용하라고 나와있는 문..
[여러 가지 정렬 1]에 나오는 정렬들 보다는 조금 복잡하지만 더 빠른, 배열을 정렬(오름차순)하는 방법을 알아보자. 1. Merge Sort 배열을 분할하여 각각 정렬하고, 정렬된 결과를 합치는 분할정복(Divide and Qunquer) 방식 주어진 배열을 둘로 나누어 각각 정렬하고, 이를 하나로 합친다. -> 둘로 나뉜 부분 배열은 어떻게 정렬할까? 둘로 나뉜 배열을 또 둘로 나누어 각각을 정렬하고, 이를 하나로 합친다. -> 또 나뉜 배열을 둘로 나누고, ... 길이가 N인 배열을 정렬하기 위해서는 길이가 N/2인 배열을 정렬해야 하고, 또 그 배열을 정렬하기 위해서는 길이가 N/4인 배열을 정렬해야 하고, ... , 결국 길이가 1인 배열을 정렬해야 하는데, 길이가 1인 배열을 정렬하는 것은 너..
배열을 정렬(오름차순)할 수 있는 여러 가지 방법에 대해서 알아보자. 1. Selection Sort 주어진 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬 첫 번째 과정에서 가장 작은 데이터를 찾아 배열의 첫 번째 자리에 넣고, 두 번째 과정에서 그 다음 작은 데이터를 찾아 두 번째 자리에 넣고, ... n-1자리까지 반복한다. n개의 데이터에서 가장 작은 데이터를 찾고, n-1개의 데이터에서 가장 작은 데이터를 찾고, 그 다음은 n-2개, n-3개, ... 이렇게 이어지기 때문에 O(N^2)의 시간복잡도를 가진다. public void selectionSort(int[] arr) { for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j ..
