알고리즘/개념 정리(9)
-
[알고리즘] 버블정렬
다음과 같은 5개의 데이터를 버블정렬로 정렬할 때의 순서입니다. 선택정렬의 경우 (1)번지의 값을 기준으로 두고 (2)번지, (3)번지.....순으로 즉 (1)→(2) (1)→(3) (1)→(4) (1)→(5) 순으로 비교했지만 버블정렬의 경우 인접한 다음 번지의 값을 비교합니다. (1)→(2) (2)→(3) (3)→(4) (4)→(5) 를 비교해 정렬하는 형태입니다. 그렇기 때문에 1회전 시 순으로 진행되다 종료됩니다. 결국 1회전이 끝나면 마지막 번지에 제일 큰 값이 들어갑니다. 각 회전 마다 비교대상은 이렇습니다. 반복값을 표현하면 i = 1, 4, 1 j = 1, 5-i, 1 이 됩니다. 위와 같은 경우는 5개의 데이터로 한정된 경우지만 그렇지 않고 n값으로 설정됐을 때는 결국 i = 1, n-1..
2021.10.12 -
[알고리즘] 선택정렬
n개의 데이터를 정렬할 때 총 회전 수는 n-1개 (마지막 데이터는 나머지가 다 정리된 뒤 남은 값이기 때문에 정렬할 필요가 없다) 다음은 5개의 데이터를 오름차순으로 정리하는 문제입니다. 5개의 데이터를 서로 비교해서 작은 값부터 왼쪽으로 보내 정렬하는 건데요. 이때 1회전 때 (1)번지의 값을 (2), (3), (4), (5) 번지의 값들과 비교해 가장 작은 값을 찾아 (1)번지에 넣어야 합니다. 비교가 끝나면 가장 작은 값이 (1)번지에 들어가면서 1회전이 끝나게 됩니다. 4회전까지 진행하고 나면 이런 형태가 되는데요. 이때 5회전을 하지 않고 종료됩니다. 남은 값이 하나일 때는 이미 다른 값들과 비교가 끝난 상태이기 때문이죠. 이때 비교하려는 두 값을 i, j 변수에 넣고 비교한다면 이런 형태가 ..
2021.10.12 -
[알고리즘] 최대공약수, 최소공배수, 유클리드 호제법
최대공약수(GCD) ex) 8와 12의 최대공약수 더 이상 나누어 떨어지는 값이 없는 서로소 상태일 때 종료되고 나눈 값을 모두 곱하면 최대공약수가 나옵니다. 최소공배수(LCM) ex) 8와 12의 최소공배수 구하려는 두 수를 곱한 값에서 최대공약수를 나누면 최소공배수가 나옵니다. 유클리드 호제법 최대공약수를 구하는 방법으로 구하려는 두 수를 비교해서 큰 수에서 작은 수를 0이 나올 때까지 빼나갑니다. ex) 8과 12의 최대공약수
2021.10.04 -
[알고리즘] 약수, 완전수, 부족수, 과잉수
약수 어떤 수로 정수가 나누어 떨어지는 수 ex) 8의 약수는 1, 2, 4, 8 완전수 자신을 제외한 약수의 합 = 자신 ex) 6의 약수는 1, 2, 3, 6 6을 제외한 수를 더하면 (1+2+3=6) 6으로 자신과 값이 같음 부족수 자신을 제외한 약수의 합 자신 ex) 20의 약수는 1, 2, 4, 5, 10, 20 20을 제외한 수를 더하면 (1+2+4+5+10=22) 22로 자신보다 값이 큼
2021.10.01 -
[알고리즘] 이진 검색(Binary Search)
이진 검색 찾을 데이터를 반씩 나눠가면서 원하는 데이터를 찾는 방식입니다. 아래는 1번지부터 10번지까지 데이터가 저장되어 있는 일차원 배열입니다. 만약 변수 key에 5를 받았다면 배열 안에 저장된 데이터에 5가 있는지 찾고 그 주소를 출력하는 것입니다. 원하는 데이터가 배열 안의 몇 번지에 위치하는지 찾는 방식인데요. 이진 검색은 처음에 말했다시피 찾을 데이터를 반씩 나눠가는데요. 전제조건으로 데이터가 오름차순이나 내림차순으로 정렬되어 있어야 이진 검색을 사용할 수 있습니다. 검색 방법은 먼저 배열 중 가운데 값을 찾습니다. 위의 배열에서는 (5) 번지가 되겠네요. 이 (5) 번지의 데이터 7 과 찾을 key 값을 비교합니다. 값을 비교해보니 찾을 값이 (5) 번지의 데이터 보다 작습니다. 그렇다면 ..
2021.09.30 -
[알고리즘] 대각선 채우기
대각선 채우기 5행 5열의 배열이 존재할 때 아래와 같은 형식으로 데이터가 들어가는 것을 말합니다. 데이터가 들어가는 순서는 대각선 방향이며 총 9회전 되는 형식인데요. 이렇게 2차원 배열이 나오게 되면 데이터가 들어가는 순서의 규칙을 찾아야 하는데 규칙을 찿기 위해서 데이터의 주소값을 살펴보겠습니다. 여기서 규칙을 찾을 수 있는데요. 회전 마다 주소값의 행과 열을 더한 값이 같은 걸 볼 수 있습니다. 여기서 또 하나 알 수 있는 건 만약 행이 변수처리 되어 있다면 역으로 더한 값에서 행을 빼는 방식으로 열을 구할 수 있다는 겁니다.
2021.09.29