본문 바로가기

cs50

(4)
알고리즘 기초 (삽입정렬) Harvard CS50 x Edwith 강의를 학습하며 정리한 내용입니다. 삽입정렬 삽입정렬은 자료를 정렬하는 알고리즘중 하나로 자료가 정렬된 부분과 정렬되지 않은 부분으로 나누어 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법입니다. 그렇기 때문에 자료를 여러 번 비교하거나 교환할 필요가 없으며 배열이 길수록 효율이 떨어지지만 구현은 간단한 방법입니다. 예제 3, 6, 2, 5, 1, 4 의 배열을 정렬해보자. [3] | 6 | 2 | 5 | 1 | 4 [3] | [6] | 2 | 5 | 1 | 4 [2] | [3] | [6] | 5 | 1 | 4 [2] | [3] | [5] | [6] | 1 | 4 [1] | [2] | [3] | [5] | [6] | 4 [1] | [2]..
알고리즘 기초 (선택정렬) Harvard CS50 x Edwith 강의를 학습하며 정리한 내용입니다. 선택정렬 우리는 보통 정렬되지 않은 배열보다 정렬이 된 배열에서 자료를 더 쉽게 찾을 수 있습니다. 이런 정렬을 위한 알고리즘 중 선택정렬은 배열의 자료중 가장 작은 단위를 찾아 첫번째 위치의 수와 교환하는 방식을 말합니다. 선택정렬은 실행되는 동안 교환 횟수는 줄어들지만 각 자료를 비교하는 횟수는 증가한다는 특징을 가지고 있습니다. 선택정렬의 비교 횟수 선택정렬은 버블정렬과 다르게 몇 번의 교환을 해주었는지 교환 횟수 대신 비교 횟수를 기준으로 합니다. 오름차순이 기준이면 최소값을 찾아 왼쪽으로 정렬하고 내림차순이면 최대값을 찾아 오른쪽으로 정렬을 해주면 됩니다. 선택정렬은 n(n-1)/2 이란 비교횟수 연산공식을 가지고 있고 ..
알고리즘 기초 (버블정렬) Harvard CS50 x Edwith 강의를 학습하며 정리한 내용입니다. 버블정렬 정렬 알고리즘중 하나인 버블정렬은 두 개의 인접한 자료의 값을 비교하며 위치를 교환하는 방법 (A - B) 버블정렬에 대해서 버블정렬은 한번에 단 두개의 자료만 정렬하기 때문에 좁은 범위의 정렬로 단 하나의 자료를 정렬하기 위해 불필요한 교환과 낭비가 발생할 수도 있습니다. 예를 들어 4, 3, 1, 0 과 같이 내림차순으로 정렬된 경우 오름차순으로 정렬하기 위해선 총 3번을 수행해야 합니다. 즉 n개의 요소를 정렬하기 위해 n-1번을 수행해주어야 하며 이는 곧 비효율적인 최악의 상황의 경우 최대횟수를 실행해줘야 하는 것을 의미합니다. 결론적으로 버블정렬은 한번의 수행으로 모든 범위가 정렬되지 않기때문에 인접한 데이터들의..
알고리즘 기초 (선형탐색) Harvard CS50 x Edwith 강의를 학습하며 정리한 내용입니다. 선형탐색 찾고자 하는 자료가 발견될때까지 처음부터 끝까지 차례대로 탐색하는 방법 선형탐색의 효율성과 비효율성 선형탐색은 처음부터 끝까지 차례대로 탐색함으로써 정확도는 높지만 효율적이지 못한 방법입니다. 만약 찾고자 하는 자료의 길이가 n이라고 가정한다면 최악의 경우 n번만큼 확인을 해야합니다. 이보다 더 최악은 자료의 길이 안에 찾는 자료가 없는 경우이며 이 길이가 작은 단위가 아닌 100만, 1000만의 경우 속도나 효율성 측면에서 좋지 못한 선택이 되기도 합니다. 무조건 나쁘고 효율적이지 못할 것 같지만 자료가 정렬되어 있지 않거나 어떠한 기준이나 정보 없이 하나씩 찾아야 하는 경우엔 선형탐색을 사용하는 것이 효율적이고 유용합..