기록방

💡 합의 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특한 목적의 알고리즘 🚀 합의 배열 S 정의 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. A[ 0 ]부터 A[ i ]까지의 합 : S[ i ] = A[ 0 ] + A[ 1 ] + A[ 2 ] + ... + A[ i-1 ] + A[ i ] 합 배열은 기존의 배열을 전처리한 배열 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소 A[ i ] 부터 A[ j ] 까지의 배열 합을 합 배열 없이 구하는 경우, 최악은 i가 0이고 j가 N인 경우로 O(N) 합 배열을 이용하면 O(1) 🚀 합 배열 S를 만드는 공식 S[ i ] = S[ i-1 ] + A[ i ] 🚀 구간 합을 ..

💡 알고리즘에서 시간 복잡도 - 알고리즘 선택의 기준이 되는 시간 복잡도 - 코딩 테스트의 핵심 중 하나는 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것 - 주어진 문제를 해결하기 위한 연산 횟수 (일반적으로 1억번 연산을 1초로 간주해서 예측) 🚀 시간 복잡도 유형 빅-오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 빅-세타(Θ(n)) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 ⇒ 코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산 (최악을 염두) 🚀 시간 복잡도 활용 예시 N 개의 수를 오름차순 정렬한다 (1 부적합 알고리즘 병합 정렬을 사용한다면?..

> 원본 노션 페이지 보러 가기

Do it! 알고리즘 코딩 테스트 - 자바 편 http://www.easyspub.co.kr/20_Menu/BookView/500/PUB www.easyspub.co.kr 03-3 투 포인터 알고리즘이 간단하므로 문제로 알아보자 [연습문제 #006 :연속된 자연수의 합 구하기 (boj_2018)] 문제 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. 예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+..

Do it! 알고리즘 코딩 테스트 - 자바 편 http://www.easyspub.co.kr/20_Menu/BookView/500/PUB www.easyspub.co.kr 3장 : 자료구조 💡 데이터를 효율적으로 저장, 접근, 수정하기 위한 그릇 문제의 입력 데이터 형태와 사용해야 하는 알고리즘에 따라 적절한 자료구조를 선택하는 것이 매우 중요하다 03-1 배열과 리스트 배열과 리스트는 비슷한 점도 많지만 다른 점도 많다 배열과 리스트의 핵심 이론 배열 : 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 인덱스로 참조 선언한 자료형 값만 저장 가능 배열의 특징 인덱스를 사용하여 값에 바로 접근 가능 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움(해당 인덱스 값 이동 필요) 구조가..