자료구조 및 실습 - [1] 알고리즘 분석 실습문제 (나머지 연산, 비트행렬에서 최대 1행 찾기, 누적 평균) (3)

문제 1 - 나머지 연산

‘%’(modulo) 연산자는 나눗셈의 나머지를 반환한다. 덧셈과 뺄셈 연산자만을 사용하여 a를 b로 나눈 나머지를 반환하는 modulo(a, b) 함수와 이를 테스트할 프로그램을 작성하시오. 단, a ≥ 0, b > 0 인 정수다.

 

※ 힌트: modulo(a, b) 함수는 O(a/b) 시간에 실행하도록 작성할 수 있다.

 

#입력 예시 1
>>> 17 3   // 17 % 3
2

#입력 예시 2
>>> 6 3  // 6 % 3
0

#입력 예시 3
>>> 0 5  // 0
0

def modulo(a,b):
  temp = True

  while temp:
    if a>=b:
      a=a-b
    else :
      temp = False   
  print(a)
  
a = int(input())
b = int(input())

modulo(a,b)

이게 그냥 짠 코드였는데 블로그에 정리하려고 보니 '굳이 ?'라는 생각이 드는 코드이다...?

def modulo(a,b):
  while b<a: # 나누어 질 수 있는대로 (-가 여러번이면 나눗셈이므로)
    if a>=b: # a에서 b를 뺄 수 있으면
      a=a-b  #빼라
  print(a)
  
a = int(input())
b = int(input())

modulo(a,b)

코드가 더 간결해졌다! 

---

문제 2 - 비트행렬에서 최대 1행 찾기

n × n 비트 행렬 A의 각 행은 1과 0으로만 구성되며, A의 어느 행에서나 1들은 해당 행의 0들보다 앞서 나온다고 가정.

 행렬 A를 입력받아, 가장 많은 1을 포함하는 행을 찾는 프로그램을 작성하시오. 그러한 행이 여러 개 있을 경우 그 가운데 가장 작은 행 번호를 찾아야한다.

#Slow version
def mostOnes(A,n): 
  row = 0 #행을 선택
  jmax = 0 # 가장 많은 1을 가진 행에서 1의 갯수는 몇인가?

  for i in range(n-1): #행의 개수만큼 반복
    j=0
    while((j<n) & (A[i][j]==1)): # j가 열의 갯수보다 작고, 원소가 1이면? 
      j=j+1 #j의 개수 업데이트
    if j>jmax: # 탐색했던 i열의 1의 갯수가  jmax보다 크다면
      row = i #row 업데이트
      jmax = j #1의 갯수 업데이트

  print(row)
  

n = 8
A = [[1,1,1,1,0,0,0,0],[1,1,1,1,1,0,0,0],[1,0,0,0,0,0,0,0],[1,1,1,1,1,1,0,0],[1,1,1,1,0,0,0,0],[0,0,0,0,0,0,0,0],[1,1,1,1,1,1,1,0],[1,1,1,1,1,0,0,0]]

먼저 O(n^2) 인 알고리즘을 먼저 구현했다. for문 내에 while문이 삽입되어 각 행의 모든 열을 탐색하기 때문에 2차시간이 소요된다. 이를 그림으로 표현하면 다음과 같다.

 

 

하지만 다음과 같은 절차를 통해 알고리즘을 구현하면 O(n)인 알고리즘을 구현할 수 있다.

1. 행렬의 좌상 셀에서 출발한다.
2. 0이 발견될 때까지 행렬을 가로질러 간다.
3. 1이 발견될 때까지 행렬을 내려간다.
4. 마지막 행 또는 열을 만날 때까지 위 2, 3 단계를 반복한다.
5. 1을 가장 많이 가진 행은 가로지른 마지막 행이다.

이를 그림으로 표현하면 다음과 같다.

#입력 예시
8 ↦ n = 8 (8 × 8 행렬)
1 1 1 1 0 0 0 0 ↦ 각 비트는 공백으로 구분
1 1 1 1 1 0 0 0
1 0 0 0 0 0 0 0
1 1 1 1 1 1 0 0
1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0
1 1 1 1 1 0 0 0

#출력 예시 
6  // 1이 가장 많은 행 번호 : 6

#Fast Version
def mostOnesFast(A,n):
  i=0 #행번호
  j=0 #열번호
  row=0 #최대 1개수 행번호

  while((i<n)&(j<n)): # n x n 행렬에서 행과 열이 n보다 작을 때
    if A[i][j] ==1: # 만약 해당 원소가 1이면/
      j+=1 # 열방향으로 1추가
      row = i #행 업데이트
    else:
      i +=1 #해당 원소가 0이면 1행 추가

  return row

i와 j모두 커지는 성향을 가지고 있고, 0을 만났을 때 행을 추가해주기만 하면 된다. 그러면 자연스럽게 가장 많이 포함하고 있는 행을 찾을 수 있다.

 

---

문제 3 - 누적 평균

원시 데이터값들로 구성된 배열 X의 i-번째 누적평균(prefix average)이란 X의 i-번째에 이르기까지의 (i + 1)개 원소들의 평균이다. 즉, A[i] = (X[0] + X[1] + … + X[i])/(i + 1) 누적평균은 경제, 통계 분야에서 오르내림 변동을 순화시킴으로써 대략적 추세를 얻어내기 위해 사용된다. 일례로 부동산, 주식, 펀드 등에도 자주 활용된다.. 이 문제는 배열 X의 누적평균(prefix average) 배열 A를 구하는 프로그램을 구현하고 테스트하는데 관한 것이다.

# Slow Version
def prefixAverages1(X,n):
  A = []
  for i in range(n):
    sum=0
    for j in range(i+1):
      sum = sum + X[j]
      avg = sum/(i+1)
    A.append(int(sum / (i+1)))

  return A
  
n=3
X = [5,1,9]

A = prefixAverages1(X,n)
print(A)

위 함수를 살펴보면 i 번째 외부 반복에서는, 바로 전 i– 1번째 반복에서 구했던 [0 ~ i – 1]의 합에, i + 1 번째 원소 값 한 개만을 더해 현재 합을 얻어 평균을 구한다. 따라서 이를 수정하여 이전의 i – 1번째까지의 합을 보관하여다음 반복으로 전달하는 방식으로 반복한다면 현재 합을 구하는데 필요한 시간을 단축할 수 있다는 것을 알 수 있다. 이렇게 중간 합을 보관하는 방식으로 알고리즘을 개선한 함수 prefixAverage2는 누적평균값들을 선형 시간에 구할 수 있게 된다.

 

# Fast Version
def prefixAverages2(X,n):
  A = []
  sum=0
  for i in range(n): # 원소갯수만큼 반복함
    sum = sum + X[i]
    A.append(int(sum / (i+1)))

  return A
  
n=3
X = [5,1,9]

A = prefixAverages2(X,n)
print(A)