코딩 기록 저장소

1. 평균 선형 시간 선택 알고리즘 - 퀵 정렬처럼 분할한 후 자기호출 방법을 쓰면 평균적으로 선형 시간에 i번째 작은 원소를 찾을 수 있음. 그렇지만 이 알고리즘은 최악의 경우 O(n²) 시간이 소요됨. - 이번 알고리즘은 단점을 개선해서 최악의 경우에도 선형 시간에 i번째 작은 원소를 찾을 수 있게 함. - n개의 원소가 규칙 없이 저장된 배열에서 i번째 작은 원소를 찾으려 함. - 분할 알고리즘이 리턴하는 값으로 기준 원소가 전체에서 몇 번째 작은 원소인지 알 수 있음. - 기준원소가 전체에서 k번째 작은 원소란 사실을 알면, i와 k의 값을 비교해서 작으면 왼쪽 그룹에 있는 원소 중 하나이고, 같으면 기준 원소가 바로 i번째 작은 수이고, 크면 i 번째 작은 수는 오른쪽 그룹에 있는 원소 중 하나..

1. 기본적인 정렬 알고리즘 선택 정렬 - 선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나. - 배열 A[1~n]에서 가장 큰 원소를 찾아 이 원소와 배열의 끝자리에 있는 A[n]과 자리를 바꿈. - 맨 뒷자리로 옮긴 가장 큰 원소는 제외하고 나머지 원소들로 같은 작업을 반복함. selectionSort(A[],n) { ① for last

1. 점화식 - 점화식은 어떤 함수를 자신과 똑같은 함수를 이용해 나타내는 것. - 동일한 함수가 등호나 부등호의 양쪽에 나타나는데, 양쪽 함수는 변수의 크기가 다를 뿐임. - n!의 점화식은 f(n)=n * f(n-1) - 피보나치 수열의 점화식은 f(n) = f(n-1) + f(n-2) - 점화식은 재귀 함수의 복잡도를 구하는 데 유용함. 자기 호출을 사용하는 알고리즘은 매우 흔함. - 명시적으로 자기호출을 사용하지 않더라도 그 속에서 자신과 똑같지만 크기가 다른 문제를 발견할 수 있는 경우도 있음. - 재귀적 관계를 이용해 알고리즘의 수행 시간을 점화식으로 표현할 수 있음. mergeSort(A[], p, r) // A[p ~ r]을 정렬함 { ① if ( p < r ) then { ② q

1. 몇 가지 기초 사항들 알고리즘 분석의 필요성 - 어떤 알고리즘을 설계하고 나면 이 알고리즘이 자원(보통 소요시간)을 얼마나 소모하는지 분석해야 할 때가 많음. - 시간의 분석은 최악의 경우와 평균적인 경우에 대한 분석이 대표적임. - 시간 분석을 하면 알고리즘이 어느 정도의 입력에서 어느 정도의 시간이 걸리는지 미리 짐작할 수 있음. 알고리즘의 수행 시간 - 알고리즘의 수행 시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지로 표현함. - 입력의 크기 예 ) 정렬의 경우 - 정렬하고자 하는 개체의 수 도시 간 최단 거리 구하는 경우 - 도시의 총수와 도시 간 간선(도로)의 총수 계승을 구하는 경우 - 계승치를 구하고자 하는 자연수의 크기 입력의 크기가 n인 경우에 간단한 연산으로 계산할 수 있..

1. 알고리즘은 문제 해결 과정을 묘사하는 것 - 알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것. - 알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 함. - 설계하려는 알고리즘이 "무엇을" 하는지는 입력과 출력으로 명시할 수 있음. ex) 학생 100명의 시험 점수를 입력으로 받아 최고점을 출력하는 작업을 함. 입력 : 학생 100명의 시험 점수 ( x[0],x[1], ~ x[98],x[99]의 값 ) 출력 : 입력된 100개의 점수 중 최댓값 ( x[0],x[1], ~ x[98],x[99]의 값 중 최댓값 ) 알고리즘의 대략적인 형태 maxScore(x[],n) { ①x[0~n]의 값을 차례대로 보면서 최댓값을 계산함; return ..

1. 포인터 - 컴퓨터는 메모리란 저장 공간을 사용하고, 모든 메모리는 주소를 가짐. - 변수나 배열은 메모리의 어떤 위치에 저장됨. - 만약 주소를 알면 거기에 저장된 변수 값을 참조할 수 있음. - 포인터 변수, 또는 포인터는 이러한 메모리의 주소를 저장하기 위한 변수 포인터 선언 - 포인터도 변수이므로 일반 변수와 같이 사용하기 전에 먼저 선언되어야 함. - 항상 어떤 자료형의 변수를 그리킴. 가리키는 자료형을 먼저 쓰고 *를 붙인 다음 변수 이름을 씀. - *는 자료형이나 변수쪽에 모두 붙일 수 있음. int* pi; float *pf; int *a,*b,*c; - 포인터는 사용할 때 반드시 초기화 해야함. - 포인터 p는 마지막 문장과 같이 주소 추출 연산자 &를 사용해 구한 변수 a의 주소를 ..