조이의 개발 성장 다이어리

배열이란? 동일한 타입의 데이터를 한 번에 여러개 만들 때 사용하는 자료형 배열을 사용하면 연속적인 메모리 공간이 할당되고, 배열 인덱스가 주어지기 때문에 인덱스를 사용하여 쉽게 접근이 가능하다. C언어에서의 1차원 배열 선언 : 자료형 배열이름[배열 요소의 개수] // int list[6], char string[7], Student sList[6]; 값 설정 : 배열이름[인덱스] = 값 // list[0] = 100; 값 반환 : 값을 저장할 변수 = 배열이름[인덱스] //Student s1 = sList[0]; 인덱스는 0부터 시작한다. 메모리 주소는 배열의 첫번째 요소가 기본 주소가 되고, 그 다음 요소부터 기본주소+n*sizeof(자료형)이 된다. ex: int list[6]에서 list[0]의..

#include int max(int list[], int low, int high) { //순환 int middle; int max_left, max_right; if (low == high) return list[low]; //절반으로 나눈 끝에 low=high이면 자기 자신 반환 middle = (low + high) / 2; max_left = max(list, low, middle); //중앙에서 왼쪽 부분의 최대값 max_right = max(list, middle + 1, high); //중앙에서 오른쪽 부분의 최대값 return max_left >= max_right ? max_left : max_right; //조건 연산자 사용하여 왼쪽의 최대값과 오른쪽의 최대값을 비교하여 더 큰것을 반..

순차 탐색? 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 차례대로 하나씩 검사하여 원하는 항목을 찾아가는 방법 #include int seq_search(int key, int low, int high){ int i; for (i=low; i

이진탐색이란? 배열의 중앙에 있는 값을 알아내어 찾고자 하는 항목이 중앙의 왼쪽에 있는지 오른쪽에 있는지를 알아내어 탐색의 범위를 반으로 줄이는 방법 단, 배열이 반드시 정렬이 되어있어야하기 때문에 고정된 데이터에 적합하다. 위의 예시는 34를 찾는 경우이다. 1. 34는 중앙값인 27보다 크므로 오른쪽 부분에서 탐색한다. 2. 다시 오른쪽 부분의 중앙값인 38과 비교한다. 38보다 작으므로 왼쪽 부분에서 탐색한다. 3. 다시 왼쪽 부분의 중앙값인 30과 비교한다. 30보다 크므로 오른쪽 부분에서 탐색한다. 4. 다시 오른쪽 부분의 중앙값인 34과 비교한다. 찾고자 하는 값이 중앙값과 일치한다. 즉, 중앙값과 비교하면서 찾고자하는 항목이 중앙값보다 작으면 왼쪽에서 다시 중앙값과 비교하고, 크면 오른쪽에서..

사이클 길이? 어떤 정수 n이 짝수면 2로 나누고 홀수면 3을 곱한 다음 1을 더한다. 이런 과정을 반복하면서 n=1이 되면 멈춘다. 이 때 1이 나올 때까지 만들어진 수의 개수를 (n과 1 포함) 사이클 길이라고 한다. 입력 : 22 출력 : 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 사이클 길이는 16 위와 은 수열을 출력하고 사이클 길이를 리턴해주는 함수를 순환을 이용하여 작성하시오. int get_cycle_number(int n) { int cycle_length = 1; printf("%d ", n); //수열을 만들면서 숫자 출력 if (n == 1) return count; else if (n % 2 == 0) //n이 짝수이면 cycle_length+=g..

하노이탑 문제 막대 A, B, C가 있고 막대 A에 아래에서부터 크기가 큰 순서대로 원판이 쌓여있다. 막대 A의 원판들을 막대 C에 옮겨야한다. 이 때 지켜야할 3가지 조건이 있다. 한 번에 하나의 원판만 이동할 수 있다. 맨 위에 있는 원판만 이동할 수 있다. 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다. 중간의 막대를 임시적으로 이용할 수 있으나 이 역시 앞의 조건들을 지켜야 한다. 원판이 3개일 경우 A에서 C로 이동하는 과정을 그림으로 그리면 다음과 같다. 원판의 개수가 n개라고 할 경우, 다음과 같이 단순하게 생각할 수 있다. A에 쌓여있는 위에서부터 n-1개의 원판을 B에 이동하고, 제일 밑에 있는 하나의 원판을 C로 옮긴다. 그리고 다음으로 B에 있던 n-1개의 원판을 C로 옮긴다. 이를..

순환(recursion) 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 ex 1) 팩토리얼 int factorial(int n) { if (n

최악의 경우(worst case) ★ 알고리즘의 수행 시간이 가장 오래 걸리는 경우 => 시간 복잡도의 척도 최선의 경우(best case) 알고리즘의 수행 시간이 가장 적게 걸리는 경우 평균적인 경우(average case) 알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균적인 수행 시간 EX) 순차 탐색(sequential search)의 경우 ※ 순차탐색 : 찾고자 하는 항목을 배열의 첫 번째부터 마지막까지 비교하면서 찾아내는 탐색방법 최선의 경우 : 찾고자 하는 숫자가 배열의 맨 처음에 있는 경우 : 비교 횟수가 1번이므로 O(1) 5 9 10 17 21 29 33 37 38 43 최악의 경우 : 찾고자 하는 숫자가 배열의 맨 끝에 있는 경우 : 비교 횟수가 n번이므로 O(n..

효율적인 알고리즘을 짜려면? 알고리즘이 시작하여 결과가 나올 때까지의 수행시간이 짧으면서 컴퓨터의 자원(ex:메모리)을 덜 사용하도록 짜야한다. -> 즉, 알고리즘을 짤때 수행시간과 기억공간을 분석하여 시간 효율성과 공간 효율성을 고려해야함 공간 복잡도(space complexity) 알고리즘이 사용하는 기억 공간 분석 시간 복잡도(time complexity) ★ 알고리즘의 수행 시간 분석 => 알고리즘의 효율성을 이야기할때 주로 시간 복잡도를 고려 절대적인 수행 시간을 나타내는 것이 아닌 알고리즘을 이루는 연산이 몇 번 수행되는지를 숫자로 표시함 시간 복잡도 함수 : 연산의 수행 횟수는 보통 입력의 개수에 따라 달라지기 때문에 n에 대한 함수로 나타냄. 이 함수를 시간복잡도 함수라고 하며 T(n)으로..

프로그램 = 자료구조 + 알고리즘 자료구조(data structure) 프로그램에서 자료를 정리하여 보관하는 구조(배열, 스택, 큐...) 알고리즘(algorithm) 컴퓨터로 문제를 해결하기 위한 단계적인 절차 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 장치가 이해할 수 있는 언어로 기술한 것 특정한 일을 수행하는 명령어들의 집합 알고리즘의 조건 입력 : 0개 이상의 입력이 존재해야 한다 출력 : 1개 이상의 출력이 존재해야 한다 명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다 유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다 유효성 : 각 명령어들은 실행 가능한(프로그래밍 언어로 바꿀수 있는) 연산이어야 한다. 자료형 : 데이터 + 데이터 간에 가능한 연산 추상 자료형..