1. 그래프(Graph)-자료구조의 일종-정점(Node, Vertex)-간선(Edge) : 정점 간의 관계를 나타냄-G=(V,E) 로 나타낸다. 2. 경로(Path)-정점 A에서 정점 B로 가는 경로 3. 사이클(Cycle)-정점 A에서 다시 A로 돌아오는 경로 4. 단순 경로와 단순 사이클(Simple Path and Simple Cycle)-경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클-특혈한 말이 없으면, 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 말한다. 5. 방향 있는 그래프(Directed Graph)-간선에 방향이 있는 그래프 6. 방향 없는 그래프(Undirected Graph)-간선에 방향이 없음-양방향 그래프라고도 함(Bidirection Graph) ..
1. 11652번 - 카드1)map 사용법 : map 변수명-시퀀스 컨테이너 : 순서 있게 자료를 보관하는 컨테이너(vector, list, deque 등)-연관 컨테이너 : key, value 형태로 짝을 이뤄 자료를 보관하는 컨테이너(map, set 등 등) (정답 예제)...#include using namespace std;int main(){int n;cin >> n;map d;while(n--){long long x;cin >> x;d[x]++; // x를 키값으로 하는 원소의 value 참조 : d[x]} int m=0;long long ans=0;for(auto &p : d){if(p.second > m){m=p.second;ans=p.first;}else if(p.second == m &..
1. 10825번 국영수-N명 학생의 국, 영, 수 점수와 이름이 주어짐-정렬 조건1) 국어 점수가 감소하는 순서2) 국어 점수가 같으면, 영어 점수가 증가하는 순서3) 국어, 영어 점수가 같으면 수학 점수가 감소하는 순서4) 모두 같으면 이름이 사전 순으로 증가하는 순서 2. cmp 함수 사용 시(tuple 미사용) bool cmp(const Person& u, const Person& v){if(u.kor > v.kor){ // 국어 점수가 감소하는 순서return true;}else if(u.kor == v.kor){ // 국어 점수가 같으면if(u.eng < v.eng){ // 영어 점수가 증가하는 순서return true;}else if(u.eng == v.eng){ // 영어 점수도 같으면if..
1. Stable Sorting-같은 것이 있는 경우에 정렬하기 전의 순서가 유지되는 정렬 알고리즘-예를 들어, 다음을 숫자가 증가하는 순서로 정렬했을 때 5○, 4○, 3○, 3●, 2○, 1○ =>1○, 2○, 3○, 3●, 4○, 5○ 또는=>1○, 2○, 3●, 3○, 4○, 5○ 위와 같이 3에 대해서 두 가지의 결과가 나올 수 있다.이 때, 첫번째 결과처럼 정렬하기 전의 순서가 유지되는 정렬 알고리즘이 stable 한 정렬이다. 2. 시간복잡도가 N^2인 stable sorting-버블 정렬 3. 시간복잡도가 NlgN 인 stable sorting -병합 정렬(Merge Sort)-STL에는 stable_sort 알고리즘 사용 4. 문제-10814번(나이순 정렬)-10825번(국영수)-1098..
- y가 증가하는 순으로, 같으면 x가 증가하는 순서로 정렬 1. pair 사용, cmp 함수#include #include #include using namespace std; bool cmp(const pair &u, const pair &v) {if (u.second == v.second) return u.first > n;vector v(n);for (int i = 0; i < n; i++) {scanf("%d %d", &v[i].first, &v[i].second);}sort(v.begin(), v.end(), cmp);/*for (int i = 0; i < n; i++..
1. 비교 함수 사용#include #include #include using namespace std; struct Point {int x, y;}; bool cmp(const Point& u, const Point& v) {if (u.x > n;vector a(n);for (int i = 0; i > a[i].x;cin >> a[i].y;}sort(a.begin(), a.end(), cmp);for (int i = 0; i a[i].y;}sort(a.begin(), a...
-pair를 사용하면 편하다. 1. pair 1) 정의이름이 'first', 'second' 인 두 개의 변수를 저장할 수 있는 struct 2) 용도-이차원 배열의 인덱스-이차원 좌표평면에서의 좌표 (V)-정점 번호와 해당 정점 번호까지의 최단거리를 묶어서 저장해야 되는 경우 3) 사용법// pair 선언 및 생성pair p = make_pair(1, 2); //pair의 멤버 변수에 접근int valA = p.first;int valB = p.second; 2. vector1) 정의사이즈가 유동적인 배열 2) 용도-배열을 사용하는 모든 경우 3) 사용법- include 4) 멤버 함수v.size() : 사이즈 리턴v.resize(new_size) : 사이즈 변경v.empty() : 사이즈가 0인지 확..
1. 정렬-많은 정렬 알고리즘이 있다.-선택 정렬, 삽입 정렬, 버블 정렬(stable) : O(N^2)-퀵 정렬, 힙 정렬, 병합 정렬(stable) : O(NlogN)-정렬은 O(NlogN)이 걸리는 정렬을 사용하는 것으로 한다.-정렬을 직접 구현하는 것 보다는 STL에 있는 sort를 사용하는 것이 좋다.-sort(begin, end) =>begin 부터 end 바로 전까지 정렬하는 함수=>[begin, end) 까지 정렬 2. sort 함수 1)배열 정렬int n = 10;int a[10] = {};sort(a,a+n); // a[0] 부터 a[n-1] 까지 정렬 2)vector 정렬vector a;sort(a.begin(), a.end()); 3. 2751번(수 정렬하기 2)1)STL sort#..
1. 소인수분해-정수 N을 소수의 곱으로 분해-소수를 구하지 않고도 해결할 수 있다.-N을 소인수분해 했을 때, 나타날 수 있는 인수 중에서 가장 큰 값은 루트 N-따라서 2부터 루트 N 까지 for문을 돌면서-N을 나눌 수 있으면, 나눌 수 없을 때까지 계속해서 나누면 된다. (코드)for(int i=2;i*i1){printf("%d\n",n);} -11653번(소인수분해) 2. 팩토리얼-N! = 1*2*3*...*N-팩토리얼은 매우 큰 값-10!=3628800-10872번(팩토리얼) 3. 1676번(팩토리얼 0의 개수)-10!이 0이 2개인 이유는 10!을 소인수분해 해보면 알 수 있다.-10!=(2^8)*(3^4)*(5^2)*7여기서 (2*5)^2 = 10^2 이므로 0은 2개-즉, N! 의 0이 ..