Algorithm5 [Algorithm] 삽입 정렬 (Insertion Sort) 삽입 정렬은 해당 요소를 올바른 위치에 삽입하는 정렬 알고리즘입니다. 다음과 같은 순서로 이루어집니다. i번째 원소 선택 (i = 1, 2, 3...) i번째 앞 원소들을 비교하여 올바른 위치에 i번째 원소 값 삽입 위 과정을 배열 원소의 개수만큼 반복 [그림 1] 배열이 있다고 했을 때, 오름차순으로 삽입정렬을 해 보겠습니다. 1. i번째 원소 선택 (i = 1, 2, 3...) 차례대로 원소를 선택합니다. 맨 처음 원소는 선택해도 아무런 의미가 없으므로 두 번째 원소부터 선택합니다. tmp에 i번째 원소 값을 따로 저장하는 이유는, 삽입하는 과정에서 i번째 원소 값이 손실되기 때문입니다. 2. i번째 앞 원소들을 비교하여 올바른 위치에 i번째 원소 값 삽입 앞 원소와 값을 비교합니다. [그림 3]에서.. 2023. 1. 18. [Algorithm] 버블 정렬 (Bubble Sort) 버블 정렬은 인접한 원소를 비교하여 정렬하는 정렬 알고리즘입니다. 이 모습이 거품 같다고 해서 버블 정렬이라는 이름이 붙었습니다. 다음과 같은 순서로 이루어집니다. n번째와 n+1번째 원소 비교 n+1이 끝에 도달할 때 까지 비교 위 과정을 배열 원소의 개수만큼 반복 [그림 1] 배열이 있다고 했을 때, 오름차순으로 버블정렬을 해 보겠습니다. 1. n번째와 n+1번째 원소 비교 [그림 2]처럼 첫 번째부터 비교하면 됩니다. 두 번째 원소가 더 작기 때문에 서로 swap합니다. 이제 두 번째 원소, 세 번째 원소를 비교하면 됩니다. 끝나면 세 번째, 네 번째 비교, 또 끝나면 네 번째, 다섯 번째... 2. n+1이 끝까지 도달할 때 까지 반복 계속 비교를 하다 보니 제일 큰 숫자인 13이 맨 뒤로 갔습니.. 2023. 1. 17. [Algorithm] 선택 정렬 (Selection Sort) 선택 정렬은 차례대로 하나의 값을 선택한 후 다른 값과 비교하여 정렬하는 정렬 알고리즘입니다. 다음과 같은 과정으로 이루어집니다. 기준 원소 선택 해당 원소 이후의 원소 값들과 비교 기준 원소가 마지막 원소까지 도달할 때 까지 반복 [그림 1]과 같은 배열이 있다고 했을 때, 오름차순으로 선택정렬을 해 보겠습니다. 1. 기준 원소 선택 기준 원소 선택은 차례대로 이루어집니다. 기준 원소는 i라고 하겠습니다. 우선 첫 번째 원소를 기준으로 잡고, 비교가 완료되면 두 번째, 세 번째... 2. 해당 원소 이후의 원소 값들과 비교 i 이후의 원소들을 비교합니다. [그림 3]에서 j 표시된 부분 하나하나 비교해주면 됩니다. i = 3일 경우에는 i보다 작은 j가 없으므로 넘어가겠습니다. 3. 기준 원소가 마지막.. 2023. 1. 16. [Algorithm] Dynamic Programming(동적 계획법)과 피보나치 수열 Dynamic Programming(DP, 동적 계획법)은 큰 문제를 작은 문제들로 분할하여 문제를 해결하는 방법입니다. 컴퓨터의 자원은 한정적이어서 무한히 값을 계산할 수 없기 때문에, 이미 계산된 값의 결과를 재활용하여 문제를 해결하는 방법을 만들어 내게 되는데 이것이 dynamic programming입니다. 뭐가 다이나믹한 건지 의문을 제시할 수도 있는데, 이 기법을 처음 고안한 Richard Bellman은 dynamic이라는 단어가 멋있어 보여서, 벨 연구소에서 펀딩을 받기 위해 이렇게 이름을 지었기 때문에 그냥 넘어가면 됩니다. '기억하며 풀기'라고 이해하면 됩니다. 아래의 순서로 DP 문제를 접근해 볼 수 있습니다. 1. DP의 조건 DP를 이용해 문제를 해결하기 위해서는 아래 3가지 조건.. 2023. 1. 11. [Algorithm] C++로 구현한 행렬 곱셈 알고리즘 행렬의 곱셈 알고리즘은 여러 가지가 존재합니다. 이번 글에서는 행렬의 곱셈 방식과 이를 토대로 한 단순 곱셈 알고리즘을 유도해 보겠습니다. $$ \begin{bmatrix} a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ \end{bmatrix} \times \begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \\ b_{31} & b_{32} \\ \end{bmatrix} $$ 위와 같은 행렬이 존재할 때, 앞의 행렬을 A, 뒤의 행렬을 B라고 하겠습니다. 행렬 A의 크기는 2*3이고, 행렬 B의 크기는 3*2입니다. 1. 행렬 곱셈의 조건 행렬 곱셈을 하기 위해서는 행렬 A의 열과 행렬 B의 행의 개수가 동일해야 합니다. 예시로 .. 2022. 12. 28. 이전 1 다음
