반응형

학부 내용 정리/[ 2-1 ] 자료구조 15

[ 자료구조 ] 배열 (Selection Sort, Recursive Selection Sort)

Selection Sort의 알고리즘 로직은 다음과 같다. 배열이 있으면, 전체에서 제일 작은 값을 앞으로 옮긴다. 그 다음 나머지 부분에서 제일 작은 값을 앞으로 옮긴다. 그렇게 반복해서 결과적으로 정렬된 배열을 만들어 내는 것이다. int sort (int a[], int n) // n 은 배열의 크기 { //m 최소값 인덱스, t 는 교환할때 활용 int i, j, m, t; for (i = 0; i a[j] ) m = j; t= a[i]; a[i] = a[m]; a[m]=t; // 두 값의 교환 } return; } 먼저 코드를 보자면 첫번째 루프에서 0부터 n 까지 돌아가는데 거기서 최소값을 찾아서 m에 저장한다. 그리고 그 안에서 한번 더 루프가 돌아가는데 j 는 i 부터 n 까지 가장 작은 ..

[ 자료구조 ] 배열 ( Binary Search, Recursive Binary Search)

Array ( 배열 ) 정의 : 연속된 주소, 동일한 Type 장점 : n개 중 k번째 access(Read&Write)가 상수 시간에 가능, Search(어떤 x가 배열안에 있느냐?)가 빠름 단점 : 크기 변화 비용이 크다. Insert, Delete가 느릴수 있다. 사용 : 변화가 없거나 드문 자료 배열에서 가장 흔히 쓰이는 search 방법은 linear search 이다. 이는 하나하나 다 읽어보며 찾는 방법이고 모두 다 읽어봐야해서 크게 효율적이지 않다. 또 다른 방법은 Binary Search 이다. 이 방법은 sorting 되어있는 상태에서만 사용가능하다. 기본적인 로직은 절반을 확인하고 그의 절반..절반.. 을 확인하는 방법이다. 코드로 나타내면 int search(int a[], int ..

[ 자료구조 ] 기본사항: 수학적 귀납법, 시간복잡도

수학적 귀납법 ( 명제 : P(n)이 있을때 ) 기본형 : p(1)이 참이고, p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 강한 형태 : p(1)이 참이고, p(1)^p(2) ^ ....^p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 수학적 귀납법은 크게 Base 와 Step 부분으로 나뉜다. base: p(1) 이 참이다. step : p(n-1) -> p(n) 가 참이라고 보이면, p (n) 은 모든 자연수 n에 대해 참이라고 증명이 가능하다. base 와 step은 서로 독립적이고, 보통 base는 참인것을 금방 알수 있으며, 포인트가 되는 것은 step 부분이 참인 것을 알아내는 것이다. 그런데 step 에서 p(n-1) -..

[ 자료구조 ] 기본사항 : 변수와 포인터변수

변수는 정보를 담아주는 박스같은 존재이다. 변수는 이름, 주소, type으로 구성되어있다. 이름: 사람들을 위한 속성, 변수들을 구별할 수 있도록한다 주소: CPU 와 메모리를 위한 속성, 변수들을 구별할 수 있도록 한다. Type: 몇바이트의 크기를 갖고 어떤 bit들를 어떤 의미로 읽을 것인가를 결정 (문자형, 정수형) 변수를 선언 할 때 Type 이름 = 변수값 ex) int a =8 이런식으로 선언한다. 이렇게되면 우리는 이름과 타입은 알 수 있지만 주소는 알 수 없다. 우리는 다음과 같은 이유로 주소를 알아야한다. - 모든 변수를 다 만들어 둘 수가 없음 - 메모리를 얼마나 쓸지 미리 알 수 없음 -> 메모리 할당 필요 Type이 주소인 변수를 우리는 포인터 변수라고 한다. 포인터 변수는 int..

[ 자료구조 ] 기본사항 : 메모리와 컴퓨터 동작방식

자료구조를 공부하기 전에 컴퓨터의 기본적인 구조와 컴퓨터가 어떤 방법으로 실행되는지부터 보겠다. 메모리 안에는 무수한 바아트, 비트들이 있다. - 비트 : 0과 1을 표시할 수 있는 전자회로적인 도구 - 바이트 : 8개의 비트 이러한 메모리는 어떤 방식으로 저장하고 동작할까? 이를 알아보기 위해 간단한 코드와 이가 동작하는 방법을 설명해보겠다. int main() { int a,b,c; c= a+b; } //a:300 b:600 C:900 주소에 저장된다고 가정 int a,b,c 가 실행 되면 a,b,c는 memory 어딘가에 저장이 될 것이다. 메모리에는 0번부터 차례대로 번호가 매겨져 있으며 int a,b,c는 빈 자리에 가서 각 4바이트의 연속된 데이터를 차지하고 있을 것이다. 다음으로 c=a+b ..

반응형