Array algorithms: max, count, search, average · 배열 알고리즘: 최대값, 카운트, 검색, 평균
Four classic array jobs
- Most array work is one of four scans: find the maximum, count matches, search for a value, or take an average.
- Each one is a single
forloop over the array, with a variable that remembers something. - Once you know these four, most array problems are a small change to one of them.
네 가지 고전적인 배열 작업
- 대부분의 배열 작업은 다음 네 가지 스캔 중 하나입니다: 최대값 찾기, 일치 개수 세기, 값 찾기(검색), 또는 평균 계산.
- 각각은 배열 전체를 순회하는 단일
for루프이며, 무언가를 기억하는 변수가 포함됩니다. - 이 네 가지를 알면, 대부분의 배열 문제는 이 중 하나를 조금 수정하여 해결할 수 있습니다.
Finding the maximum
- Start by assuming the first item is the biggest:
int best = a[0];. - Then look at the rest. If an item is bigger than
best, it becomes the newbest. - This works for negative numbers too, because you start from a real item, not
0.
최대값 찾기
- 가장 큰 항목이 첫 번째임을 가정하고 시작하십시오:
int best = a[0];. - 나머지 항목을 확인하십시오. 만약 어떤 항목이
best보다 크다면, 그것이 새로운best이 됩니다. - 이 방법은 음수에도 적용됩니다. 왜냐하면
0가 아닌 실제 요소에서 시작하기 때문입니다.
Counting with a condition
- A counter starts at
0and adds1each time an item passes a test. - For example, count even numbers by testing
a[i] % 2 == 0inside the loop. - The counter's final value is your answer.
조건을 이용한 세기
- 카운터는
0에서 시작하여 항목이 조건을 통과할 때마다1을 더합니다. - 예를 들어, 루프 내부에서
a[i] % 2 == 0를 테스트하여 짝수를 세십시오. - 카운터의 최종 값이 당신의 답이 됩니다.
Linear search
- To search, walk the array and compare each item to the target.
- Return the index as soon as you find a match. If the loop ends with no match, return
-1. -1is a common "not found" signal because it is never a valid index.
선형 검색
- 검색하려면, 배열을 순회하며 각 항목을 타겟과 비교하십시오.
- 일치하는 것을 찾으면 즉시 인덱스를 반환하십시오. 루프가 완료되어도 찾지 못하면
-1를 반환하십시오. -1는 유효한 인덱스가 결코 될 수 없기 때문에 '찾지 못함' 신호로 자주 사용됩니다.
Average without integer-division bugs
- Add all the items into an
inttotal, then divide byn. - Dividing two
ints drops the fraction, so cast:(double)total / n. - Return a
doubleso the caller gets the exact average.
정수 나눈 오류 없는 평균
- 모든 항목을
int총합에 더한 후,n로 나눕니다. - 두
int를 나누면 소수점이 버려지므로, 캐스트가 필요합니다:(double)total / n. - caller이 정확한 평균을 받을 수 있도록
double를 반환하십시오.
Common mistakes
- Start a max or min from the first element, then compare the rest.
- Do not read past the end of the array.
흔한 실수
- 최대값 또는 최소값은 첫 번째 요소에서 시작하여 나머지를 비교한다.
- 배열의 끝을 넘어 읽지 마십시오.
Now you try
- Pass the array and its length
n, and pick the right "remember" variable for each job. - Do not write a
main— the checker provides one.
이제 직접 해보기
- 배열과 길이
n를 전달하고, 각 작업에 맞는 적절한 "기억" 변수를 택하십시오. main을 작성하지 마세요; 검증程序가 제공해 줍니다.
Scanning an array · 배열 스캔하기
One pass keeps a running result (max, sum, count) across the array. · 한 번의 순회로 배열 전반에 걸쳐 누적 결과(최댓값, 합계, 개수 등)를 유지합니다.
Complete int max(const int a[], int n) so it returns the largest item (assume n >= 1). Start from a[0] so negatives work. Do not write a main. · int max(const int a[], int n)을 완성하여 가장 큰 항목(n >= 1로 가정)을 반환하도록 하십시오. 음수가正确处理되도록 a[0]부터 시작하십시오. **main을 작성하지 마십시오.**
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete int count_even(const int a[], int n) so it returns how many items are even. Use % 2. Do not write a main. · int count_even(const int a[], int n)을 완성하여 짝수인 항목의 개수를 반환하도록 하십시오. % 2을 사용하십시오. **main을 작성하지 마십시오.**
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete int index_of(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not there. Do not write a main. · int index_of(const int a[], int n, int target)을 완성하여 첫 번째 target의 인덱스를 반환하거나, 없으면 -1을 반환하도록 하십시오. **main을 작성하지 마십시오.**
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete double average(const int a[], int n) so it returns the average of the items (assume n >= 1). Cast to avoid integer division. Do not write a main. · double average(const int a[], int n)을 완성하여 항목들의 평균(n >= 1으로 가정)을 반환하도록 하십시오. 정수 나눗음을 피하기 위해 형 변환을 사용하십시오. **main을 작성하지 마십시오.**
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.