🏰 🏰

PROGRAMMING/자료구조

• Selection Sort , Merge Sort, 그리고 증명

  PROGRAMMING/자료구조 2020. 6. 18. 16:22

  Sotring 에 대한 증명 방법 -입력: a[0], a[1], ... , a[n-1] : 집합 - Sorting 이 완료된 후 다음이 만족되어야 함 - Sorting 이 끝난 후 배열에 저장된 값들을 b[0], b[1], ..., b[n-1] 이라고 부르자 - 조건 1: a 배열과 b 배열의 값들은 집합으로 같음 - 조건 2 : b[0]

  Read More
• Arrays(배열), Binary Search(이진 탐색), 증명, 그리고 log

  PROGRAMMING/자료구조 2020. 6. 18. 14:26

  Arrays: 연속된 주소, 동일한 Type 장점: 각 원소에 대한 접근이 상수 시간에 가능. Search 가 빠름 단점: 배열의 크기를 변화하려면 비용이 크게 듦. Insert, Delete 가 느릴 수 있다. -> 변화가 없거나 드문 형태의 자료에 사용한다. Binary Search (이진 탐색) 자료의 탐색 알고리즘 중 선형 탐색(한 원소씩 처음부터 순차적으로 방문하여 찾는 방법) 보다 월등히 빠른 알고리즘으로, 자료를 반씩 나누어 탐색하는 알고리즘이다. 즉, 중간값을 보고 그보다 왼쪽에 있을지 오른쪽에 있을지 판단하여 그 해당 구역에서 새롭게 반씩 탐색하는 것이다. 이때, 자료는 (무조건) 정렬되어 있어야 한다. 다음은 각각 반복적 절차와 재귀적 절차로 적성한 이진 탐색 코드이고, 각각에 대해 증..

  Read More
• 수학적 귀납법으로 재귀 알고리즘 증명

  PROGRAMMING/자료구조 2020. 6. 18. 13:28

  수학적 귀납법으로 재귀 알고리즘을 증명하기 위해선 다음의 두 가지만 확인하면 된다. ① P(1) 이 참이다. ② P(x-1) -> P(x) 는 참이다. 즉, P(x-1) 이 참이라고 믿고(가정) P(x) 확인! :: 재귀 코드는 "재귀는 항상 성공한다"고 읽으면 됨 다음의 두 코드를 살펴보자. (c언어로 작성되었습니다.) int sum(int x) { int i, num; num=0; for (int i=0; i P(x) 이 참이다 : sum(x-1) 이 1+2+...+(x-1) 을 리턴하면 sum(x) 는 1+2+...+(x-1)+x 를 리턴한다. => 코드를 보면 sum(x) 는 x + sum(x-1) 의 값을 리턴한다. sum(x-1) 은 1+2+...+(x-1) 과 같다고 가정했으므로 sum(x)..

  Read More
• 수학적 귀납법

  PROGRAMMING/자료구조 2020. 6. 18. 13:06

  수학적 귀납법: 어떤 명제 P(n) 이 있을 때 모든 자연수 n 에 대해 참임을 증명하는 방법 - 기본형: P(1) 이 참(BASE)이고, P(n-1)->P(n) 이 참(STEP)이면 P(n) 은 모든 자연수 n 에 대해서 참이다. - 강한 형태: P(1) 이 참이고, P(1)∧P(2)∧···∧P(n-1) -> P(n) 이 참이면 P(n) 은 모든 자연수 n 에 대해서 참이다. 수학적 귀납법은 더 어려운 얘기를 쉽게 할 수 있다. ❗중요❗ P(n-1)->P(n) ≡ P->Q 의 의미 - P 가 참, Q 가 참 -> 전제는 참 - P 가 참, Q 가 거짓 -> 전제는 거짓 - P 가 거짓, Q 가 참 -> 전제는 참 - P 가 거짓, Q 가 거짓 -> 전제는 참 P 가 거짓이면 Q 는 '의미 없음'. (참..

  Read More
• 변수와 포인터

  PROGRAMMING/자료구조 2020. 6. 18. 12:52

  (이 문서는 c언어를 기준으로 작성되었습니다.) 변수: 이름 , 주소 , type(크기, 해석) - 이름은 사람을 위한 것, 주소는 CPU/MEMORY 를 위한 것. 변수를 동적할당하게 되면, MEMORY 에 해당 변수의 '크기'만큼 공간이 생긴다. 그리고 그 변수의 주소로 그 변수를 다룰 수밖에 없는데, 그 주소를 저장할 수 있는 변수가 포인터 Pointer : 변수의 일종. 변수의 특징 중, type 가 주소인 변수. - 어떤 type 의 주소를 가지고 있는지도 추가로 표시해야 함 - 표기: int * p; - * 은 "p에 있는 값을 꺼내서 주소로 생각해서 그 주소로 간다" 즉, p에서 주소를 꺼내 목적지에 가면 int 가 있는 것으로 항상 생각 - p= &a : 변수 a 의 주소를 꺼내 p 에 저..

  Read More