CS/Algorithm8

• QUICK SORT 정리..[C] 퀵정렬 분할정복법(divide ans conquer) 사용한다. O(NlogN) 시간 복잡도를 가진다. 오름차순 기준) 개념: 피봇값을 기준으로 더 작은 수를 왼쪽으로, 더 큰 수를 오른쪽으로 옮긴다. 왼쪽부터 하나씩 확인하며 피봇보다 큰 값을 찾고, 오른쪽부터 하나씩 확인하며 피봇보다 작은 값을 찾아, 이 둘의 위치를 바꾼다. 그러다 엇갈리게 되면, 피봇값과 엇갈린 앞에 값 위치를 바꾼다. 코드로 이해하는 게 제일 나을 듯 하다. 소스코드를 깔끔하게 하려면 재귀함수로 구현 #include void quickSort(int *data, int start, int end) { printf("called! start: %d, end: %d\n", start, end); for(int i=start;i= en.. CS/Algorithm 2022. 7. 27.

• [boj 10989] 카운팅 정렬 이 정렬법은 O(n+k)의 시간 복잡도를 가진다. 이때 k는 정렬하고자 하는 수 배열의 최대값이다. n개의 배열을 한 번 훑으며 개수를 체크해야 하므로O(n)인데 최대값 k에 따라서 메모리가 증가한다. 알고리즘 count배열을 선언한다. 이때 배열의 크기는 정렬하고자 하는 수의 최대값으로 정한다. #include #include int main() { int n; scanf("%d", &n); int input; int count[10000]; // 초기화 해야함 memset(count, 0, 10000*sizeof(int)); // 입력을 어레이로 받지 않고 단일 int로 받는것에 주의 for(int i=0;i CS/Algorithm 2022. 7. 20.

• [백준 10815] 이분 탐색법(binary search) 숫자 카드: 백준 10815번 문제 n개의 카드를 받았을 때, m개의 숫자카드 중 가지고있는 카드가 무엇무엇인지를 판단하는 문제 문제 이해 및 풀이 arr1에 n개의 숫자를 받고, std::sort 알고리즘으로 미리 정렬해놓는다. sort 알고리즘은 헤더파일에 있고 퀵소트로 정렬하여 O(nlogn)의 시간복잡도를 가진다. sort(start, end, compare)으로 첫번째인자는 시작주소, 두번째인자는 끝주소, 마지막인자는 비교함수를 옵션으로 넣어줄 수 있다. 기본값은 오름차순 정렬이다. 다시 돌아와서, m개의 숫자를 받아 각 숫자가 n개의 카드에 존재하는지 여부를 출력해주기 위해 바이너리서치 함수로 전달한다. 함수로 배열을 전달할 때 길이정보가 같이 넘어가지는 않으므로, 꼭 인자로 따로 넘겨주어야 .. CS/Algorithm 2022. 6. 24.

• 

  [백준 2609] 최대공약수와 최소공배수 최대공약수와 최소공배수 구하기 일반적으로 교과과정에서 배운 최대공약수 구하는 법은 두 수를 2나 3, 나뉠만한 소수로 계속 나눠보는 것이다. 위와 같이 더이상 나눠지지 않는 수까지 나눈 후에, 즉 A와 B를 서로소가 될 때까지 나눈 후에 왼쪽 나눈 수들을 전부 곱한 값이 gcd, 최대공약수이고 A, B를 gcd로 나눈 몫들을 모두 gcd와 곱한 값을 lcm, 최소공배수라 한다. 최대공약수 gcd = greatest common divisor 최소공배수 lcm = least common multiple 이는 사실 A와 B를 소인수분해한 후, 공통약수를 모두 골라내는 작업과 같다. 하지만 이 계산법들은 A와 B가 커질수록 소인수분해하기 어려워진다. 유클리드 호제법: Euclidean algorithm 원이름.. CS/Algorithm 2022. 6. 21.

• [백준 20353] C언어 기본 자료형 정리 C언어 자료형 정리 백준 20353 Atrium 문제 날먹할 외국어 문제 찾아보다가, 의외로 브론즈 4랭크인 20353번 Atrium 문제에서 10번이나 "틀렸습니다"를 받아 포스팅한다. (15610번과 같은 문제) 이번 기회에 자료형을 확실히 정리하고 넘어가야겠다.. 분명 입력값이 single integer a(1 CS/Algorithm 2022. 6. 16.

• [백준 11729] 하노이 탑 옮기기(재귀) 문제해석 / 풀이 / 코드 하노이 탑 문제 시작 기둥, 보조 기둥, 목적 기둥 3개로 나눠 놓았을 때, 시작 기둥에 있는 n개의 원판을 목적 기둥으로 옮기는 게임이다. 조건 한번에 하나만 옮기고 큰 원판이 작은 원판 위에 있으면 안된다. 관찰 결국에는 가장 큰 n번째 원판이 목적기둥으로 이동해야 하고, 그 중간 과정에서, n-1개의 원판은 보조기둥에 위치한다. 즉 정리하면, n개의 원판을 시작->목적으로 옮기는 작업은 아래 세 과정으로 요약된다. n-1개의 원판을 시작->보조로 옮기기, 원판n을 시작->목적 옮기기, n-1개의 원판을 보조->목적으로 옮기기 수식으로 이해 f(n)을 n개의 탑을 옮기는 데 필요한 이동횟수라 하자. 위 관찰 과정에서 확인한대로 식을 정리하면, f(n) = 2*f(n-1) + 1이 된다. n-1개의 원.. CS/Algorithm 2022. 6. 15.

• [백준 4948] 베르트랑 공준(소수 구하기) 이해하기 / 코드 소수 구하기 소수의 정의 자연수 n에 대하여 소수는 1과 자기자신만을 약수로 갖는다. 또한 1은 소수가 아니다. 1. 기본 방법 소수는 2 이상, n-1 이하의 수로 나누어떨어지므로 2부터 n-1까지 나눠서 0이 나오면 소수로 판별할 수 있다. 예를 들면 아래와 같이 구할 수 있다. #include int main() { int n; scanf("%d", &n); // n은 소수입니까? if(n==1) { printf("소수가 아님"); return 0; } for(int i=2;i CS/Algorithm 2022. 6. 13.

• [백준 2447] 별찍기(재귀) 문제이해 / 풀이 / 코드 접근방법 기본적으로 입력 N 사이즈만큼 문양이 찍힌다는것을 알아야한다. 즉 N==27이면 가로27, 세로27 사이즈의 문양이 찍힌다. N회 반복의 for문을 두 번 중첩하고, 개행문자를 찍어줘야 하는것이 문제의 출발점이다. 별 찍는 함수에는 좌표와 입력값 N을 같이 넘긴다. 함수에서는 divide-and-conquer 방법을 사용하여 별을 찍을지, 말지를 결정한다. n==1일 때까지 재귀호출을 하며 %3 연산을 취했을 때 i와 j가 1이 되는 경우에만 공백을 찍고, 이 조건에 걸리지 않았을 경우인데 n==1일 경우에는 별을 찍고 끝낸다. 소스코드 #include void recur(int i, int j, int n) { if((i/n)%3==1 && (j/n)%3==1) // 이 조건에 해당하는 부분을.. CS/Algorithm 2022. 6. 13.