차근차근

0. 제목 백준 11652 카드 BOJ 11652 카드 C++ 11652 카드 1. 문제 https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다. www.acmicpc.net 2. 풀이 적혀있는 수의 범위가 크기 때문에 자료형을 long long으로 사용하는 것이 핵심이다. 처음에 배열을 입력받은 후, sort로 정렬을 한다. 그 후 가장 앞의 원소부터 다음..

0. 제목 백준 10989 수 정렬하기 3 BOJ 10989 수 정렬하기 3 C++ 10989 수 정렬하기 3 1. 문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 계수 정렬(Counting Sort)를 사용하는 문제이다. 버블 소트와 같은 것을 사용하면 시간 초과가 난다. 계수 정렬은 수의 범위가 작을 때 사용하기에 적합하다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ..

0. 제목 백준10825 국영수 BOJ 10825 국영수 C++ 10825 국영수 1. 문제 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다. www.acmicpc.net 2. 풀이 이름, 국어성적, 영어성적, 수학성적을 pair를 사용하여 묶어준다. sort함수에서 쓰일 정렬 기준 함수인 comp를 주의해서 구현하면 된다. 3. 코드 1 2 ..

0. 제목 백준 11651 좌표 정렬하기 2 BOJ 11651 좌표 정렬하기 2 C++ 11651 좌표 정렬하기 2 1. 문제 https://www.acmicpc.net/problem/11651 2. 풀이 vector의 sort기준인 comp함수식만 잘 세우면 되는 문제이다. 좌표쌍을 vector에 넣어줘야 하므로 make_pair를 사용하였다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #include using namespace std; typedef pair P; int N; vector v; bool comp(P a, P b){ if(a...

0. 제목 백준 2252 줄 세우기 BOJ 2252 줄 세우기 C++ 2252 줄 세우기 1. 문제 https://www.acmicpc.net/problem/2252 2. 풀이 Topological Sort(위상 정렬)을 사용하는 문제이다. 위상 정렬은 indegree 즉, 자신에게 들어오는 노드 수를 계산하고 indegree가 0이 되면 먼저 정렬해 주는 것이다. 위상 정렬의 특징 중 하나는 사이클이 생기면 안된다는 것이다. indegree가 모두 0보다 크면 사이클이 생긴다는 의미이다. 따라서 위상 정렬은 indegree가 0인 것이 하나 이상 존재할 때 가능하다. 이 문제에서 1 3 이 주어졌을 때 1 다음에 3이 줄을 서야 한다. 방향을 나타내면 1 -> 3 으로 나타낼 수 있고 이 상황에서 3의..

0. 제목 백준 11650 좌표 정렬하기 BOJ 11650 좌표 정렬하기 C++ 11650 좌표 정렬하기 1. 문제 https://www.acmicpc.net/problem/11650 2. 풀이 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표로 증가하는 순서로 정렬하는 것이다. 비교기준인 compare함수를 보면 pair로 인자들을 받는다. compare함수는 위 조건에 만족하면 true를 반환하고 아니면 false를 반환한다. 그리고 vectorv(N); 이렇게 2차원 벡터를 선언해주었는데, (N)을 빼먹으면 안된다. vectorv; 후 v.resize(N); 을 해주어도된다. resize함수는 내부용량을 딱 정해놓고 사용하는 것이다. 만약 사이즈를 10으로 해놨을 경우 무조건 사이즈는 10이..

0. 제목 백준 2751 수 정렬하기 2 BOJ 2751 수 정렬하기 2 C++ 2751 수 정렬하기 2 1. 문제 https://www.acmicpc.net/problem/2751 2. 풀이 O(N^2)인 정렬을 사용하면 안된다. 왜냐하면 수의 개수의 범위가 1,000,000까지이기 때문이다. sort는 최대 O(NlogN)이기 때문에 시간내에 정렬이 가능하다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include #include using namespace std; int main(int argc, const char * argv[]) { int N; int num; vector arr; cin..

0. 제목 백준 2750 수 정렬하기 BOJ 2750 수 정렬하기 C++ 2750 수 정렬하기 1. 문제 https://www.acmicpc.net/problem/2750 2. 풀이 가장 작은 것을 앞으로 보내는 것이 핵심 아이디어인 선택 정렬을 사용하였다. 가장 작은 원소를 맨 앞으로 보내고 다음 Loop에서는 두번째 작은 원소를 두번째로 보내고 이런식으로 원소 개수만큼 Loop를 돈다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include using namespace std; int main(int argc, const char * argv[]) { int N; int ar..

0. 핵심 아이디어 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내면 어떨까? 1. 예시 1 10 5 8 7 6 4 3 2 9 1 5 10 8 7 6 4 3 2 9 1 5 8 10 7 6 4 3 2 9 1 5 8 7 10 6 4 3 2 9 1 5 8 7 6 10 4 3 2 9 1 5 8 7 6 4 10 3 2 9 1 5 8 7 6 4 3 10 2 9 1 5 8 7 6 4 3 2 10 9 1 5 8 7 6 4 3 2 9 10 //결국 가장 큰 값이 뒤로 오게 됨. 첫번째 Loop 끝. 1 5 7 8 6 4 3 2 9 10 1 5 7 6 8 4 3 2 9 10 .... 2. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using n..

0. 핵심 아이디어 가장 작은 것을 선택해서 제일 앞으로 보내면 어떨까? 1. 예시 1 10 5 8 7 6 4 3 2 9 1 2 5 8 7 6 4 3 10 9 1 2 3 8 7 6 4 5 10 9 1 2 3 4 7 6 8 5 10 9 1 2 3 4 5 6 8 7 10 9 1 2 3 4 5 6 7 8 10 9 1 2 3 4 5 6 7 8 9 10 2. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int main(int argc, const char * argv[]) { int i, j, min, index, temp; int array[10] = {1, 10, 5, 8, 7, 6,..