전체 글153 [백준/C,C++] 11279번: 최대 힙 www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 풀이 최대 힙을 구현하는 문제입니다. #include using namespace std; const int MAX = 100001; class MaxHeap { private: int heap[MAX]; int idx = 0; public: int size(); void push(int data); int pop(); void swap(int* a, int* b); int select(in.. 2021. 4. 21. [백준/C,C++] 9019번: DSLR www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 최단 거리 찾기 종류의 문제인데, 살짝 변형된 문제입니다. 이 문제에서 중요한 것은 실행된 명령어를 어떻게 유지할 것인가인데, 문자열로 유지를 했더니 시간 초과가 났습니다. 그래서 다른 분들의 코드를 참고해 pair에 현재 사용된 명령어와 이전 노드의 번호를 저장해 마지막에 역순으로 출력해주는 방식을 사용했습니다. #include #include #include #include using na.. 2021. 4. 21. [백준/C,C++] 1707번: 이분 그래프 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 풀이 이분 그래프라 함은 모든 꼭짓점을 빨강과 파랑으로 칠하되, 모든 변이 빨강과 파랑을 포함하도록 색칠할 수 있는 그래프를 말합니다(출처 : 위키백과). 즉 같은 레벨(깊이)의 정점은 모두 같은 색으로 칠할 수 있어야 합니다. 너비 우선 탐색을 하며 방문하지 않은 정점이라면 이전 레벨의 노드와 반대의 색을 칠하고 방문한 정점이라면 이전 레벨의 노드와 색이 반대인지 체크한 후에 반대가 아니라면 이분.. 2021. 4. 21. [백준/C,C++] 1389번: 케빈 베이컨의 6단계 법칙 www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 각 유저를 출발 노드로 모든 노드를 방문할 때까지 BFS를 실행한 뒤, 모든 노드를 방문했을 때의 깊이(depth)를 더한 값이 가장 작은 노드를 출력하면 됩니다. 모든 정점에서 모든 정점을 방문해야 할 때, 플로이드 와샬이라는 알고리즘을 사용할 수 있던데 자세한 내용은 ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4.. 2021. 4. 21. 이전 1 ··· 15 16 17 18 19 20 21 ··· 39 다음