Algorithm_Week_1

신태원·2020년 9월 6일
0

Algorithm

목록 보기
1/4
post-thumbnail

알고리즘의 정의

=> 어떤 문제를 푸는 알고리즘 = 어떤 입력에도 정확한 출력을 유한한 시간에 내는 프로그램

  • "어떤 입력" - 문제가 풀기 쉽든, 여렵든, 입력의 크기가 작건, 크건 문제를 풀 수 있다.
  • 어떤 경우에는 정답을 내지 못한다면 우리가 이 프로그램을 믿고 쓸 수 있겠는가?
  • "정확한 출력" - 문제가 요구하는 조건을 만족한다.
  • 정답이 요구하는 조건이 무엇인지를 명시할 수 있다.

문제 1) 100명의 학생들의 시험 점수중 최대값을 구하시오.

다양한 방법이 있겠지만, 그냥 단순히 두개의 인덱스를 차례대로 비교해주는 방법이 있다. 코드는 다음과 같다.

A = [1, 3, 5, 7, 2, 4, 6, 8]

max = A[0]
for i in range(1, len(A)):
   if A[i] > max:
	  max = A[i]
 
print(max)

위 방법의 경우 총 n-1번을 비교해준다.

문제 2) 100명의 학생들의 시험 점수중 가장 자주 나오는 값을 구하시오.

방법 a - 우선 두개의 인덱스를 차례대로 비교해주는 방식이긴한데, 모든 짝을 고려해야함으로, 비교 횟수는 n(n-1)/2가 된다. 사람들끼리 서로 중복없이 악수를 한번씩 해주는 걸 생각하면 된다. 코드는 다음과 같다.

def brutecount(X):
   C = [0 for _ in range(len(X))]
   for i in range(len(X)):
       for j in range(i+1, len(X)):
 	   if (X[i] == X[j]):
 	       C[i] = C[i] + 1
    mostfrequent = 0
    for i in range(1, len(X)):
 	if (C[i] > C[mostfrequent]):
 	    mostfrequent = i
    return X[mostfrequent]0

C라는 배열 X의 길이를 가진, 0으로 초기화된 배열을 만들어주고, X에서 두개의 인덱스를 비교해주며, 겹칠때마다 배열 C의 인덱스값을 하나씩 올려줌으로써 최빈값을 측정할 수 있도록한다.
하지만 위 방식은 시간이 너무 오래 걸린다는 단점이있다. 굳이 C라는 배열을 만들지 않더라도, 최빈값을 뽑아낼 수 있는 방법이 존재한다.

방법 b -

우선 코드부터 확인해보자.(단, 이 코드에는 오류가 있다고 하심. 같이 찾아보도록 하자)

def sortcount(X):
   C = sorted(X)
   current = C[0]
   count = 0
   maximal = C[0]
   maxcount = 0
   for x in C:
      if (x == current):
         count = count + 1
      else:
         if (count > maxcount):
            maxcount = count
	    maximal = current
	 current = x
	 count = 1
   return maximal

우선 이 코드는, 배열 X를 sorted() 함수를 통해 순서대로 정렬한 후, 탐색을 시작하는데, count값을 하나씩 올려주다가 숫자가 바뀌면 count값을 다시 0으로 만들어주되, maxcount라는 변수에 최고로 높았던 count의 값을 저장해주는 방식이다. 이런 방식을 사용하면, 굳이 모든 인덱스에 대하여 빈도수를 저장해주는 배열을 만들지 않더라도 최빈값을 뽑아낼 수 있다.

하지만, 위 코드를 보면 오류가 있다고 하니 찾아보자. 우선 개인적인 생각으로는, 13번 째 줄에 maximal을 current로 바꿔주는게 아니라, maxcount로 바꿔줘야되는 것같다. 왜냐하면, 나중에 for문을 마쳤을 때, return해주는 값이 maximal이기 때문에, maximal에다가 지금껏 나왔던 maxcount값을 저장해줘야되기 때문이다.
내가 생각했던 것은, 최빈값을 구하는게 아니라, 최빈값이 몇번이나 반복되었는지 이다. 이 코드에 오류는, 마지막 인덱스에대해 생각해주지 않았기 때문에, 정렬된 배열인 C 맨뒤에 마지막 원소랑 다른 값 하나를 추가해주기만 하면 된다.

방법 c - 값들을 이진 탐색 트리에 넣고, 같은 값이 있으면 빈도수를 늘린다.
이 경우는 최악의 경우(K=n)를 제외하고선, 방법 b 보다 빠르다고 할 수 있다.
(사실 방법 c는 정확하게 잘 모르겠음. 추후에 알게되면 내용 추가하겠음)
이진탐색트리는 원래 서로 다른 값을 저장하게되어있는데, 지금은 같은 값들이 두번이상 들어가도 의미가 있음.

왜 알고리즘을 배울까?

굉장히 현실적인 이유라고 한다. 바로 훗날 보게 될 코딩 테스트를 위해서. 코딩 테스트를 통과해야 서류도 낼 수 있고, 면접을 볼 수 있는 기회가 생긴다. 하지만 현재 프로그래밍을 배웠지만 코드를 짤 수 없는 사람이 많고, 생각을 코드로 옮기는 훈련이 된 사람은 의외로 적다고 한다.
때문에 우리는 알고리즘을 배워야 한다.

