[3주차] 알고리즘: 배열, 유전알고리즘, 행렬뒤집기

Q. 배열에 빠진 수를 찾으세요.

서로 다른 [1, n]범위의 n-1개의 숫자가 들어있는 리스트가 주어집니다. 주어진 배열에 빠진 수를 찾으세요.

1. 정렬sort

• 배열에 숫자가 있는지 하나씩 검사하는 방법

def sort(A):
    A.sort()
    for i in range(1, len(A) + 1):
        if cur not in A:
            print("Missing number is " + str(i))
            break

• 시간복잡도: O(nlogn)
  • 파이썬 내장함수 .sort 시간 복잡도가 O(nlogn)
• 공간복잡도: O(1)

1. 완전탐색
   • 범위 내의 숫자를 하나씩 존재하는지 검사

def bruteforce():
    N = len(A)

    for i in range(1, N+1):
        flag = False
        for x in A:
            if i == x:
                flag = True
                break

        if flag is False:
            print("Missing number is " + str(i))
            break

• 시간복잡도: O(n²)
• 공간복잡도: O(1)

1. XOR

• XOR 연산

• 

• 풀이

• 

def xor(A):
    N  = len(A)
    X1 = A[0]
    X2 = 0

    # X1 = A1 ^ A2 ^ A4
    for i in range(1, N):
        X1 = X1 ^ A[i]

    # X2 = A1 ^ A2 ^ A3 ^ A4
for cur in range(1, N+2):
        X2 = X2 ^ cur

    print("Missing number is " + str(X1 ^ X2))

• 시간복잡도: O(n)
• 공간복잡도: O(1)

🚨 숫자가 커질 경우 정수 오버플로우 문제가 발생할 수 있다.

• 추가 해설
• A=[5, 6, 1, 4, 2] 일 경우

X1 = X1 ^ A[i]

5 = 5 ^ 6
ans: 3
3 = 3 ^ 1
ans: 2
2 = 2 ^ 4
ans: 6
6 = 6 ^ 2
ans: 4
final X1 = 4

Missing number is 3

Q. 유전 알고리즘에 대해서 설명하세요.

생물체가 환경에 적응하면서 진화해가는 모습을 모방하여 최적해를 찾아내는 검색 방법

생물의 진화과정인 자연선별(nature selection)과 유전법칙을 모방한 확률적 탐색기법이다.

→ 알고리즘 이라기 보다는 최적화 문제를 풀기 위한 방법론에 가까움

💡 매 세대에서 각 개체의 적응도(fitness)를 평가하여 이에 따라 다음에 생존할 개체들을 확률적으로 선별(selection)한다. 선별된 개체 중 일부가 짝을 지어 교배해 자손을 생성하고, 이때 교차(crossover)가 일어나면서 부모의 유전자가 자손에게 상속되고 돌연변이가 일어날 수 있다. 자손이 부모로부터 좋은 유전형질을 상속받으면 다음세대는 그 이전세대보다 더 좋아진다.

*다윈의 적자생존 이론: 다양한 개체 중 우수한 개체만이 자손을 남기고, 열등한 개체는 도태된다. 남은 개체는 다시 돌연변이를 일으켜 더 우수한 개체가 되거나 퇴화한다.

개념 및 용어

• 염색체(Chromosome): 하나의 해(solution)를 표현한다. 생물학적으로는 유전물질을 담고 있는 집합
• 유전자(gene): 염색체를 구성하는 요소로, 하나의 유전 정보를 나타냄
• 자손(offspring): 특정 시간 t에 존재했던 염색체로부터 생성된 염색체를 t에 존재했던 염색체의 자손이라고 함 → 이전 세대와 비슷한 유전정보를 가짐
• 적합도(fitness): 해당 문제에 대해 염색체가 표현하는 해가 얼마나 적합한지 나타냄 (어떤 염색체가 갖고 있는 고유값)

유전 알고리즘의 동작 단계

1. 초기 염색체의 집합 생성
2. 초기 염색체의 적합도 계산
3. 현재 염색체로부터 자손 생성 → 이 단계에서 알고리즘의 성능을 향상시키기 위한 기법이 적용된다.
4. 생성된 자손의 적합도 계산
5. 종료 조건을 판별
   1. 거짓 → 3으로 이동
   2. 참 → 알고리즘 종료

💡 t에 존재하는 염색체의 집합으로부터 **적합도가 가장 좋은 염색체를 선택**하고,

선택된 해의 방향으로 검색을 반복하면서

최적해를 찾아가는 구조로 동작한다.

연산

💡 연산의 종류

1. 초기 염색체를 생성하는 연산 (임의의 값)
2. 적합도를 계산하는 연산
3. 적합도를 기준으로 염색체를 선택하는 연산 (룰렛휠방식)
4. 선택된 염색체들로부터 자손을 생성하는 연산 (crossover방식)
5. 돌연변이 연산

