| English | 의미 |
|---|---|
| traversal/træˈvɜːsl/ | 반복 Traverse |
| index/ˈɪndeks/ | 인덱스 |
| linear search/ˈlɪnɪə sɜːtʃ/ | 선형 탐색 |
표준 배열 알고리즘
- 대부분의 배열 작업은 traversal과 몇 가지 표준 패턴 중 하나의 조합입니다.
- Sum / average: 총액을 누적한 후
length로 나눕니다. - Count: 요소가 조건에 부합할 때마다 증가시킵니다.
- Min / max: 현재까지 본 가장 작거나 가장 큰 값을 추적합니다.
최대값 찾기
max = a[0](첫 번째 요소)로 시작하여, 인덱스1부터 순회합니다.- 루프 내에서 **
if (a[i] > max) { max = a[i]; }**합니다. - 루프가 끝난 후,
max에 배열의 최대 값이 저장됩니다. 0가 아닌 첫 번째 요소부터 시작하세요.0이 모든 값보다 클 수 있습니다.
값 찾기
- 값이 존재하는지 확인하려면 순회하며 각 요소를 비교합니다.
- 찾은 위치의 index를 반환하거나, 루프가 매칭 없는 상태로 끝나면
-1를 반환합니다. - 루프 내부에서는
if (a[i] == target) return i;; 루프 종료 후에는return -1;. - 이는 linear search입니다 (단원 4.14에서 심층 다룹니다).
이동 및 수정
- 일부 알고리즘은 요소를 이동하거나 변경합니다. 예: 모든 것을 왼쪽으로 이동하거나 각 값을 두 배로 만들기.
- 수정에는 indexed 루프가 필요합니다. 이를 통해
a[i] = ...에 할당할 수 있습니다. a[i+1]를 읽을 때 경계를 주의하세요. 마지막 인덱스에는 이웃이 없습니다.- 인덱스를 신중하게 추적하여 범위를 벗어난 접근을 피하세요.
최대/최소 검색을 0가 아닌 FIRST element로 초기화하십시오. int max = 0;은 모든 값이 음수일 경우 실패합니다 (0를 잘못 보고합니다). int max = a[0];을 사용하고 루프를 인덱스 1에서 시작하세요. 그리고 알고리즘이 a[i+1]을 읽을 때, 루프를 i < a.length - 1에서 멈추어야 마지막 반복 시 끝을 넘어 읽는 일이 없습니다.
a의 최대값 찾기:
int max = a[0];for (int i = 1; i < a.length; i++) { if (a[i] > max) max = a[i]; }a = {3, 9, 5}에 대해: max가9이 됩니다.
배열 알고리즘은 traversal과 패턴의 조합입니다: sum/average, count, min/max, 또는 search(인덱스 또는 -1 반환). min/max를 first element로 초기화하고, 0으로 하지 마십시오. 요소를 수정할 때는 indexed 루프가 필요하며, a[i+1]을 읽을 때는 범위에 맞게 경계를 좁혀야 합니다.
최대값 찾기
max는 a[0]=3에서 시작하여 9가 된 후 유지됩니다 (a = {3,9,5})
배열의 최대값을 찾으려면 max를 ...로 초기화해야 합니다
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
0에서 시작하면 모든 값이 음수일 경우 실패합니다
a = {3, 9, 5}일 때 최대값은 무엇입니까?
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
9은 가장 큰 요소입니다
타겟을 찾지 못했을 때 선형 검색은 무엇을 반환합니까?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
관례상 -1은 '찾지 못함'을 의미합니다
a[i+1]을 읽는 알고리즘은 ...일 때 루프를 반복해야 합니다
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
조금 일찍 멈추면 a[i+1]이 범위 내에 있습니다
배열 요소 수정(a[i] = ...)은 인덱스 루프가 필요하며, for-each는 필요합니다
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
for-each는 배열에 다시 할당할 수 없습니다