개발자꿈나무

[문제] [입출력 형식] 사실 이 문제는 간단하게 풀고자한다면 sort() 메소드를 이용해서 간단하게 풀 수 있다. 나역시 sort 메소드를 이용해서 몇 초만에 문제를 풀었고, 이후에도 유사한 문제들을 sort 메소드를 이용해서 간단하게 풀었지만 그렇게하면 알고리즘 실력을 쌓을 수 없기 때문에 정렬 알고리즘에 대해서 공부를 다시 하고 알고리즘을 활용해서 문제를 풀어봤다. 오늘 공부한 정렬은 버블정렬으로 버블정렬이란 인접한 두 개의 값을 비교해서 정렬을 해주는 알고리즘 방식이다. 간단하게 구현할 순 있지만 시간 복잡도는 O(n제곱)으로 다른 정렬 알고리즘보다 속도가 느린 편이다! [버블 정렬 과정] 위의 예시를 보고 간략하게 설명을 해보자면 현재 [5 2 3 4 1]이란 값이 저장되어있는 상태이고 오름차순..

이번엔 1차원 배열을 이용한 구간합 구하기가 아니라 2차원 배열을 이용한 구간합 구하기에 대해서 알아볼 것이다. 2차원 배열 합 배열의 공식을 먼저 살펴보도록 하자. 먼저 기본적인 배열이 아래와 같이 주어져있다고 할 때, 이 배열의 합 배열을 직접 그려가면서 이해해볼 것이다. 회색 칸은 단순히 (0, 0)의 인덱스를 나타낸 것으로 전부 0이라고 생각하면 되고 흰색 칸의 값들이 들어가있다고 할 때 첫번째 행과 첫번째 열의 합부터 구해보면 1차원 배열의 합배열과 똑같은 것을 알 수 있다. 첫번째 열을 구하는 공식은 D[1][j-1] + A[1][j]이고 첫번째 열을 구하는 공식은 D[i-1][1] + A[i][1]이다. 행과 열이 섞여있어 헷갈릴 수 있는데 직접 그림은 그리면서 생각해보면 이해가 될 것이다...

구간합 문제를 풀기에 압서 배열합과 구간합의 공식과 개념을 먼저 알아볼 필요가 있다. 구간합이란 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 특수한 목적의 알고리즘 구간합 알고리즘을 활용하려면 합 배열을 구해야 한다! 합 배열 S[i] = A[0] + A[1] + A[2] + ... + A[i] //A[0]부터 A[i]까지의 합 위 그림에서 S[5]의 값은 A[0] + A[1] + A[2] + A[3] + A[4] + A[5]의 값과 같다. 즉, S[i] = S[i-1] + A[i] 라는 공식까지 도달할 수 있다. => S[1] = S[0] + A[1] = 15 + 13 = 28 // S[5] = S[4] + A[5] = 48 + 12 = 60 구간합을 구하는 식도 간편한데 i부터 j까지의 합..

시간 복잡도란 : 주어진 문제를 해결하기 위한 연산 횟수. 일반적으로 수행시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측 시간 복잡도 유형 - 빅-오메가 : 최선일 때 (best case)의 연산 횟수를 나타낸 표기법 - 빅-세타 : 보통일 때 (average case)의 연산 횟수를 나타낸 표기법 - 빅-오(O(n)) : 최악일 때 (worst case)의 연산 횟수를 나타낸 표기법 코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋음! 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격이므로 최악일 때를 염두에 둬야 함. 예를 들어 백준 2750번을 푼다고 가정했을 때, 시간제한이 2초라면 이 조건을 만족하기 위해서는 2억 번 이하의 연산 횟수로 문제를 해결해야 ..

[문제] [입력 출력 조건] [수도 코드] 소수들의 집합을 먼저 구해야 함 -> 에라토스테네스의 체에 대해서 먼저 알아볼 필요가 있음 일단 먼저 소수란 1과 자기 자신만을 약수로 가지고 있는 자연수라고 할 수 있음 에라토스테스의 체란? 구하고자 하는 구간의 모든 자연수를 나열한 후 소수의 배수들을 전부 지워주는 방식. - 예를 들어 100까지의 소수를 구하고자 한다면 일단 1은 제외하고 제일 작은 값인 2를 소수로 채택 -> 2의 모든 배수들 지우기 - 그 다음 작은 값인 3을 소수로 채택 -> 3의 모든 배수 지우기 - 이런 식으로 배수들을 지워나가면 결국 마지막에는 소수들만 남아있음 에라토스테스의 체를 이용해서 소수면 false로 boolean 배열 안에 저장해놓고, 소수의 값들만 list에 저장 l..

퀵 정렬 - 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 - 병합 정렬과 더불어 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나 - 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정 퀵 정렬의 시간 복잡도 - 평균의 경우 O(NlogN)의 시간 복잡도를 가지며, 최악의 경우 O(N의 제곱) Ex) 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해 퀵 정렬을 수행하면 분할이 될 때마다 오른쪽 묶음만 남은 것과 같은 모양이 되고, 선형적으로 하나하나 이미 정렬된 배열을 다시 진행하게 되므로 최악의 경우 O(N의 제곱)이 될 수 있음 public static void quickSort(int[] arr, int start, ..