728x90

전체 글 360

C++ sort 함수 제대로 사용하기(배열, 벡터)

* C++ sort함수란? : C++STL에서 제공하는 sort 알고리즘 - 헤더파일: - 구문: sort(start, end); //start부터 end개를 오름차순(default)로 정렬한다. - 내부는 Quick sort(퀵 정렬)로 구현되어 있다. 따라서 평균 시간 복잡도는 O(NlogN)을 가진다. 1) 함수 원형 template void sort(T start, T end); template void sort(T start, T end, Compare comp); : 3번째 인자 값(Compare comp)을 넣으면 오름차순, 내림차순 등으로 정렬할 수 있다. compare 함수는 true 인 경우를 기준으로 정렬한다. 2) 배열(array) 사용할 때 예시 sort(arr, arr+n); /..

C++ 동적할당?

* 배열의 길이를 고정한다는 것과 동적할당한다는 것의 차이점은? - 고정배열(fixed array): 컴파일 타임에 배열의 길이를 정하는 것. - 동적배열(dynamically array): 런타임 동안에 배열의 길이를 정하는 것. * 동적할당을 위해 필요한 연산자: new[], delete[] * 배열의 길이를 동적으로 할당하고 값을 초기화시켜보자. #include int main(){ int length; cin >> length; int *array = new int[length]; //이렇게 하면 배열의 길이를 입력받은 length로 할당 가능 for(int i = 0; i> array[i]; } delete[] array;// 동적할당 시, 배열 할당한 메모리 꼭 해제해주기. return 0; ..

[Baekjoon][C++] 14500번 테트로미노 문제설명 및 코드

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net ▷ 문제설명 NxM 크기의 종이 위에 테트로미노를 하나 놓아서 놓인 칸에 쓰여 있는 수의 합을 최대로 하는 문제 N, M의 범위는 4 > N >> M; for (int i = 0; i > arr[i][j]; } } StartCalculation(arr, N, M); } void StartCalculation(int arr[SIZE][SIZE], int N, int M) { int ..

[Baekjoon][C++] 1476번 날짜계산 문제설명 및 코드

1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net ▷ 문제설명 준규가 사는 나라는 연도를 표현할 때 E, S, M 세 문자로 표현한다. 각각의 문자가 가지는 범위는 1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19 이다. E, S, M이 주어질 때, E S M으로 표시되는 가장 빠른 연도를 출력하자. ▷ 문제풀이 이 문제의 경우 표현할 수 있는 년도는 15 * 28 * 19 = 7980년까지 이므로 브루트포스 방법으로 1년 부터 7980년까지 구하다가 정답과 같아지는 순간을 찾으면 된다. 이 때, 문제에..

[Baekjoon][C++] 2309번 일곱난쟁이 문제설명 및 코드

2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net ▷ 문제설명 찐 일곱난쟁이를 찾는 문제! 즉, 가짜 난쟁이 2명이 포함된 9명의 난쟁이 중에서 찐 일곱난쟁이를 찾아야 한다. 그리고 일곱난쟁이의 키를 오름차순으로 출력해야 한다. ▷ 문제풀이 1) 일곱 난쟁이의 키의 합이 100인 것과 순열의 성질을 이용한다. 2) 9명 중, 7명을 선택하는 방법이 아닌 2명의 난쟁이를 선택하는 경우를 구한다.(9C7 = 9C2) 3) 전체 키의 합에서 2명 키를 빼본다. 4) 그 값이 100이 된다면 그 둘이 가짜 난쟁이들이다. ▷ 시..

[Algorithm] 브루트 포스(Brute Force)

▷ 부루트 포스 알고리즘이란? : 아묻따 모든 경우의 수를 다 계산해보는 것. : 숫자가 커질 수록 계산 시간이 기하급수적으로 증가함. ▷ 예시 4자리 비밀번호를 풀어야 할 때의 0000~9999의 경우의 수인 10,000가지를 다 계산해보는 것을 말한다. ▷ 관련된 백준 알고리즘 문제 : 2309번 일곱 난쟁이, 1476번 날짜 계산, 14500번 테트로미노 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는..

[Math&Algorithm] 소수?

▷소수란? : 약수가 1과 자기 자신 밖에 없는 수 : 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지지 않는 자연수 소수의 예) 2, 3, 5, 7, 11, 13, 17, 19, 23, ... ▷소수를 구하는 방법? ① 자연수 N의 가장 큰 약수는 N/2보다 작거나 같으므로 2부터 N/2까지 나눠보기. ② 자연수 N을 루트 N까지 나눠보기. Why? N이 소수가 아니라면 N=a X b 로 표현할 수 있다. (a와 b는 자연수) (이 때, a와 b는 a b 라면 두 수를 바꿔서 항상 a

[Math&Algorithm] 최대공약수? 최대공배수?

▷최대공약수란? : GCD(Greatest Common Divisor) : 두 수 A와 B의 공통된 약수 중에서 가장 큰 정수 ▷구하는 방법? ① 2부터 min(A, B)까지 모든 정수로 나눠서 나머지가 0이 되는 최대 정수 찾기. ② 유클리드 호제법(Euclidean algorithm)으로 찾기. : a를 b로 나눈 나머지를 r 이라고 했을 때, GCD(a, b) = GCD(b, r) 이 성립한다. → 재귀로 구현 가능 : r이 0이면 그 때의 b가 최대 공약수 이다. ex) GCD(16, 12) = GCD(12, 4) = GCD(4, 0) = 4 → GCD(a, b) = GCD(b, a%b) 로 표현 됨 ▷최대공배수란? : LCM(Least Common Multiple) : 두 수의 공통된 배수 중에..

728x90