코딩 기록 저장소

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의 주소를 ..

1. 큐란? - 스택은 나중에 들어온 데이터가 먼저 나가는 구조인데 비해 큐는 먼저 들어온 데이터가 먼저 나가는 자료구조임. - 이러한 특성을 선입선출 (FIFO : First-In First_Out)임. - 큐의 예시 : 놀이공원 매표소에 늘어선 대기열. - 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 말함. - 스택은 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 다른 쪽에서 일어남. - 큐에서 삽입이 일어나는 곳을 후단, 삭제가 일어나는 곳을 전단이라고 함. 큐의 추상 자료형 데이터 : 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모음 연산 : init() : 큐를 초기화함. enqueue(e) : 주어진 요소 e를 큐의 맨 뒤에 추가함. dequeue() :..