Algorithm
정렬 : 주어진 데이터를 정해진 기준에 따라 순서를 재배열하는 작업 가장 기본적인 정렬 알고리즘에 대해 설명하겠다. 1. 버블 정렬(bubble sort) 인접한 두 원소의 크기를 비교하여 교환하는 작업을 반복하여 정렬하는 알고리즘 void bubble_sort(int data[], int n) { for(int i=0;ii;j--){ if(data[j] < data[j-1]) swap(data[j], data[j-1]); } } } 2. 선택 정렬 (selection sort) 정렬 되지 않은 원소 중에서 최소값 원소를 찾아서 맨 왼쪽 원소와 교환 void selection_sort(int data[], int n) { for (int i=0; i
https://www.acmicpc.net/problem/15975 15975번: 화살표 그리기 직선위에 $N$개의 점들이 주어지고 각 점은 $N$개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 $N$까지의 수로 표시 하고, 점들의 좌표는 모두 다르다. 각 점 $p$에 대해서, $p$에서 시작하는 직선 www.acmicpc.net #include #include #include #include using namespace std; bool Compare(pair a,pair b) { if(a.second==b.second){ return a.first < b.first; } else{ return a.second < b.second; } }; int main() { long long n=0; vec..
std::vector 란? C++에서 C 스타일 배열을 대체하는 가변 크기 컨테이너 - 초기화 과정에서 데이터의 크기를 지정하지 않아도 됨 - 배열의 크기를 확장할 수 있음 #include #include using namespace std; int main() { // 벡터 생성 vector v1; // int 값을 저장할 비어 있는 벡터 생성 vector v2(10); // int 값 10개를 저장할 벡터 생성하고 0으로 초기화 vector v3(10, 1); // int 값 10개를 저장할 벡터 생성하고 1로 초기화 vector v4 {10, 20, 30, 40, 50}; // 유니폼 초기화(uniform initialization) vector v5(v4); // v4를 복사하여 v5 생성 vec..
문제 https://www.acmicpc.net/problem/8892 8892번: 팰린드롬 팰린드롬은 어느 방향으로 읽어도 항상 같은 방법으로 읽을 수 있는 단어이다. 예를 들어, civic, radar, rotor, madam은 팰린드롬이다. 상근이는 단어 k개 적혀있는 공책을 발견했다. 공책의 단어는 ICPC www.acmicpc.net #include using namespace std; typedef long long ll; int n; string s[101]; bool isPal(string s){ for(int i=0;2*i> n; for(int i=0;i> s[i]; } for(int i=0;i
문제 https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net #include #include #include using namespace std; bool compare(int x, int y){ return x > y; } int main() { int N; cin >> N; vector A; for(int i=0;i> temp; A.push_back(temp); } sort(A.begin(),A.end(),compare); ..
문제 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net #include #include #include using namespace std; int n; int arr[1001]; int dp[1001]; int main() { cin >> n; for(int i = 0;i> arr[i]; } int max = 0; for(int i=0;i
풀이 코드 배열 a,b를 만들어 숫자들을 저장한 다음, 배열 a를 오름차순 정렬한다. 그 다음, map을 이용하여 압축된 코드를 저장한다. map의 find 함수를 사용하면 찾고자 하는 값의 iterator을 가져오고, 만일 찾고자 하는 값이 없다면 map.end()을 반환한다. map을 순회하면서 a[i]가 있다면 k값을 할당하고, 없다면 ++k 값을 할당한다. 출력은 배열 b를 이용하여 map을 순회하면서 한다. #include using namespace std; typedef long long ll; #define num 1000001 map m; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n=0;int a[num]={0}; ..