Engineering Note

삽입정렬 삽입정렬은 선택한 요소를 그 보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘이다. 선택정렬과 비슷하게 보일 수 있지만 단순 선택 정렬은 값이 작은 요소를 선택해 알맞은 위치로 옮긴다는 점이 다릅니다. 삽입정렬의 구체적 개념(오름차순 기준) 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 이다. 이미 정렬된 배열 부분과 비교 하기 위해서 두번째 요소(1번 인덱스)부터 선택하여 첫번째 요소(0번 인덱스)와 비교하여 오름차순에 위배된다면 오름차순이 되도록 앞쪽에 삽입합니다. 위의 단계를 수행하기위해 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후..

선택정렬 가장 작은 요소를 찾아 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다. 선택정렬 알고리즘의 구체적 개념(오름차순 기준) 첫 번째 요소부터 마지막 요소 까지 비교하여 가장 작은 값을 찾아 첫 번째 요소에 위치 시킨다. 다시 두 번째 요소부터 마지막 요소 까지 비교 하여 가장 작은 값을 찾아 두 번째 요소에 위치 시킨다 위 과정을 반복 수핸한다. 선택 정렬 알고리즘 C언어 구현 SelectionSort 함수 배열의 주소와 사이즈를 인수로 받아 Min 함수로 최소값 찾고 Swap 함수로 교환 Min 함수 배열의 주소와 최소값 찾을 구간을 넘겨주면 구간에서 첫번째 요소인덱스를 min에 대입하고 구간에서 루프문으로 두번째 요소부터 마지막 요소까지 list[min]과 비교 하며 최소값 인덱스값..

버블 정렬 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복한다. 버블정렬 알고리즘의 구체적 개념(오름차순 기준) 첫 번째 요소와 두 번째 요소를 비교하여 첫 번째 요소가 두 번째 요소보다 크다면 두 요소 값을 교환한다.두 번째 요소와 세 번째요소를 비교하여 두 번째 요소가 세 번째 요소보다 크다면 두 요소 값을 교환한다. 이런 식으로 세 번째와 네 번째를 ... (마지막-1)과 마지막 요소를 비교하여 (마지막 -1)요소가 마지막요소 보다 크다면 두 요소의 값을 교환한다. 위 단계를 수행하고 나면 가장 큰 값이 마지막 요소에 배치된다. 위 단계를 1회전 수행 후 2단계 수행시 비교는 마지막 요소는 제외한다. 즉, (마지막요소-2)와 (마지막요소-1)까지 비교, 교환을 수행한다. 2회전을 끝내고 나면 (..

01-1.자료구조에 대한 기본적인 이해 자료구조란 무엇인가? 자료구조에서는 데이터를 표현하고 저장하는 방법에 대해서 설명한다. 우리는 C언어를 공부하면서 다음과 같은 이야기를 접한적이 있다. "프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다." 위에서 말하는 '데이터의 표현'은 '데이터의 저장'을 포함하는 개념이다. 그리고 이렇듯 '데이터의 저장'을 담당하는 것이 바로 자료구조이다. ex) 1. "정수를 저장하기 위해서 int형 변수를 선언" 2. "개인정보를 저장하기 위한 목적으로 구조체 정의" 넓은 의미에서 int형 변수도, 구조체의 정의도 자료구조에 속한다. int형 변수도, ,구조체도 데이터를 표현 및 저장하는 하나의 방법이기 때문..

정렬이 된 배열에서 사용이 가능하다. 정렬된 배열 arr에서 탐색시작 인덱스: left 탐색마지막 인덱스 : right 구간 중간 인덱스 : middle == (left + right)/2 1. 중간 값과 찾는 값 비교 2. 찾는 값이 중간값 보다 작으면 중간값 좌측 구간을 탐색하도록 right값 갱신(middle-1) 찾는 값이 중간값 보다 크면 중간값 우측 구간을 탐색하도록 left값 갱신(middle+1) 3. 1,2조건 반복 1.left와 right가 교차할 경우 2.값을 찾지못했을 경우 -1 에러값을 반환하도록 구현

재귀함수는 자신의 이름의 함수를 호출하면서 종료조건에 수렴해 가야한다. 그러므로 반드시 종료조건이 있어야한다. 종료조건이 없다면 무한 재귀에 빠지면서 프로그램이 종료된다. 재귀를 이해하기 위해서는 함수의 수행 순서를 이해할 필요가 있다. 함수가 호출 되면 스택에는 함수의 매개변수, 호출이 끝난뒤 돌아갈 반환 주소값, 함수에서 선언된 지역 변수 등이 저장됩니다. 이렇게 스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택 프레임(stack frame)이라고 합니다. 이러한 스택 프레임 덕분에 함수의 호출이 모두 끝난 뒤에, 해당 함수가 호출 되기 이전 상태로 되돌아 갈 수있습니다. 스택프레임의 동작방식을 스택 자료구조형태로 이해하는 것은 조금 불편한 부분이 있기 때문에 트리구조의 모양으로 그려서도 설명하..

Queue 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조입니다. 하지만 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입(FIFO, First In First Out)인 점이 스택과 다릅니다. 생활에서 볼수 있는 큐의 에는 은행창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열을 들 수 있습니다. 큐에 데이터를 넣는 작업을 enqueue라하고, 데이터를 꺼내는 작업을 dequeue 라고합니다. 또 데이터를 꺼내는 쪽을 front라 하고, 데이터를 넣는 쪽을 rear라고 합니다. 배열과 front, rear 변수를 사용해 쉽게 queue를 구현할 수 있습니다. front와 rear라는 변수를 도입한 이유는 현실세계처럼 queue를 컴퓨터상에서 구현하려면 많은 자원을 필요로 합..

* 자료구조 코드 구현시 Tip 1.해당 자료구조 개념에 대한 이해 2.이해한 내용을 바탕으로 해당 자료구조에 어떤 데이터와 어떤 함수인터페이스가 필요할지 생각 (위의 내용을 추상화라고 하고 이 추상화하는 것이 중요함) 3.기본적인 코드를 구현한 후에는 예외상황들에 대한 코드 최적화 작업을 진행 ex) 스택에서는 데이터를 넣고 뺄 메모리공간을 쉽게 만들수 있는 배열로 메모리공간을 생성하고 순서(데이터 위치상태)를 기억하기 위한 top변수가 필요함을 생각합니다. 그리고 데이터를 넣는 Push함수, Pop함수를 생성합니다. 그리고 코드 최적화 단계에서 어플리케이션 별로 스택이 필요 할 수 있으므로 위의 배열 메모리공간과 top변수를 위한 구조체를 생성하고 초기화 함수를 통해 해당 배열이 프로그램 동작시 공간..