728x90
투포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.
매우 간단한 알고리즘으로
투포인터 이동 원칙1. 연속된 자연수의 합을 구하는 경우 : 투포인터를 모두 시작인덱스에 셋팅
* sum < N : sum = sum + end_idx; end_idx++;
* sum == N : end_idx++; sum = sum + end_idx; count++;
* sum > N : sum = sum - start_idx; start_idx++;
투포인터 이동 원칙2. 두 수의 합을 구하는 경우 : 투포인터를 양끝에 셋팅
* A[i] + A[j] > M : j--;
* A[i] + A[j] == M : i++; J--; count++;
* A[i] + A[j] < M : i++;
006 연속된 자연수의 합 구하기
//(24.11.26 코드 복기)
public static void main(String[] args) {
//*투포인터 : 2개의 포인터로 알고림즘의 시간복잡도를 최적화함.
//자연수 N을 입력받아 연속된 사연수의 합으로 나타내는 가짓수를 출력하라.(제한시간: 2초)
//입력값
//1: N (1<=N<=10,000,000)
//분석 : 시간복잡도 알고리즘 고르기
//N의 범위가 크므로, O(n)의 시간복잡도 알고리즘 사용하기. (e.g. O(nlogn) 사용하면 안됨)
//O(n) 시간복잡도 = 투포인터 사용하기★
//연속된 자연수의 합이므로, 시작 인덱스, 종료 인덱스를 투 포인터로 지정한 후 문제에 접근!
/******************************************************
* 투 포인터 이동 원칙
* ----------------------------------------------------
* sum > N : sum = sum - start_index; start_index++;
* sum < N : sum = sum + end_index; end_index++;
* sum == N : end_index++; sum = sum + end_index; count++;
******************************************************/
/* **********************************
* 슈도코드 작성하기
* **********************************
* N 자연수 저장
*
* 사용변수 초기화
* int sum = 1;
* int count = 1 ; //자연수 N
* int start_index = 1;
* int end_index = 1;
*
* while(end_index != N){
* if(sum < N){
* end_index++; //종료인덱스 증가
* sum = sum + end_index; //sum + 종료인덱스
* }else if (sum > N ){
* sum = sum - start_index; //sum - 시작인덱스
* start_index++; //시작인덱스 증가
* }else if(sum == N){
* end_index++;
* sum = sum + end_index;
* count++;
* }
* }
*
* result 출력
* **********************************/
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //자연수 N
//변수 초기화
int count = 1; //합 가짓수(결과)
int sum = 1; //연속된 자연수 합
int start_index = 1; //시작 인덱스
int end_index = 1; //종료 인덱스
while(end_index != N) { //현재 연속합이 N보다 작은 경우
if(sum < N) {
end_index++;
sum += end_index;
}else if(sum > N) { //현재 연속합이 N보다 큰 경우
sum -= start_index;
start_index++;
}else if(sum == N) { //현재 연속합이 N과 같은경우
end_index++;
sum += end_index;
count++;
}
}
System.out.println("rs: "+ count);
}public static void main(String[] args) {
/* (문제)[시간복잡도 최적화문제/투포인터]
* 어떠한 자연수 N은 몇개의 연속된 자연수의 합으로 나타낼수 있다.
* 어떤 자연수 N (1<=N<=10,000,000)을 몇개의 연속된 자연수의 합으로 나타내는 가짓수를 구하라
*
* -------------------------------------------------------------
* 시간복잡도란, 입력된 N의 크기에 따라 실행되는 조작의 수.
* -------------------------------------------------------------
* (시간복잡도) : N의 최대값이 매우 크므로, O(n) 알고리즘 사용해야함! ==> 여기서는 end_idx가 n임.
*
*(풀이방식)
* 1) 연속된 자연수의 최대값은 N이다. (1~N까지) => 카운터 개수 : 1로 초기화
* 2) 시작인덱스, 종료인덱스를 투포인터로 지정한후 문제에 접근
*
*(투포인터 이동 원칙)
* sum < N : sum = sum + end_idx; end_idx++;
* sum == N : end_idx++; sum = sum + end_idx; count++;
* sum > N : sum = sum - start_idx; start_idx++;
* */
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int cnt = 1; //N수 일단 카운트함.
int sum = 1; //시작 자연수(=1)로 셋팅
int stt_idx = 1;
int end_idx = 1;
// s
//e.g) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
// e
//sum : 3 6 10 15 21 22 21
// 20 18 15 18 13
//cnt :1 2
while(end_idx != N) {
if(sum == N) {
cnt ++;
end_idx++;
sum += end_idx;
} else if(sum < N) {
end_idx++;
sum+= end_idx;
} else if(sum > N) {
sum-= stt_idx;
stt_idx++;
}
}
System.out.println("RS : "+ cnt);
}
007 주몽의 명령
//(24.11.27 복기)
public static void main(String[] args) throws IOException {
//문제) 갑옷만들기
//갑옷을 만드는 재료들은 각각 고유한 번호가 있고,
//갑옷은 2개의 재료로 만드는데 2가지 재료의 고유한 번호를 합쳐 M(1<M<10,000,000)이 되면 갑옷이 만들어진다.
//자신이 만들고 있는 재료로 갑옷을 몇개나 만들수 있는지 구하라.
//입력값
//1. N개의 재료(1<N<15,000)
//2. M : 갑옷을 만드는데 필요한 수 (1<M<10,000,000)
//2. N개의 재료들이 가진 고유한 번호들 (1<N<100,000) 자연수 => 정렬필요(고유한 수니까!)
//단,정렬알고리즘의 시간복잡도는 O(nlogn)이지만 N이 최대 15,000이니까 괜찮다
//분석 : O(n)시간복잡도를 쓰자! ★
//단, 투포인터를 양쪽 끝에두고 시작 ★★★★
/* ********************************
* 슈도코드 짜기
* ********************************
* int N 저장하기
* int M 저장하기
* int[] num 고유번호 저장하기
*
* num 정렬하기
*
* 변수초기화
* start_index = 1;
* end_index = N;
* sum = 0;
* count = 0;
*
* while(start_index < end_index){
* sum = num[start_index] + sum[end_index];
*
* if(sum < M){
* end_index--;
* }else if(sum > M){
* start_index++;
* }else if(sum == M){
* count++;
* start_index++;
* end_index--;
* }
* }
*
* 출력하기
*
* ---------------------------
* 예제
* ---------------------------
* 6
9
2 7 4 1 5 3
* ********************************/
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine()); //N개의 재료
int M = Integer.parseInt(bf.readLine()); //M
int[] num = new int[N];
StringTokenizer st = new StringTokenizer(bf.readLine());
//고유의수 저장하기
for(int i=0; i<N; i++) {
num[i] = Integer.parseInt(st.nextToken());
}
//고유의수 정렬하기
Arrays.sort(num);
//변수초기화
int start_index = 0; //시작 인덱스
int end_index = (N-1); //종료 인덱스
int sum = 0; //두재료의 합
int count = 0; //결과
while(start_index < end_index){
sum = num[start_index] + num[end_index];
if(sum > M){
end_index--;
}else if(sum < M){
start_index++;
}else if(sum == M){
count++;
start_index++;
end_index--;
}
}
System.out.println("결과: "+ count);
}public static void main(String[] args) throws IOException {
/*(문제) : 고유번호 2가지 수의 합이 M (1<= M <= 10,000,000)이 되는 갯수를 구하라
* 첫번째줄 : N 재료의 개수 (1<= N <= 15,000)
* 두번째줄 : M 구할수의 합
* 세번째중 : 재료들 (숫자사이 공백 있음)
*
* -------------------------------------------------------------
* 시간복잡도란, 입력된 N의 크기에 따라 실행되는 조작의 수.
* -------------------------------------------------------------
* (시간복잡도) : 두 재료의 합, 즉 크기를 비교하므로 계산에 앞서 우선 값을 정렬필요.
* 최대수가 15,000 이므로 O(nlogn) 사용해도 무방함
* ==> 일반적인 정렬알고리즘의 시간복잡도는 O(nlogn) 임!!
*
* (풀이방법)
* 1. 입력받은 N개의 재료를 배열에 넣어 오름차순 정렬한다
* 2. 투포인터 사용 (i,j를 양끝에 셋팅)
*
*
* (투포인터 이동원칙)
* A[i] + A[j] > M : j--;
* A[i] + A[j] == M : i++; J--; count++;
* A[i] + A[j] < M : i++;
* */
// Scanner sc = new Scanner(System.in);
//
// int N = sc.nextInt();
// int M = sc.nextInt();
// int[] A = new int[N];
//
// //배열 값 저장
// for(int i=0; i<N; i++) {
// A[i] = sc.nextInt();
// }
/*------------------------------------*/
//InputStream & StringTokenizer 사용 (s)
/*------------------------------------*/
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int M = Integer.parseInt(bf.readLine());
int[] A = new int[N];
StringTokenizer st = new StringTokenizer(bf.readLine());
//배열 값 저장
for(int i=0; i<N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
/*------------------------------------*/
//InputStream & StringTokenizer 사용 (e)
/*------------------------------------*/
//투포인터 인덱스
int i = 0;
int j = N-1;
int cnt = 0;
//배열 정렬
Arrays.sort(A); //오름차순
/* e.g) M= 9, N = 6
*
* i : i
* j : j
* 1 2 3 4 5 7
* sum : 8 9 8 9
*
*/
//재료의합 구하기
while(i<j) {
if(A[i]+A[j] > M) {
j--;
}
else if(A[i]+A[j] == M) {
i++;
j--;
cnt ++;
}
else if(A[i]+A[j] < M) {
i++;
}
}
System.out.println("RS : "+ cnt);
bf.close();
}
008 '좋은수' 구하기
public static void main(String[] args) throws IOException {
/* (문제)주어진 N개의 수에서 다른 두수의 합으로 표현되는 "좋은수(=K)" 찾기. 단, 자기자신을 "좋은수(=K)" 만들기에 포함시키면 안됨
* 첫번째 줄 : 수의 개수 N (1<= N <= 2,000)
* 두번째 줄 : N개의 수의 값 Aｉ (|Aｉ| <= 1,000,000,000, Aｉ는 정수)
*
* (시간복잡도) 최소 O(nlogn)이여야 함. ===> 정렬, 투포인터 알고리즘 사용!
*
* (풀이방식)
* 1. N개의 수 배열에 저장
* 2. 배열 오름차순 정렬
* 3. 투포인터 셋팅 (양끝)
* 4. 투포인터 두수의 합이 배열 인덱스 순차적으로 하나씩 증가시킨 값 "좋은수(=K)"가 되는지 확인
* */
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int[] A = new int[N];
int cnt = 0;
StringTokenizer st = new StringTokenizer(bf.readLine());
//배열 값 저장
for(int i=0; i<N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
//배열 정렬
Arrays.sort(A); //오름차순
/*---------------------------------------------------------------*/
//FYI) 내림차순시 int 배열을 Integer로 변경 후 정렬해주어야 함
/*---------------------------------------------------------------*/
// Integer[] IA = Arrays.stream(A).boxed().toArray(Integer[]::new);
// Arrays.sort(IA, Collections.reverseOrder());
//K를 0부터 N까지 반복
for(int k=0; k<N; k++) {
int i = 0;
int j = N-1;
while(i < j) {
if(A[i]+A[j]== A[k]) {
if((i!=k) && j!=k) {
cnt++;
break;
} else if(i == k) {
i++;
} else if(j == k) {
j--;
}
} else if(A[i]+A[j] > A[k]) {
j--;
} else {
i++;
}
} //end while
}//end for
System.out.println("RS : "+ cnt );
bf.close();
}
이쯤되면 이제 시간복잡도 알고리즘에 대해 궁금해진다.
어떨때 어떤 시간복잡도를 쓰는게 좋은지..
우리의 ChatGPT를 통해 한번 짚고 넘어가자.
(질문)
투포인터 알고리즘을 공부중인데 시간복잡도 알고리즘에 대해 궁금해. 보통 투포인터은 시간복잡도가 O(n)이래 그리고 정렬 알고리즘은 시간복잡도가 O(nlogn)이래 예를들어 N이 1<N<10,000,000 일때, 1부터 N까지의 자연수의 연속된 합이 N이 되는 경우를 구하는걸 하는데, 이때는 시간복잡도가 O(nlogn)이면 안되고 N이 1<N<15,000 정도이고 1부터 N까지의 자연수가 랜덤으로 주어질때는 정렬을 한번 한 다음에 투포인터 알고리즘을 써도 괜찮데. 여기서 궁금한게 시간복잡도 알고리즘의 O(n)과 O(nlogn)을 사용할때 주의해야할점, 둘의 차이점, 그리고 어느정도의 수까지는 어떤 시간복잡도를 써야하는지.. 등을 자세하게 설명해줘
(ChatGPT 답변) :
투포인터 알고리즘과 정렬 알고리즘의 시간복잡도를 이해하고, 각각을 적절히 선택하는 기준을 이해하려면 시간복잡도의 성질과 실제로 수행 시간에 미치는 영향을 고려해야 합니다. 아래에서 이를 자세히 설명하겠습니다.
728x90
1. 시간복잡도의 O(n)과 O(nlogn)의 차이
O(n)
- 의미: 데이터의 크기 nn에 비례하여 연산 횟수가 증가합니다. 데이터가 nn만큼 커지면 수행 시간도 비슷하게 nn배로 증가합니다.
- 특징:
- 비교적 빠릅니다.
- 선형적으로 연산을 수행하기 때문에 대규모 데이터에도 적합합니다.
- 예: 투포인터 알고리즘, 단일 반복문을 사용하는 탐색 문제.
O(nlogn)
- 의미: 데이터 크기 nn에 로그 크기를 곱한 만큼 연산 횟수가 증가합니다. 이는 정렬 알고리즘과 같은 문제에서 자주 나타납니다.
- 특징:
- nn이 작을 때는 O(n)보다 큰 차이가 나지 않지만, nn이 커질수록 느려집니다.
- logn\log n은 느리게 증가하기 때문에 큰 nn에서도 실용적일 수 있습니다.
- 예: 퀵소트, 병합 정렬 등 효율적인 정렬 알고리즘.
2. 주의해야 할 점
O(n)의 알고리즘을 사용할 때
- 단일 반복문에서 실행:
- O(n)은 모든 데이터를 한 번씩 살펴보는 연산이므로, 불필요하게 중복된 연산이 없어야 합니다.
- 데이터 크기가 매우 크더라도 적합:
- 데이터 크기가 nn에 비례한 연산량이므로, 대규모 입력에도 실용적입니다.
O(nlogn)의 알고리즘을 사용할 때
- 데이터 정렬이 필요한 경우:
- 정렬을 미리 수행해야 투포인터처럼 효율적인 알고리즘을 사용할 수 있습니다.
- 데이터 크기에 유의:
- nn이 매우 클 경우 nlognn \log n은 O(n)보다 연산량이 많아질 수 있습니다.
- 정렬 비용과 이후 연산의 효율성 비교:
- 정렬 이후 O(n)으로 해결 가능한 문제라면 전체적으로 O(nlogn)만큼의 효율성을 가질 수 있습니다.
3. 어떤 상황에서 어떤 시간복잡도를 선택해야 하는가?
(1) N이 큰 경우 (예: 1<N<10,000,0001 < N < 10,000,000)
- 이 경우 nn이 매우 크므로, O(nlogn)보다 O(n)을 사용하는 것이 바람직합니다.
- 이유:
- nn이 클수록 nlognn \log n의 시간복잡도가 O(n)보다 훨씬 느려집니다.
- 투포인터와 같은 O(n) 알고리즘은 정렬 없이 바로 데이터를 처리하므로 더 효율적입니다.
(2) N이 비교적 작은 경우 (예: 1<N<15,0001 < N < 15,000)
- 이 경우 O(nlogn)으로 정렬 후 O(n) 알고리즘을 사용하는 것이 가능합니다.
- 이유:
- nn이 작을 때는 logn\log n의 증가량이 작기 때문에, 정렬을 수행하는 비용이 크지 않습니다.
- 정렬 후 투포인터를 사용하면 문제를 보다 간결하고 효율적으로 해결할 수 있습니다.
4. 투포인터 + 정렬 알고리즘의 혼합 사용
정렬 + 투포인터 알고리즘의 시간복잡도는 다음과 같습니다:
- 정렬 단계: O(nlogn)
- 투포인터 알고리즘 실행: O(n)
따라서, 전체 시간복잡도는 O(nlogn+n)O(nlogn + n), 즉 O(nlogn)O(nlogn)이 됩니다.
5. 정리
- O(n)를 사용하는 상황:
- nn이 매우 크고 데이터가 정렬되어 있거나, 정렬 없이도 문제를 풀 수 있을 때.
- 연속적인 탐색이 주된 작업일 때.
- O(nlogn)를 사용하는 상황:
- nn이 상대적으로 작거나, 문제 해결을 위해 정렬이 반드시 필요할 때.
- 정렬 이후 추가 작업의 복잡도가 낮아 전체 연산량이 효율적일 때.
추천 기준
- n>100,000n > 100,000: O(n) 알고리즘을 사용하는 것을 우선 고려.
- n≤100,000n \leq 100,000: O(nlogn)도 무리 없이 사용 가능.
이 기준은 상황에 따라 유동적일 수 있으므로, 문제에서 요구하는 성능 조건에 따라 적절히 선택하세요!
728x90
'알고리즘' 카테고리의 다른 글
| [알고리즘] 시간복잡도 알고리즘 (1) | 2024.11.26 |
|---|---|
| [알고리즘] 등비수열 (0) | 2023.11.06 |
| [알고리즘] Q005 나머지 합 구하기 (조합/Combination) (0) | 2023.08.20 |
| [알고리즘] Q004 구간합 (2차 배열) (0) | 2023.08.19 |
| [알고리즘] 로그확인/출력시 Tip (0) | 2023.08.19 |