좋은 알고리즘의 조건

  • 간결하고 이해하기 쉬울 것

  • 효율적일 것

  • 코딩 테스트: "맞는데 왜 틀려요?"

    -생각하지 않은 경우에 오답
    -정답으로 생각한 코드보다 느려서 시간 제한에 못들어온다.

알고리즘의 예)

입력: U={1,2, ..., n} 중에서 특정한 수 하나만 빼고, 무작위의 순서로 총 n-1개의 숫자가 한번에 하나씩 입력됨
출력: U에서 빠진 하나의 수를 찾는다

알고리즘 1 -

크기가 n인 배열 A를 만들고 0으로 초기화한 다음에, U를 하나씩 훑으면서 U의 인덱스 k가 들어오면 A[k] = 1로 바꾼다. 인덱스를 다 받으면 A를 처음부터 뒤져서 A의 인덱스값이 0인 부분을 찾는다.
이때 필요한 공간: 배열 A[n]
필요한 시간: 가장 좋을 때는 1(빠진 수가 1일때), 가장 나쁠때는 n(빠진 수가 n일때) => 평균적으로는 n/2

알고리즘 2(개선된 알고리즘) -

1부터 n까지의 합을 구하는 공식은 n(n-1)/2 이기 때문에, n까지의 합 n(n-1)/2 에서 배열 U 의 모든 인덱스를 더한 값인 Z를 빼주면 빠진 숫자를 구할 수 있음.
이때 필요한 공간: 변수 Z
필요한 시간: 별도의 추가적인 검색 시간 필요 없음.

문제의 변형과 알고리즘의 수정

입력: U={1,2, ..., n} 중에서 특정한 수 둘만 빼고, 무작위의 순서로 총 n-2개의 숫자가 한번에 하나씩 입력됨
출력: U에서 빠진 두 수를 찾는다.

알고리즘 1 -
이 문제도 같은 식으로 풀 수 있다.

알고리즘2(개선된 알고리즘) -
각 인덱스들의 합 Z에 추가로, 각 인덱스들의 제곱의 합 Y도 구한다. 1 부터 n 까지 각 수들의 제곱의 합은 n(n+1)(2n+1)/6 이니, 이 값에서 Y값을 뺀 방정식과, n(n+1)/2 에서 Z를 뺀 방정식을 연립하면 u, v 를 구할 수 있음.

알고리즘 설계 과정

  • 크고 복잡한 문제의 해법을 바로 설계하는 것은 어렵다!
  • 문제를 분석하여, 풀 수 있는 크기의 작은 문제들로 나눈다.
  • 이 문제들을 푼 후, 각 문제들 간의 관계를 이용하여 해법을 연결한다.

예제: 하노이 탑

  • 알고리즘 설계 기법중 되부름(recursion)을 이용.
  • k개의 원반을 옮기는 문제 -> k-1개의 원반을 옮기는 문제가 됨.
  • 즉, 쉽게 풀 수 있을 때까지 문제의 크기를 줄인다.

예제: Stable Marriage

n명의 남자와 n명의 여자가 있을 때, 다음 조건을 만족하게 모든 남자와 여자를 1:1로 짝지울 수 있는가?

  • 일단은 제일 좋아하는 사람과 짝을 지어준 다음, 충돌이 일어났을 때, 선호도를 비교해 짝을 지어줌.

  • 알고리즘 수행 과정에서 모든 여성은 반드시 짝을 갖게 됨 - 남성 기준으로 알고리즘을 수행 과정에서 파트너가 바뀔 때마다 남성 파트너의 선호도는 감소함 (여성 파트너의 선호도는 증가함)

  • 따라서, 한 남성이 n번 이상 파트너가 바뀔 수 없다.(점점 좋아지거나 점점 안 좋아지는 방법밖에 없기 때문에) 총 n^2번 이상 파트너가 바뀔 수 없으므로 시간 복잡도는 O(n2).

    탐색 문제 1

정렬되지 않은 배열 E[1..n]에서, 어떤 값 k가 있는지 찾으시오. 만약 있다면 E[i]=k인 i를, 없으면 -1을 내보내시오.

int index, ans=-1;
for (index=0; index<n; index++){
   if (k==E[index]) {
      ans=index;
      break;
   }
}
return ans;

k를 E의 모든 인덱스와 비교해봐야 함으로, 1부터 최대 n번의 비교를 해야한다.

탐색 문제 2

정렬된 배열 E[1..n]에서, 어떤 값 k가 있는지 찾으시오. 만약 있다면 E[i]=k인 i를, 없으면 -1을 내보내시오.

a. E[1], E[b+1], E[2b+1], ....와 k를 비교. E[ib+1] <= k < E[(i+1)b+1] 인 i를 찾는다.

b. E[ib+1], E[ib+2], ... E[(i+1)b]에서 k 값을 찾는다.

(9/14 추가)

  • 우선 b개로 나눠서, 구간마다 하나씩 비교해준 다음에, 그 구간에 걸리면, 그 구간에서 하나씩 비교해줌.
    => 처음부터 하나씩 다 비교하는 것보다는 시간이 짧게 걸림.
    ➢ 시간복잡도: 최악의 경우 n/b + b번 비교. ( b개로 나누고, 걸린 구간에서는 하나씩(b개) 비교 해줘야 되니까 시간복잡도는 n/b + b 이다.)
    ➢ b=√n일 때 최소값 2√n = O(√n)
    (솔직히 잘 모르겠다. 추후에 알게되면 설명 추가함)
profile
일단 배우는거만 정리해보자 차근차근,,

0개의 댓글