문제

• $n*n$ 배열 A의 각 행은 1과 0으로만 구성되며, A의 어느 행에서나 1들은 해당 행의 0들보다 앞서 나온다고 가정
• A가 이미 주기억장치에 존재한다고 가정하고, 가장 많은 1을 포함하는 행을 $O(n)$ 시간에 찾는 알고리즘 mostOnes(A,n)를 의사코드로 작성하라

ex) $8x8$ 배열 A -> 6행이 가장 많은 1을 포함

잘못된 방법

실행시간이 $O(n)$이 아니라 $O(n^2)$

Alg mostOnesButSlow(A,n)
	input bit matrix A[nxn]
    output the row of A with most 1's
    
1. row <- jmax <- 0
2. for i<- 0 to n-1
		j<-0
        while((j < n) & (A[i,j] = 1))
        	j <- j+1
        if(j > jmax)
        	row <- i
        	jmax <- j
3. return row           

해결 방법

1. 행렬의 좌상 셀에서 시작
2. 0이 발견될 때까지 행렬을 가로지름
3. 1이 발견될 때까지 행렬을 내려감
4. 마지막 행 or 열을 만날 때까지 위의 2&3단계를 반복
5. 1을 가장 많이 가진 행은 가로지른 마지막 행

• 최대 $2n$회의 비교를 수행하므로 -> 실행시간 $O(n)$
• 두가지 버전으로 작성 가능

방법 1

Alg mostOnes(A,n)
	input bit matrix A[nxn]
    output the row of A with most 1's
    
1. i <- j <- 0
2. while(1)
	while(A[i,j] = 1)
    	j <- j + 1
        if(j = n)
        	return i
    row <- i
	while(A[i,j] = 0)
    	i <- i + 1
        if(i = n)
        	return row

방법 2

Alg mostOnes(A,n)
	input bit matrix A[nxn]
    output the row of A with most 1's
1. i <- j <- row <- 0
2. while((i<n) & (j<n))
		if(A[i,j] = 0)
        	i <- i + 1
        else
        	row <- i
        	j <- j + 1
3. return row