도담이 먹여 살려야하는 집사

정렬된 여러 개의 데이터 열들을 정렬된 하나의 데이터 열로 만드는 알고리즘 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식 재귀적으로 함수를 호출함. 일반적인 방법으로 구현할 경우 이 정렬은 안정 정렬에 속함. 분할 정복 알고리즘 분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 분할 정복 방법은 대개 순환 호출을 이용하여 구현 병합 정렬은 데이터 열의 병합(Merge)작업을 이용한 정렬 알고리즘 분할(Divide) 데이터 열을 2개로 나누는 단계 정복(Conquer) 부분 배열 정렬 , 부분배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법 ..

함수는 특정한 시점에 필요한 계산 값을 또 다른 자기 자신을 사용해서 구할 수 있음. 재귀호출(recursive call)은 함수 f(x)가 값을 구하기 위해 자기 자신 f(x)을 호출하는 표현이 포함된 상황. 함수가 본인 스스로를 호출해서 사용할 수 있음. 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적. 무한루프에 빠진 경우 함수 호출을 메모리의 스택을 사용함. 계속 자기 함수를 호출하다가 스택이 넘치게 됨. >> stack overflow에러 발생 단순하게 자기 자신을 다시 호출하게 되면 무한루프에 빠질 수 있음. 다음 경우와같이 변화를 주어 무한루프에 빠지지않도록 해야함. 자기 자신f(x)를 다시 호출하는 경우 단순하게 결과값만 반환하는 경우 함수의 반복 횟수를 계산하기 위해 매..

Bubble Sort 서로 인접한 2개의 원소를 비교하여 정렬하는 알고리즘 2개의 원소의 크기를 비교했을때 (오름차순)올바르지 않으면 두 원소를 교환 1번 원소와 2번 원소를 비교, 2번 원소와 3번 원소를 비교, .... (마지막 원소 - 1) 과 마지막 원소를 비교하면서 자료들을 정렬. step 1 - step 6까지 1회전 정렬하고 나면 가장 큰 수의 원소가 맨 뒤로 이동. 2회전 정렬때는 가장 큰 원소를 제외. n개의 원소에 대해서 버블 정렬을 한번 수행할 때마다 n번째의 원소가 제 자리를 찾게되고, 그 다음 정렬에서는 n-1개의 원소를 정렬해 주면 됨. 🔽 Bubble Sort 의사코드 Repeat n–1 times For i from 0 to n–2 If i'th and i+1'th eleme..

순차 탐색 즉, 자료구조를 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 순차적으로 검색한다. 이런식으로 자료들을 검색할 경우, 원하는 원소가 마지막 인덱스에 저장 되어있다면 처음부터 끝까지 검색을 해야하기 때문에 정확하지만 비효율적인 알고리즘이다. 하지만 자료가 정렬되어있지 않거나 그 어떤 정보도 없이 하나씩 찾아야 하는 경우에는 유용하다. ⁉️시간이 오래 걸리고 공간을 더 많이 차지 하는데 왜 정렬을 해줘야 할까? 여러번 리스트를 검색해야 하거나 매운 큰 리스트를 검색해야 할 경우 시간을 단축시킬 수 있다. #include #include int main(void) { // numbers 배열 정의 및 값 입력 int numbers[] = {4, 8, 15, 16, 23, 42}; // 값 5..

Big O 표기법 (실행 시간의 상한) O : on the order of의 약자로 ~만큼의 정도로 커지는 실행 시간을 나타내기 위해 많이 사용됨 $O(n^2)$ $O(n logn)$ $O(n)$ Linear search (선형검색) n만큼 커지는 것 n이 늘어날수록 선형적으로 증가하게 됨. $O(log n)$ Binary search ( 이진 검색 ) $O(1)$ Big Ω 표기법 (실행 시간의 하한) $\Omega(n^2)$ $\Omega(nlogn)$ $\Omega(n)$ $\Omega(logn)$ $\Omega(1)$ >> linear search, binary search 선형검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 $O(n)$이 되지만 운이 좋다면 한 번만에 검색..

부스트코스 컴퓨터과학 CS50 스터디 2기에 참여하고 있다. 비전공자라 전공지식이 많이 약해서 좋은 기회라 신청하게 되었음. 1주차에 컴퓨팅사고 라고 강의를 들었지만 하는것도 없이 뭔가 바빠서 블로그 포스팅 안했음. 그래서 2주차 부터는 이왕하는거 제대로 하기위해서 시작해봄 ㅎㅎ 우선 강의를 모두 듣진 않았지만 이번주는 C언어에 대한 강의가 있음. 나는 첫 프로그래밍 언어로 Java를 배웠는데 조금 비슷한 느낌이 있는거 같았다. 그래서 문제 팀 과제 풀때도 좀 수월하게 풀 수 있었던거 같았음. #include #include #include stdi.h라는 이름의 파일을 찾아서 함수에 접근할 수 있도록 해줌 (java에서 import같은 역할 아닐까 생각해봄.) int main (void) { ...