LUNA's Archive

버블 정렬, 삽입 정렬, 선택 정렬은 단순한 알고리즘들이지만 정렬하는데 시간이 많이 든다는 커다란 단점이 있다. 즉 자료가 많을때 이들 정렬 방법들을 부적절하고 보다 빠른 정렬 알고리즘이 필요하다. 이번에는 좀 더 빠른 정렬 방법중 하나인 합병 정렬(merge sort)에 대해 살펴보겠다. 합병 정렬? 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법이다. 이 정렬 방법은 분할 정복(divide and conquer) 기법에 바탕을 두고 있는데, 분할 정복 기법이란 하나의 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 방법을 말한다. 분할 정복 기법은 대개 순환 호출..

Data Structure & Algorithm 2019. 8. 25. 01:28

이번 시간에는 C++에서 동적 메모리 할당하는 방법에 대해 살펴보자. 동적 메모리 할당 방법을 보기 전에 동적 메모리 할당이란 무엇인가에 대해서 먼저 알아보겠다. 동적 메모리 할당의 개념 동적 메모리 할당이란 컴퓨터 프로그래밍에서 실행 시간동안 사용할 메모리 공간을 할당하는 것을 뜻한다. 사용이 끝나면 운영체제가 쓸 수 있도록 반납하고 다음에 요구가 오면 재할당을 받을 수 있다. 이것은 프로그램이 실행하는 순간 프로그램이 사용할 메모리 크기를 고려하여 메모리의 할당이 이루어지는 정적 메모리 할당(static memory allocation)과 대조적이다. 동적으로 할당된 메모리 공간은 프로그래머가 명시적으로 해재하거나 쓰레기 수집(garbage collection)이 일어나기 전까지 그대로 유지된다. C..

C++ 2019. 8. 23. 20:41

간단한 정렬 알고리즘 중 하나인 삽입 정렬에 대해서 알아보자. 삽입 정렬? 삽입 정렬이란 정렬이 되어있지 않은 부분의 데이터를 뽑아서 정렬된 부분의 적절한 위치에 삽입하는 방법이다. 즉, 배열에서 생각해보면 다음 그림과 같이 배열에서 정렬이 되지 않은 부분의 숫자를 정렬된 부분의 적절한 위치에 삽입하는 과정을 반복한다. 삽입 정렬은 추가적인 배열을 사용하지 않고 입력 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용하면 된다. 정렬되어 있지 않은 부분의 첫 번째 숫자가 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단한 후 해당 위치에 이 숫자를 삽입하게 되면, 정렬된 부분의 크기는 하나 커지게 되고, 정렬이 되지 않은 부분의 크기는 하나 줄어들게 된다. 이러한 삽입 연산을 정렬되지 않은 요소..

Data Structure & Algorithm 2019. 8. 23. 19:07

이번 시간에는 가장 이해하기 쉬운 정렬 알고리즘 중 하나인 선택 정렬에 대해 알아보겠다. 선택 정렬 알고리즘은 구현하기 굉장히 단순하지만 정렬시 많은 시간이 걸리는 비효율적인 방법이다. 선택 정렬? 선택 정렬 알고리즘이 어떻게 동작하는지 살펴보자. 먼저 정렬되지 않은 숫자들이 들어 있는 리스트와 정렬이 완료된 숫자들이 들어가는 리스트가 있다고 하자. 아래 그림과 같이 초기 상태에서 정렬된 리스트는 비어 있고 정렬되어야 할 숫자들은 모두 오른쪽 리스트에 들어 있다. 선택 정렬은 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 반복한다. 이것은 오른쪽 리스트가 공백 상태가 될 때까지 되풀이 된다. 위 설명에서는 두 개의 리스트로 나누어 설명했지만 실제로 선택 정렬을 구현하기 위해 ..

Data Structure & Algorithm 2019. 8. 21. 22:29

이번에는 평균적으로 매우 빠른 수행 속도를 보장하는 정렬 방법인 퀵 정렬에 대해 알아보겠다. 퀵 정렬(quick sort)? 퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 이 정렬 방법은 분할-정복법(divide and conquer)을 사용하고, 합병 정렬과 달리 리스트를 균등하지 않게 분할한다. 여기서 분할-정복법이란 문제를 작은 문제들로 분리하여 각각 해결하고 결과를 모아서 문제를 해결하는 전략이다. 그리고 분할-정복법은 대게 순환 호출을 이용하여 구현한다. 이제 퀵 정렬이 어떻게 이뤄지는지 살펴보자. 먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 여기서는 리스트의 첫 번째 요소를 피벗으로 하자. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다..

Data Structure & Algorithm 2019. 8. 5. 19:48

정렬 알고리즘의 한 종류인 버블 정렬에 대해 알아보겠다. Bubble sort? 버블 정렬이란 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 인접한 2개의 레코드를 비교하여 크기가 순서대로(ex. 오름차순 또는 내림차순) 되어 있지 않으면 서로 교환한다. 버블 정렬 알고리즘에대해 구체적인 개념을 살펴보면 아래와 같이 요약할 수 있다. 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를,... 이런 식으로 (마지막 -1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외하고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬..

Data Structure & Algorithm 2019. 7. 22. 21:18

일차원 배열과 마찬가지로 이차원 배열 또한 동적할당을 할 수 있습니다. 이 경우 사용자가 필요한 만큼의 크기의 메모리를 할당받아 사용하므로 불필요한 자원 낭비를 최소화할 수 있다. 2차원 배열을 어떻게 동적으로 할당 받는지 알아보기 전에 복습 차원에서 일차원 배열을 동적할당하는 방법을 살펴보자. var_type *pointer_name = malloc(sizeof(var_type) * length); int *numPtr = malloc(sizeof(int) * 10); 과 같이 int 크기에 10을 곱하여 동적으로 메모리를 할당하여 1차원 배열처럼 사용할 수 있다. 즉 []연산자를 이용하여 특정 인덱스에 접근할 수 있다. 2차원 배열 동적할당 다음으로 2차원 배열을 동적할당하는 방법을 다음 예제를 통해..

C 2019. 7. 16. 21:48

MCU 프로그래밍을 하다 보면 레지스터를 제어하기 위해 같은 주소에 여러번 값을 여러번 쓰는 경우가 빈번하고, 이런 경우 코드를 보면 앞에 volatile 키워드를 사용하는 경우를 볼 수 있다. 처음 이런 코드를 보면 언뜻 C언어를 배울 때 배웠던 volatile 키워드의 용법과 연결이 되지 않는다. 그래서 volatile이 왜 쓰이는지 같이 살펴보도록 하자. volatile? 우선 volatile 키워드가 무엇인지 알아보자. 변수를 선언할 때 앞에 volatile을 붙이면 컴파일러는 해당 변수를 최적화에서 제외하여 항상 메모리에 접근하도록 한다. 즉, volatile 변수를 참조할 경우 레지스터에 로드된 값을 사용하지 않고 매번 메모리를 참조한다. volatile [type] [variable_name..

C 2019. 7. 16. 14:44