배열 요소에 접근하는데 O(1)의 시간이 걸리는 이유

배열은 선형 데이터 구조입니다. 배열은 메모리에 연속적으로 할당되므로 배열의 인덱스를 통해 값을 가져오는 것은 산술 연산입니다. 산술 연산은 O(1)로 수행됩니다. 배열에는 인덱스 0의 메모리 주소가 있습니다. 인덱스 번호와 한 요소의 크기(int일 경우 4바이트)를 기본 주소에 더하면 해당 인덱스 값의 주소를 얻을 수 있습니다. i번째 인덱스 주소 = 0번째 인덱스 주소 + i x (한 요소의 크기) 예시 int[] arr = {1,2,3,4,5} arr 배열에서 인덱스 0의 메모리 주소를 100이라고 가정했을 때 3번째 인덱스 주소를 얻을려면 100 + 3 * 4 = 112의 메모리 주소값을 얻습니다.

• format_list_bulleted 알고리즘/자료구조
• · 2024. 4. 4.
• textsms

행렬인가 무엇인가?

행렬이란? 행렬은 행과 열로 구성된 2차원 배열입니다. 항목의 가로 또는 세로 줄로 요소를 배열하는 것입니다. 행렬의 선언 행렬의 선언은 1차원 배열과 매우 유사합니다. int[][] arr = new int[3][5]; 행렬의 첫번째 요소는 arr[0][0]입니다. 첫번째 대괄호 안의 값은 행 번호를 나타내고 두 번째 대괄호 안의 값은 열 번호를 나타냅니다. 행렬의 초기화 int[2][2] arr = {{1,2},{3,4}}; 2개의 행과 2개의 열을 가진 행렬의 구성을 가지면서 값을 넣어줍니다. 행렬의 접근 1차원 배열과 마찬가지로 행렬에서도 무작위 요소에 접근이 가능합니다. arr[i][j]를 사용하여 i번째 행과 j번째 열에 있는 요소에 접근할 수 있습니다. int value = arr[i][j]..

• format_list_bulleted 알고리즘/자료구조
• · 2024. 4. 4.
• textsms

배열이란 무엇인가?

배열이란? 배열은 인접한 메모리 위치에 저장된 동일한 데이터 유형 모음입니다. 쉽게 생각하면 계단이라고 생각하시면 됩니다. 계단에서 5걸음 올라가면 5번째 위치이고 3걸음 올라가면 3번째 위치입니다. 걸음 수만 알면 어디 위치인지 알 수 있습니다. 배열의 첫 번째 요소의 메모리 위치에 오프셋을 추가하기만 하면 각 요소의 위치를 쉽게 계산할 수 있습니다. 배열의 기본 인덱스의 값은 0이고 배열의 길이가 늘어날 수록 인덱스는 1씩 증가합니다. 배열의 기본 용어 인덱스 : 배열의 요소의 위치는 인덱스로 식별됩니다. 배열의 인덱스는 0부터 시작합니다. 배열 요소 : 배열에 저장된 항목입니다. 배열 길이 : 저장할 수 있는 배열의 요소 수에 따라서 달라집니다. 배열의 선언 주어진 크기의 배열에 메모리를 할당하는 ..

• format_list_bulleted 알고리즘/자료구조
• · 2024. 4. 4.
• textsms

수학 알고리즘 - 순열과 조합 알고리즘(재귀, 반복문)

순열이란 집합의 요소들을 중복없이 특정한 순서로 나열하는 것을 말합니다. 예를 들어 {1, 2, 3}으로 집합이 주어져있을 때 2개를 순열로 만들면 {1,2},{1,3},{2,1},{2,3},{3,1},{3,2}이 됩니다. 서로 다른 n개의 원소에서 r개를 선택하여 나열하는 경우의 수를 말합니다. 조합이란 집합의 요소들 중에서 중복없이 일부를 선택하여 순서에 상관없이 나열하는 것을 말합니다. 예를 들어 {1,2,3}으로 집합이 주어져있을 때 2개를 조합하면 {1,2},{1,3},{2,3}이 됩니다. 서로 다른 n개의 원소에서 r개를 선택하는 경우의 수를 말합니다. 반복문을 이용한 조합 코드 예시 function combination(arr) { const result = [] for(let i = 0; ..

• format_list_bulleted 알고리즘/초급 알고리즘
• · 2024. 4. 3.
• textsms

수학 알고리즘 - 거듭제곱 알고리즘(반복문, 분할정복)

거듭 제곱이란 거듭 제곱은 한 수를 다른 수의 거듭제곱으로 나타내는 것을 말합니다. 2의 3승은 2 * 2 * 2 = 8입니다. 반복문을 이용한 거듭 제곱 코드 예시 function power(n, m) { let result = 1 for(let i = 1, i > 1, r) } return fastPower(n, m, 1) } 숫자와 지수를 받아서 거듭제곱하는 함수입니다. 재귀를 통해 r에 현재 계산 결과를 가지고 있습니다. 만약 지수가 0이면 현재 계산 결과를 반환합니다. 지수가 홀수이면 숫자를 한번더 곱합니다. 2^5이면 2^2 * 2^2 * 2이 계산이기때문에 홀수일 때 숫자를 더 곱해야됩니다. 지수가 짝수면 지수는 반으로 줄이고 숫자를 제곱하여 넘겨줍니다. 2^4 = 2^2 * 2^2 2^2 ..

• format_list_bulleted 알고리즘/초급 알고리즘
• · 2024. 4. 2.
• textsms

수학 알고리즘 - 소수 판별 알고리즘(브루트 포스, sqrt, 에라토스테네스의 체)

소수란 소수는 1과 자기 자신으로만 나누어지는 양의 정수입니다. 예를 들어 2, 3, 5, 7, 11등이 있습니다. 브루트 포스를 이용한 소수 판별(n -1까지) 코드 예시 function isPrime(num) { for(let i = 2; i < num; i++) { if(num % i === 0) return false } return true } 2부터 시작하여 num - 1까지 나머지를 검사하면서 0이 있으면 소수가 아니고 나머지가 0이 하나라도 없으면 소수입니다. 브루트 포스를 이용한 소수 판별(sqrt 까지) 코드 예시 function isPrime(num) { for(let i = 2; i

• format_list_bulleted 알고리즘/초급 알고리즘
• · 2024. 4. 1.
• textsms