Q. 배열에 빠진 수를 찾으세요.
서로 다른 [1, n]범위의 n-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)
- 완전탐색
- 범위 내의 숫자를 하나씩 존재하는지 검사
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)
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)과 유전법칙을 모방한 확률적 탐색기법이다.
→ 알고리즘 이라기 보다는 최적화 문제를 풀기 위한 방법론에 가까움
개념 및 용어
- 염색체(Chromosome): 하나의 해(solution)를 표현한다. 생물학적으로는 유전물질을 담고 있는 집합
- 유전자(gene): 염색체를 구성하는 요소로, 하나의 유전 정보를 나타냄
- 자손(offspring): 특정 시간 t에 존재했던 염색체로부터 생성된 염색체를 t에 존재했던 염색체의 자손이라고 함 → 이전 세대와 비슷한 유전정보를 가짐
- 적합도(fitness): 해당 문제에 대해 염색체가 표현하는 해가 얼마나 적합한지 나타냄 (어떤 염색체가 갖고 있는 고유값)
유전 알고리즘의 동작 단계
- 초기 염색체의 집합 생성
- 초기 염색체의 적합도 계산
- 현재 염색체로부터 자손 생성 → 이 단계에서 알고리즘의 성능을 향상시키기 위한 기법이 적용된다.
- 생성된 자손의 적합도 계산
- 종료 조건을 판별
- 거짓 → 3으로 이동
- 참 → 알고리즘 종료
연산
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% 등 아주 낮은 확률로 발생
→ 변이의 결과가 우수하면 살아남고, 열등하면 도태될 것
- reverse: 임의의 유전자를 하나 선택해 0→1, 1→0으로 바꾸는 연산
- exchange: 두 유전자를 임의로 선택해 값을 교환
- 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]
- insert: 임의로 값을 추가
- 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도 회전시켰을 때 가로, 세로가 바뀌게 된다.
- 배열의
n
,m
을 바꾼rotate
배열을 선언한다. - 이중
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;
}
'Team Project (2021-2022) > CS Study' 카테고리의 다른 글
[7주차]Garbage Collection, 함수형 언어 (0) | 2022.03.21 |
---|---|
[5주차] P NP 문제, ArrayList와 LinkedList, Java vs Python (0) | 2022.03.14 |
[4주차] 동기/비동기, HashMap 동작 방식, Array vs List vs Vector의 차이점 (0) | 2022.02.28 |
[2주차] 알고리즘: 배열, map, hashmap, set (0) | 2022.02.14 |
[1주차] 알고리즘: Dynamic Programming, 배열 (0) | 2022.02.09 |