본문 바로가기

전체 글

알고리즘/기본 문법 2022. 4. 21. <알고리즘> 모듈러 연산 * 모듈러 연산의 속성 0. a ≡ b mod n과 b ≡ c mod n 은 a ≡ c mod n 을 의미 1. [(a mod n)+(b mod n)] mod n = (a+b) mod n 2. [(a mod n)-(b mod n)] mod n = (a-b) mod n 3. [(a mod n)*(b mod n)] mod n = (a*b) mod n 예시 문제) 11 mod 8 = 3; 15 mod 8 = 7 (11 + 15) mod 8 = 26 mod 8 = 2 ((11 mod 8 ) + (15 mod 8)) mod 8 = 10 mod 8 = 2 (11 - 15) mod 8 = -4 mod 8 = 4 ((11 mod 8 ) - (15 mod 8)) mod 8 = -4 mod 8 = 4 (11 x 15) m..
알고리즘/기본 문법 2022. 4. 21. <알고리즘> 최대공약수/최소공배수 코드 #include #include #include #include using namespace std; // 최대 공약수 int gcd(int a, int b) { if(a == 0) return b; return gcd(b % a, a); } // 최소 공배수 int lcm(int a, int b) { return a * b / gcd(a, b); } int main() { cout
<알고리즘> 조합(Combination)
알고리즘/기본 문법 2022. 4. 21. <알고리즘> 조합(Combination) 조합에서 “순서”는 없음, 그저 몇명을 뽑아서 갈 것인가를 쓸 때 조합을 씁니다. 예를 들어 지원자가 1000명 중에 4명의 개발자를 뽑아 회사의 신입개발자로 채용한다고 하면 순서 상관없고 다양하게 뽑으면 됨 1. 재귀 함수 활용 코드 #include #include #include #include using namespace std; // 전체개수 int n = 5; // 몇개를 뽑을 건지 int k = 3; int a[5] = { 1, 2, 3, 4, 5 }; vector b; void print(vector b) { for (int i = 0; i < b.size(); i++) cout
<알고리즘> 순열(permutation)
알고리즘/기본 문법 2022. 4. 21. <알고리즘> 순열(permutation) 순열(permutation)이란 순서가 정해진 임의의 집합을 다른 순서로 섞는 연산을 말함 예를 들어 1, 2, 3이렇게 있을 때 1, 3, 2 이런식으로 다른 순서로 섞는 연산을 순열이라고 합니다. 그리고 n 개의 집합 중 n 개를 고르는 순열의 개수는 n!이라는 특징을 가지고 있으며 보통 중복을 허용하지 않는 기본조건이 있음 예를 들어 3개의 자연수(1, 2, 3)를 이용해 만들 수 있는 3자리 자연수는 몇개 일까요? 123, 132, 213, 231, 312, 321 이렇게 6개 입니다. 그렇다면 3개의 자연수(1, 2, 3)를 이용해 만들 수 있는 1자리 자연수는 몇개일까요? 3개입니다. 전자는 3개중 3개를 뽑는 것이라 3!이 되고 후자는 3개중 1개를 뽑는 것이라 3이 됩니다. 3개중 3개를 ..
<자료구조> 우선순위 큐
CS/자료구조 2022. 4. 20. <자료구조> 우선순위 큐 우선순위 큐(Priority Queue) : 내부구조는 heap으로 구현되어있으며 주로 다익스트라, 그리디 등에 쓰입니다. 다음 코드 처럼 greater 를 써서 오름차순, less를 써서 내림차순으로 바꿀 수 있습니다. 정렬하는 것은 이 최소힙, 최대힙을 머리속으로 생각하면 될 것 같다. 방식 priority_queue * 우선순위 큐에서는 커스텀정렬 넣을때 반대로 넣는게 특징이다. 활용 코드 1 #include using namespace std; // priority_queue priority_queue pq; // 오름차순 // priority_queue pq; // 내림차순 int main() { pq.push(5); pq.push(4); pq.push(3); pq.push(2); pq.push..
알고리즘/기본 문법 2022. 4. 19. <알고리즘> 구조체를 이용한 커스텀 정렬 C++에서 커스텀한 구조체를 형성하기 위해 class와 struct를 씁니다. 하지만 struct만 알아도 충분함 구조체(struct) 는 다음과 같습니다. // 1) 커스텀한 정렬이 필요할 경우 struct Point{ int y, x; Point(int y, int x) : y(y), x(x){} Point(){y = -1; x = -1; } bool operator < (const Point & a) const{ if(x == a.x) return y < a.y; return x < a.x; } }; // 2) 정렬이 필요하지 않을 경우 struct percent{ int x, y; double w, d, l; } a[6]; //간단한 struct 커스텀한 무언가를 진행하고 싶다면 구조체를 통해서 ..
<자료구조> queue와 deque
CS/자료구조 2022. 4. 19. <자료구조> queue와 deque queue : 선입선출구조(FIFO), 주로 BFS에 쓰임 queue 활용 코드 #include using namespace std; int main() { queue q; q.push(1); cout
<자료구조> stack
CS/자료구조 2022. 4. 19. <자료구조> stack stack : LIFO구조, 가장 마지막으로 들어간 데이터가 가장 첫번째로 나오는 구조를 지녔습니다. 문자열 폭발, 아름다운 괄호만들기 짝을 찾기 등 문제에 쓰입니다. “교차하지 않고” 라는 문장이 나오면 스택을 사용할지 말지를 의심해봐야 합니다. stack을 활용한 코드 #include using namespace std; stack stk; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); stk.push("엄"); stk.push("준"); stk.push("식"); stk.push("화"); stk.push("이"); stk.push("팅"); while(stk.size()) { cout

티스토리툴바