728x90 알고리즘9 [알고리즘] 시간복잡도 알고리즘 1. 시간복잡도의 O(n)과 O(nlogn)의 차이O(n)의미: 데이터의 크기 nnn에 비례하여 연산 횟수가 증가합니다. 데이터가 nnn만큼 커지면 수행 시간도 비슷하게 nnn배로 증가합니다.특징:비교적 빠릅니다.선형적으로 연산을 수행하기 때문에 대규모 데이터에도 적합합니다.예: 투포인터 알고리즘, 단일 반복문을 사용하는 탐색 문제.O(nlogn)의미: 데이터 크기 nnn에 로그 크기를 곱한 만큼 연산 횟수가 증가합니다. 이는 정렬 알고리즘과 같은 문제에서 자주 나타납니다.특징:nnn이 작을 때는 O(n)보다 큰 차이가 나지 않지만, nnn이 커질수록 느려집니다.logn\log nlogn은 느리게 증가하기 때문에 큰 nnn에서도 실용적일 수 있습니다.예: 퀵소트, 병합 정렬 등 효율적인 정렬 알고리즘... 2024. 11. 26. [알고리즘] 등비수열 https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=junhyuk7272&logNo=221247061276 3. 등차수열의 합 3. 등차수열의 합 (1) 기본적인 공식 도출 등차수열의 합공식은 가우스가 초등학교 때 만들었습니...blog.naver.com 등차수열의 합, 등비수열의 합 공식 유도고등학교 2학년 과정이죠. 이번 포스팅에서는 수학 1 과목에서 배우는 등차수열과 등비수열의 합에 대한 내...blog.naver.com 2023. 11. 6. [알고리즘] Q006~008 투 포인터 (시간복잡도 알고리즘) 투포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. 매우 간단한 알고리즘으로 투포인터 이동 원칙1. 연속된 자연수의 합을 구하는 경우 : 투포인터를 모두 시작인덱스에 셋팅 * sum * 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] 006 연속된 자연수의 합 구하기 //(24.11... 2023. 9. 10. [알고리즘] Q005 나머지 합 구하기 (조합/Combination) //N개의 수 A1,A2..An이 주어졌을때, 연속된 부분의합이 M으로 나누어 떨어지는 구간의 개수 구하기(제한시간: 1초)//즉, Ai+...Aj(i 0 ~ N){ * N개의 수 입력받기 (A) * S[i] = S[i-1] + A[i] //합배열 저장 * remainder = S[i] % M //합배열을 M으로 나눈 나머지 값 * * if(remainder == 0){ * answer++ * } * C[remainder]++ * } * * for(i -> 0 ~ M){ * C[i](i가 나머지인 인덱스의 개수)에서 2가지를 뽑는 경우의 수를 정답에 더하기 * //공식 : (C[i]*C[i]-1)/2 * } * * answer 출력 * * */.. 2023. 8. 20. [알고리즘] Q004 구간합 (2차 배열) 코딩테스트에 자주 등장하는 2차배열 구간합 관련 문제package Quiz;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.StringBufferInputStream;import java.util.ArrayList;import java.util.Arrays;import java.util.StringTokenizer;public class Q004_구간합구하기2 { public static void main(String[] args) throws IOException { //NxN개 수가 NxN크기의 표에 채워져있다. (X1,Y1)부터 (X2,Y2)까지 수의 합구하기.. 2023. 8. 19. [알고리즘] 로그확인/출력시 Tip 배열 출력 : Arrays.toString(arr);java.util.Arrays의 toString() 메소드 사용import java.util.Arrays; public class PrintArray { public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5 }; System.out.println(Arrays.toString(arr)); }} 2023. 8. 19. [알고리즘] 003 구간합 BufferedReader 코딩테스트를 처음칠때 약간 당황했던건문제에서 주어진 입력값을 어떤형식으로 받아야 하는가 였다. 여러문제를 많이 접해보면 자연스럽게 알게되겠지만그렇지 못했던 지난날을 되돌아보며.. package Quiz;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.StreamTokenizer;import java.util.Scanner;import java.util.StringTokenizer;public class Q003_구간합구하기 { public static void main(String[] args) throws IOException { // TODO Auto-gener.. 2023. 8. 19. [알고리즘] Java 기초 편(자료구조) P.33 03 자료구조 03-1 배열과 리스트03-2 구간 합03-3 투 포인터03-4 슬라이딩 윈도우04-5 스택과 큐------------------------------------------------------------------------------------------ 03-1 배열과 리스트배열과 리스트의 핵심 이론 2023. 8. 15. 이전 1 2 다음 728x90
