728x90 전체 글240 [C++] 백준 11000번: 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 중요풀이 그리디 알고리즘 활용에서 시간을 단축하기 위해 입력된 벡터를 O(N)의 시간복잡도만 확인하여 조건을 확인해보는 방법을 생각해봐야합니다. 우선적으로 받음 입력을 시작, 끝 시간 순으로 정렬을 시켜줍니다. 이후 벡터에서 꺼내 시간을 이동한다고 생각하여 중복되는 시간들의 수를 체크해줍니다. #include #include #include #include using namespace std; bool compare(pair a, pairb) .. 2021. 8. 22. [C++] set 라이브러리 Set 저장 데이터의 값이 유일한 자료구조(중복허용x) 노드 기반 컨테이너 임의 접근 불가능 균형 이진 트리로 구현 각 노드는 pair 구성 *multset은 첫 번째 조건인 중복허용을 가능하게 만든 set의 형태의 자료구조입니다. 라이브러리 include 및 선언 #include //set set 명; set s; 맴버함수 *일반 함수의 형태에 iterator를 파라미터로 사용하는 것보다 맴버함수를 직접사용하는 것이 효율적이다. set s; s.insert(12);// 원소 삽입 s.find(key);// key 값에 해당하는 원소를 찾아 반복자 반환 s.lower_bound(key);// key 값에 해당하는 원소가 시작되는 주소를 가리키는 반복자 반환 // 시간복잡도 O(log(N)) lower_b.. 2021. 8. 22. [C++] 백준 1202번: 보석 도둑 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제를 풀면서 중요한 개념을 배웠습니다. 중요 포인트 set 라이브러리 활용 upper_bound, lower_bound 개념 그래야 시간복잡도를 최소한으로 구현할 수 있습니다. #include #include #include #include using namespace std; struct Jewelry { int M; int V; }.. 2021. 8. 22. [C++] 그리디 알고리즘 예시 코딩 문제 작업의 수 N(1~100,000), 제한시간 D(1~10,000,000) 작업을 다수의 컴퓨터로 수행할 시 작업을 최소의 컴퓨터로 수행하는 컴퓨터의 수를 구하시오. 예시 1 10 14 7 5 4 6 1 2 3 5 2 3 computer1 : 7 3 2 computer2 : 5 1 2 5 computer3 : 4 6 3 #include #include // 작업목록을 담을 work 벡터 #include // 가까운 시간대를 찾기위한 우선순위 큐 #include // 배열 초기화 memset사용 using namespace std; int main(void) { ios_base::sync_with_stdio(false); cout.tie(); cin.tie(); int TC, N, D, input; i.. 2021. 8. 21. [C++] 백준 4386번: 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 유니온-파인 알고리즘의 개념과 이미 연결되어 있는 그래프를 파악하여 그래프에 사이클이 존재하는지 여부를 지속적으로 확인하여 줍니다. 이러한 기법을 크루스칼 알고리즘 또는 최소 스패닝 트리라고 합니다. #include #include #include #include using namespace std; class edge { public: int node[2]; float distance; ed.. 2021. 8. 19. [C++] 백준 4195번: 친구 네트워크 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 유니온-파인 알고리즘과 해쉬맵을 활용하여 풀이를 진행하였습니다. 해쉬맵은 인덱스가 많을 시 효율성이 떨어지지만 이렇게 자료가 한정적인 문제에서는 사용에 유리합니다. #include #include #include using namespace std; int N, M, parent[200001], cnt[200001]; map m; int find(int index) { if (pa.. 2021. 8. 19. [C++] 백준 2638번: 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 깊이 우선 탐색(DFS) 그래프 탐색 방식과 너비 우선 탐색(BFS) 방식을 모두 사용하여 문제 풀이를 진행 하였습니다. #include #include using namespace std; queueq, p;//q:치즈 위치 저장, p:이번 턴에 녹을 치즈들 int N, M; int page[101][101]; //탐색 방향 위, 아래, 왼쪽, 오른쪽 int idx[4] = {.. 2021. 8. 19. [C++] 백준 2108번: 통계학 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 풀이 각각의 단어에 맞는 식을 구현하였습니다. #include #include #include #include using namespace std; int coordinate[500001]; int cnt[8001]; int main() { vectorv; int N, k, total = 0; cin >> N; for (int i = 0; i > k; total += k; v.pu.. 2021. 8. 19. [C++] 백준 1976번: 여행 가자 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 그래프 탐색 기법을 이용하여 풀이를 진행하였습니다. 활용된 알고리즘으로는 유니온-파인 알고리즘을 활용하여 그래프들의 연결 상태를 파악하며 그래프 탐색을 진행합니다. #include using namespace std; int city[201]; int node[1001]; //보통 union find 알고리즘을 사용할 때 갱신을 작은 수쪽으로 수정해줍니다. //parent 찾기 int get.. 2021. 8. 19. 이전 1 ··· 12 13 14 15 16 17 18 ··· 27 다음 728x90