1️⃣ 초기 염색체를 생성하는 연산

• 가장 많이 사용되는 방식은 규칙 없이 임의의 값으로 염색체를 생성하는 것

Random rand = new Random();
int[] chromosome = new int[SIZE_CHROMOSOME];

for(int i = 0; i < SIZE_CHROMOSOME; i++) {
    chromosome[i] = **rand.nextInt(MAX_VAL_GENE)**;
}

import random, copy
sample_chrm = range(1,10) # a feasible solution
init_population = [ ] # an empty list
random.seed(0)
population_size = 5
for i in xrange( population_size ):
 new_chrm = copy.copy( sample_chrm )
 random.shuffle( new_chrm)
 init_population.append( new_chrm)

2️⃣ 적합도를 계산하는 연산

염색체에 표현된 정보를 기반으로 적합도(fitness, 염색체가 표현하는 해가 얼마나 적합한지 나타내는)를 계산하는 연산

→ 해결하고자 하는 문제에 따라 매우 다른 편

3️⃣ 적합도를 기준으로 염색체를 선택하는 연산

보통 룰렛 휠 선택 (roulette wheel selection)방법을 이용한다.

→ 이 방식을 이용하면 적합도가 높은 염색체가 더 높은 확률로 선택되도록 설정하는 동시에, 염색체의 다양성도 유지할 수 있다.

4️⃣ 선택된 염색체들로부터 자손을 생성하는 연산

두 부모 염색체로부터 자손 염색체를 생성한다.

주로 Crossover연산을 이용해 자손을 생성한다. (division point는 임의로 선택됨)

5️⃣ 돌연변이 연산 (mutation)

지역 최적점에 빠지는 문제를 해결하기 위해 새롭게 생성된 염색체에 확률적으로 돌연변이가 발생하도록 한다.

→ 일반적으로 0.1%, 0.05% 등 아주 낮은 확률로 발생

→ 변이의 결과가 우수하면 살아남고, 열등하면 도태될 것

1. reverse: 임의의 유전자를 하나 선택해 0→1, 1→0으로 바꾸는 연산
2. exchange: 두 유전자를 임의로 선택해 값을 교환
3. import random chrm = [4, 1, 5, 6, 9, 2, 3, 7, 8] position1 = random.randint(0, len(chrm)-1 ) position2 = random.randint(0, len(chrm)-1 ) chrm[position1], chrm[position2] = chrm[position2], chrm[position1]
4. insert: 임의로 값을 추가
5. import random chrm = [4, 1, 5, 6, 9, 2, 3, 7, 8] element_position = random.randint(0, len(chrm)-1 ) insert_position = random.randint(0, len(chrm)-2 ) element_value = chrm[element_position] del chrm[element_position] chrm.insert( insert_position, element_value )

외에도 많은 종류가 있다.

사용

• 해를 염색체 꼴로 나타낼 수 있고, 적합도 함수로 평가할 수 있을 때 사용 가능
• 데이터가 방대해 해를 구하는데에 오랜 시간이 소요되는 문제에 주로 사용됨

Q. pivotal(대각선이 고정인 행렬) 3x3, 4x4를 뒤집는 로직을 짜보세요 재귀를 써야함.

재귀란?

어떤 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 어떤 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 방식이다.

N*N인 2차원 배열을 90도 회전시키기

아래 그림처럼 기준선을 잡은 뒤, 맞은 편의 숫자들을 하나씩 교환해준다.

1번. 노란색 줄을 기준으로 초록색, 파란색 줄의 숫자들을 하나씩 교환.

2번. 7, 5, 3의 대각선 줄을 기준으로 숫자들을 하나씩 교환.

⇒ 90도 회전한 모양.

public void change(int[][] matrix) {
    int n = matrix.length;

    // 1번. 
    for (int i = 0; i < n / 2; i++) {
        for (int j = 0; j < n; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[n - i - 1][j];
            matrix[n - i - 1][j] = tmp;

        }
    }

    // 2번. 
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
}

재귀를 사용하여

회전시키려는 arr 2차원 배열이 있을 때, 90도 회전시켰을 때 가로, 세로가 바뀌게 된다.

1. 배열의 n, m 을 바꾼 rotate 배열을 선언한다.
2. 이중 for 문을 돌면서 rotate[i][j] = arr[n-1-j][i] 식으로 rotate 배열을 채워준다.

static int[][] rotate(int[][] arr) {
    int n = arr.length;
    int m = arr[0].length;
    int[][] rotate = new int[m][n];

    for (int i = 0; i < rotate.length; i++) {
        for (int j = 0; j < rotate[i].length; j++) {
            rotate[i][j] = arr[n-1-j][i];
        }
    }

    return rotate;
}