전체 글58 파스칼의 삼각형 파스칼의 삼각형은 자연수를 삼각형 모양으로 배열한 것을 말합니다. 1303년 중국인에 의해 유럽에 알려졌으나 이 삼각형에서 흥미로운 성질을 많이 발견한 프랑스의 철학자이자 수학자인 파스칼(Pascal)의 이름을 따서 파스칼의 삼각형이라 부르게 되었습니다. 파스칼의 삼각형을 잘 이용하면 여러 가지 재미있는 문제를 해결하는데 도움이 됩니다. 예를 들면, 사과와 배 두 종류만 파는 과일가게에 갔는데 과일을 사는 방법의 경우의 수를 생각해 보면 둘을 모두 사는 경우가 1가지, 둘 중 하나를 사는 경우는 사과만 살 경우와 배만 살 경우가 있으므로 2가지, 둘 다 사지 않는 경우의 수 1가지가 있습니다. 이것은 그림에서 세번 째 줄의 숫자 1, 2, 1과 같습니다. 그러면 사과, 배, 감의 세가지 과일을 사는 경우.. 2020. 7. 13. [C언어 알고리즘] 정렬(5) - 쉘정렬(Shell sort) 삽입정렬(Insertion sort)은 이미 정렬되어 있는 경우나 대충 정렬되어 있는 경우 좋은 성능을 보이지만 그렇지 않은 경우 속도가 매우 느립니다. 왜냐면 삽입정렬은 인접한 요소와 비교를 하기 때문인데 역순으로 배열된 경우 가장 작은 값이 맨 뒤에 있으므로 배열의 크기만큼 비교와 이동을 해야해서 비효율적입니다. 쉘정렬(Shell sort)는 이런 문제점을 개선하기 위해 일정 간격으로 떨어진 값을 삽입하여 정렬하는 방법으로 점진적으로 해결하는 형태입니다. 예를 들어 간격이 10이라면 0, 10, 20, 30...의 요소를 뽑아 이 요소간의 삽입정렬을 합니다. 다음으로 1을 더해 1, 11, 21, 31...의 요소 간 삽입정렬을 하는 식으로 반복하여 9, 19, 29, 39 ...의 요소를 마지막으로.. 2020. 7. 11. [C언어 알고리즘] 정렬(4) - 거품정렬(Bubble sort) 이번 시간은 거품정렬(Bubble sort)입니다. 거품정렬은 인접요소(Adjacent element)를 비교하여 교환하는 모습이 마치 거품이 보글보글 하는 모양이라서 붙은 이름입니다. 거품정렬의 의사코드(Pseudo code)는 다음과 같습니다. 거품정렬 알고리즘 1. i=0 2. i가 n-1이면 끝낸다 2.1 j=1 2.1.1 j가 n-i가 되면 2.2로 간다. 2.1.2 a[j-1] > a[j]이면 두 값을 교환 2.1.3. j를 하나 증가 시키고 2.1로 돌아간다. 2.2. i를 하나 증가 시기코 2로 돌아간다. j가 n-i까지 반복하는 이유는 n-i이후는 이미 가장 큰 값들로 정렬이 되어 있는 상태이기 때문입니다. 첫 번째 수행은 다음과 같습니다. 첫 번째 수행에서 값을 교환하여 배열의 가장 마.. 2020. 7. 9. [C언어 알고리즘] 정렬(3) - 삽입정렬 (Insertion sort) 삽입정렬(Insertion sort)은 선택정렬(Selection sort)와 함께 많이 사용되는 아주 간단한 정렬 방법입니다. 카드 뭉치로 예를 들자면, 이미 정렬된 카드패에 새로운 카드를 다른 항목사이에 끼워넣는 것으로 생각하시면 됩니다. 삽입정렬 알고리즘 우선 삽입 정렬의 의사코드(Pseudo code)를 보면 다음과 같습니다. 1. i=1 2. j=i 3. a[j-1] > a[i] 이고 j > 0인 동안 3.1. a[j] = a[j-1] 3.2. j-- 4. a[j] = a[i] 위 코드를 보면 배열에서 i번째 미만은 이미 정렬된 상태이며 i번째 항을 적절한 위치에 삽입하는 과정을 반복합니다. 그림을 통해서 살며보면 우선 다음과 같은 문자 배열이 있다고 가정을 합니다. 첫 번째 수행 시작은 i가 .. 2020. 7. 8. [C언어 알고리즘] 정렬(2) - 선택정렬 (Selection sort) 선택정렬은 가장 간단한 정렬 알고리즘입니다. 실생활 속에서 가장 많이 사용하는 예를 들자면, 카드패 정렬입니다, 카드 뭉치에서 가장 작은 숫자 카드를 맨앞에 놓고 그 다음 작은 숫자카드를 놓고 ...의 작업을 반복하여 정렬하는 방법을 선택정렬 이라고 합니다. 선택정렬 알고리즘 이번 포스팅에서는 문자형 배열을 정렬하는 것으로 해보겠습니다. 의사코드(Pseudo code)를 적어보면 다음과 같습니다. 1. i =0 2. i 가 n-2 이면 끝난다. 2-1. 배열의 i항 부터 n-1항까지 중 최솟값을 찾아 min에 저장한다. 2-2. 배열의 i항과 min항을 교환한다. 2-3. i를 1 증가시키고 2로 돌아간다. 다음과 같은 문자형 배열이 있다고 가정해 봅시다. 첫 번째 수행은 아래와 같습니다. 가장 먼저 첫.. 2020. 7. 7. [C언어 알고리즘] 정렬(1) - 개요 알고리즘에 대한 첫번째 포스팅으로 정렬(Sort)을 선택했습니다. 정렬(Sort)은 컴퓨터를 통해 문제해결을 하는데 역사와 함께 했으며, 가장 연구가 많이 되어 왔습니다. 정렬의 기본 개념은 매우 간단한데요, 바로 "줄을 서시요~" 입니다. 줄을 세울 대상을 자료(Data) 라 하고 줄을 세울 기준을 키(Key)라고 합니다. 예를 들어, 학생 20명인 반에서 번호 순으로 일렬로 서라고 한다면 학생들이 데이터, 번호가 키가 되겠죠. 번호가 작은 학생 부터 줄을 선다면 오름차순(Ascending order), 번호가 큰 학생부터 줄을 선다면 내림차순(Decending order)라고 합니다. 정렬 알고리즘의 구분은 구현의 복잡도에 따라 알고리즘이 간단한 선택정렬(Selection sort), 삽입정렬(Ins.. 2020. 7. 7. 이전 1 ··· 4 5 6 7 8 9 10 다음
