분류 전체보기 검색 결과

해당 글 904건
c언어 do while문 : 반복문 루프를 최소한 1번 이상 수행한다.

이번 시간에는 제가 모 사이트에서 4200문제를 풀면서 매우 뜸하게 썼던 반복문인 c언어 do while문을 알아보도록 하겠습니다. 구현 문제에서 가끔 썼던 것 말고는 for나 while보다는 매우 많이 빈도가 적었습니다. 저 둘은 아마 제가 그 사이트에서 낸 코드들을 보면, 각각 10만 ~ 13만회 정도, 혹은 그 이상도 썼을 듯 싶은데, 오늘 배울 반복문은 많아봤자 90회 정도 썼을 거에요. 그 정도로 빈도가 매우 적습니다. 90회 vs 10만회. 비교가 안 될 정도의 빈도입니다. do{block}while(cond1); 문법은 대략 이러합니다. do를 먼저 써 주고 반복문 블록이 온 다음에, while이 옵니다. 그 안에 cond1, 즉, 조건이 들어갑니다. 예를 들어서 T>0이냐? 등등이 말입니다..
코딩/C 2019. 8. 22. 12:03
자료구조 덱 (deque) : 앞과 뒤에서 추가되고 삭제된다.

자료구조의 덱, 그러니까 deque는 queue하고 비슷합니다. front와 back, 이렇게 2개의 포인터 있습니다. 그런데, 큐가 front에서 삭제가 일어나고, back에서 삽입 연산이 일어나는데 비해서, 덱은 front에서도 삽입과 삭제가, back에서도 삽입과 삭제가 일어납니다. 이 연산만 구현하려면, 사실 List로 구현하는 게 제일 간단해 보입니다. 먼저 다음과 같이 초기화를 시켜 봅시다. 그러면 이 때가 비어있는 상태일 겁니다. head->next가 tail이고, tail->prev가 head일 때, empty 상태라고 판단할 수 있습니다. 저는 이 두 개의 더미를 인위적으로 잇기만 하였습니다. 여기에서 push_front 연산을 수행해 봅시다. 이것은 맨 앞에 원소를 추가하는 것입니다. ..
자료알고/자료구조 2019. 8. 22. 01:05
왜 유클리드 알고리즘 함수는 최악의 경우 O(log)일까?

질문이 왔습니다. 왜 확장 유클리드는 최악의 경우에, 대략 log(min(a,b))개의 gcd 함수를 호출하나요? 생각보다 빨리 끝나는 것 같은데. 이 질문에 대한 답을 하기 위해서는 재귀 함수의 기저 조건에서부터 위로 쭉 올라가 보아야 합니다. 그러면 기저 조건을 먼저 볼 건데요. gcd(2,1)의 값은 1입니다. 2는 1로 나누어 떨어지기 때문입니다. 이 때, gcd는 재귀적으로 1번 호출합니다. 유클리드 알고리즘은, a = bQ+r꼴로 표현이 될 때 (단 0b이면서 3으로 나눴을 때 나머지가 2인 가장 작은 자연수는 얼마인가요? 5입니다. 우리는 b 다음에 a 이렇게 커지는 수열을 생각할 때, a를 최대한 작은 친구를 선택하는 겁니다. 최대한 천천히 증가하게끔. 그러면 gcd(5,3)을 호출하였을 ..
자료알고/알고리즘 2019. 8. 21. 15:50
mysql from : 어느 릴레이션에서 정보를 찾아올까?

mysql에서는, 정보를 조회할 때 select from where 절은 상당히 많이 씁니다. 오늘은 그 중 첫 번째, from 절에 대해 알아봅시다. 보통 이 뒤에는 릴레이션, 즉 db 안에 있는 테이블 명이 오는데요. 이 뒤에 테이블 이름이 여러개가 들어와 있으면 어떻게 동작할까요? 그 전에, 카티션 곱을 아실 필요가 있습니다. 집합 A가 있고 집합 B가 있다고 해 봅시다. 이 때, A와 B의 카티션 곱 C는 아래와 같이 정의됩니다. C = {(a,b)|a는 A에 속하고, b는 B에 속한 원소} 즉, n(A) = 3이고, n(B) = 3이라면 n(C) = 9라는 것입니다. from 절에 테이블 2개가, 즉 t1과 t2가 오면 결과 값은 t1과 t2의 카티션 곱으로 나옵니다. 정말 그런지 확인을 해 볼..
코딩/Sql 2019. 8. 20. 23:03
퀵 정렬 평균 시간 복잡도 : 왜 O(nlogn)일까?

평균적으로 퀵 정렬은 머지보다, 빠른 것으로 알려져 있습니다. 물론 최악의 경우에, skew만 계속 일어나면, 별로 좋지는 않겠지만요. 이건 왜 그럴까요? 머지에 비해서 Quick은 추가적인 공간을 쓰지 않기 때문에 그렇습니다. 사실, 이게 제일 큰 요인입니다. 이것이 어떻게 동작하는지 이해가 가지 않으시다면, 관련 글을 보고 오시는 것도 좋겠습니다. [관련글] 퀵 정렬에 대해서 알아봅시다. 그러면 평균 복잡도는 왜 O(nlogn)일까요? 몇 가지 가정을 해 봅시다. partition이 일어날 때, arr[0]을 pivot으로 잡습니다. 이 때, 정렬을 할 데이터의 갯수가 n개라고 하면, arr[i]보다 작은 것의 갯수가 0개, 1개, 2개, ... , n-1개인 경우가 있을 거에요. 그러한 확률이 모두..
자료알고/알고리즘 2019. 8. 20. 16:18