분류 전체보기
-
퀵 정렬알고리즘/정렬 2021. 12. 25. 00:07
퀵 정렬 : 하나의 큰 문제를 두 개의 작은 문제로 분할하는 정렬 알고리즘이다. 특정한 값을 기준(pivot)으로 큰 숫자와 작은 숫자를 선택해 서로 교환한 뒤 배열을 반으로 나눈다. 일반적으로 pivot은 첫번째 원소부터 설정된다. Ex) pivot을 기준으로 왼쪽에선 큰값을 찾고, 오른쪽에선 작은 값을 찾는다. 3 7 8 1 5 9 6 10 2 4 3 2 8 1 5 9 6 10 7 4 3 2 1 8 5 9 6 10 7 4 (작은 값의 인덱스가 큰 값의 인덱스보다 작아 엇갈릴 때 작은 값과 pivot이 교환되어 첫번째 분할이 일어남.) 1 2 3 8 5 9 6 10 7 4 (3을 기준으로하여 왼쪽의 집합과 오른쪽의 집합에서 각각 pivot이 정해진 뒤 정렬을 수행함.) 위의 과정 반복 1 2 3 8 5..
-
삽입 정렬알고리즘/정렬 2021. 12. 24. 23:50
삽입 정렬: 각 숫자를 적절한 위치에 삽입하는 정렬 알고리즘. 반복적으로 새로운 원소를 이미 정렬된 데이터에 필요할 때만 그 위치를 정해주어 그 곳으로 넣어주는 것이 핵심이다. Ex) 1 10 5 8 7 6 4 3 2 9 1 5 10 8 7 6 4 3 2 9 1 5 8 10 7 6 4 3 2 9 1 5 7 8 10 6 4 3 2 9 ~ 1 2 3 4 5 6 7 8 9 10 시간복잡도 : O(N^2) 삽입 정렬은 앞에 정렬되어 있는 것을 알고있는 상황을 가정하므로 적절한 위치에 삽입만 하기때문에 O(N^2) 정렬 알고리즘 중에서는 효율적인 편임. (거의 정렬된 상태라면 모든 정렬 알고리즘에서도 굉장히 효율적.) Ex) 2 3 4 5 6 7 8 9 10 1 (이미 정렬되어 있으므로 한번씩만 비교하고 마지막 ..
-
버블 정렬알고리즘/정렬 2021. 12. 24. 23:47
버블 정렬: 옆에 있는 값과 비교해서 작은 값을 앞으로 보내기 사이클이 돌때마다 가장 큰 값이 맨뒤로 이동하게 된다. Ex) 1 10 5 8 7 6 4 3 2 9 1 5 8 7 6 4 3 2 9 10 1 5 7 6 4 3 2 8 9 10 ~ 1 2 3 4 5 6 7 8 9 10 시간 복잡도 : O(N^2) 구현은 쉬우나 가장 비효율적인 정렬 알고리즘. 실제로 선택정렬과 시간 복잡도는 같으나 수행 시간이 더 오래걸리는 이유 선택 정렬은 최솟값을 선택하여 마지막에만 스왑을 하지만 버블 정렬의 경우 비교 연산과 스왑을 사이클마다 수행하므로 연산 횟수가 사실상 훨씬 더 많아진다. #include int main() { int i, j, temp; int array[10] = {1, 10, 5, 8, 7, 6, ..
-
선택 정렬알고리즘/정렬 2021. 12. 24. 23:42
선택 정렬: 가장 작은 것을 반복적으로 선택하여 제일 앞으로 보내는 정렬 알고리즘. 정렬이 안된 숫자들 중에서 최소값을 선택하여 배열의 맨 앞쪽 요소와 교환한다. Ex) 정렬할 데이터 : 1 10 5 8 7 6 4 3 2 9 1 2 5 8 7 6 4 3 10 9 1 2 3 8 7 6 4 5 10 9 1 2 3 4 7 6 8 5 10 9 ~ 1 2 3 4 5 6 7 8 9 10 시간복잡도 : O(N^2) 최악의 경우 연산의 횟수가 기하급수적으로 늘어나므로 비효율적인 정렬 알고리즘. #include #include int main() { int i, j, min, index, temp; // index : 가장 작은 원소가 존재하는 위치 int array[10] = {1, 10, 5, 8, 7, 6, 4, ..
-
5. 메모리Computer Science/Boostcourse CS50 2021. 12. 24. 02:46
메모리에 대하여 본격적으로 설명드리기 앞서, 익숙한 이야기부터 해보려 합니다. 어떠한 변수를 선언한 후 그 변수에 사용자가 원하는 값을 대입하기 위하여 항상 입력을 받았습니다. #include int main() { int var; scanf("%d",&var); } 위와 같이 입력을 받을 때는 변수 앞에 & 연산자가 왜 붙는지 궁금하실 겁니다. &가 붙는 이유는 변수를 선언하면 컴퓨터 메모리 어딘가에 자료형의 크기만큼 메모리를 차지하는데, 여기서 차지하는 메모리마다 주소를 갖고 있습니다. 이 주소에 & 연산자를 통해 접근하여 메모리 공간 안에 있는 데이터를 변경시켜주기 위한 것입니다. #include int main() { int var; int *pvar = &var; scanf("%d",&var..
-
4-1 애너그램 판별 프로그램Computer Science/Boostcourse CS50 2021. 12. 24. 02:43
애너그램이란 문자의 구성은 같고, 배치 또는 뜻만 다른 문자열을 의미합니다. 버블 정렬 알고리즘을 이용하여 5개의 숫자로 구성된 문자열 애너그램을 판별하는 프로그램을 작성해보았습니다. #include #include #define SIZE 5 int check_anagram(char anagram[][6]); int main() { // 문자열의 끝인 null값까지 포함하여 6열까지 공간을 할당해줘야함. char anagram[2][6] = {"11132", "21131"}; if(check_anagram(anagram)) printf("Anagram True\n"); else printf("Anagram False\n"); } 정렬 후 문자열이 같은지 비교하기 위하여 strcmp 함수를 사용해야 하므로..
-
4. 알고리즘Computer Science/Boostcourse CS50 2021. 12. 24. 02:40
평소에 프로그래밍을 하면서, "알고리즘"이라는 단어를 많이들 접해보셨을 것입니다. 어떤 문제를 푸는 데 있어서도 알고리즘은 거의 항상 쓰이고, 중요한 개념이지만 정확히 무엇을 뜻하는지는 모른 채 학습을 진행합니다. 이번에는 알고리즘의 정의와 조건 그리고 중요성에 대해 말씀드리고자 합니다. 알고리즘은 입력값(input)을 출력값(output)의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열입니다. 간단히 말해서 주어진 문제를 해결하기 위한 절차나 방법이라고도 불립니다. 알고리즘의 중요한 조건으로는 정확성과 효율성이 있는데, 정확성은 본인이 선택한 알고리즘을 통하여 확실하게 그 문제를 해결할 수 있는지에 대한 것이고 효율성은 작업을 완료하기까지 얼마나 시간..
-
3-2 배열 Queue 구현Computer Science/Boostcourse CS50 2021. 12. 24. 02:37
Queue는 선형 자료구조 중 하나로, 은행 업무와 비유를 해보면 사람들은 대기표를 뽑고 은행원들은 대기표의 번호 순에 따라 업무를 해결해 주는데 이때는 당연히 먼저 온 사람이 업무를 먼저 보고 빠져나가는 식입니다. 이처럼 큐는 First In First Out으로 선입선출의 특징을 가지고 있습니다. 큐의 대표적인 기능을 간단히 살펴보자면 다음과 같습니다. 1. 큐에 데이터 삽입 (= 대기표 뽑기) 2. 큐에 쌓여있는 데이터 조회 (= 대기인원 보여주기) 3. 큐에 있는 데이터를 앞에부터 제거 (= 순서대로 대기인원 호출) 위의 세 가지 기능은 대표적인 것이고 이외에 추가적으로 큐가 비어있는지 확인을 해주는 함수와 큐에 들어갈 수 있는 공간이 꽉 찼는지 확인하는 함수를 구현해보았습니다. #in..