전체 글137 백준 g4 2617 구슬 찾기 c++ https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 문제 각각 무게가 다른 구슬 N개가 주어지고, M개의 구슬 2개 간의 대소 관계가 주어진다. 이때 구슬 무게의 중앙값을 찾으려고 한다. M개의 대소 관계가 주어지면 중앙값이 절대로 될 수 없는 구슬들을 알 수 있다. 중앙값이 절대로 될 수 없는 구슬들의 개수는? 예제 2>1 4>3 5>1 4>2 가 주어지면, 1보다 큰 구슬이 2, 4, 5로 3개이므로 1은 중앙값이 될 수 없다.. 2024. 3. 19. 백준 g4 1707 이분 그래프 c++ https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 K개의 테스트 케이스가 주어진다. 각 테스트 케이스에서 V, E와 E개의 간선이 주어진다. 해당 그래프가 이분 그래프 인지 아닌지를 출력하기 *이분 그래프: 정점들을 두 집합으로 나눴을 때, 집합 내의 원소들끼리는 인접하지 않는 그래프 풀이 서로 인접한 노드들은 다른 집합에 속해야 한다. 노드들을 집합 A, 집합 B로 나눈다고 했을 때 vis에는 1, -1 으로 표시한다. 인접한 노드들을 만.. 2024. 3. 18. 백준 g5 2660 회장뽑기 c++ https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 문제 한 사람이 있을 때, 다른 모든 회원과 친구 -> 1점 다른 모든 회원과 친구 or 친구의 친구 -> 2점 ... 이런 식으로 점수를 매겨서 회장 후보를 뽑는다. 회장 후보의 점수, 회장 후보의 수, 각 회장 후보의 번호를 차례대로 출력 이때 친구이면서 친친일 때는 친구로 생각해야 하며, 모두가 건너건너면 다 아는 사람임(다 연결된 하나의 그래프) 풀이 문제를 정리하면 가장 거리가 먼 친구와.. 2024. 3. 18. 백준 s1 11403 경로 찾기 c++ https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 가중치가 없는 그래프의 인접행렬이 주어졌을 때, i노드 -> j노드로 갈 수 있는지 나타내는 N*N 배열을 출력하기 갈 수 있으면 1, 그렇지 않으면 0 풀이 각 정점에서 시작해서 DFS로 방문할 수 있는 노드를 answer[시작정점][방문가능한정점] = 1로 둔다. 이때 방문할 수 있다 == 갈 수 있다이므로, 결국엔 DFS의 vis배열과 같게 된다. 수도 코드 for start: 1번 노드 ~ N번 노드 dfs로 가.. 2024. 3. 17. 백준 s2 5567 결혼식 c++ https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 문제 상근이는 친구와 친구의 친구까지 결혼식에 초대하려고 한다. 친구 관계가 그래프 형식으로 주어질 때, 초대하는 사람의 수는? 풀이 그래프 탐색으로 거리가 2인 노드들의 개수를 세주면 된다. 다만 주의할 점은 DFS로 풀면 1, 2, 3이 서로 연결되어 있을 때 3이 거리가 2로 취급되므로 틀렸습니다 가 뜰 수 있다. 전체 코드 /*boj s2 5567 결혼식*/ #include .. 2024. 3. 16. 백준 g2 1781 컵라면 c++ https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 문제 N개의 문제가 주어지고, 각 문제의 dead line과 맞혔을 때 주어지는 컵라면 개수가 주어진다. 예시) 문제 번호/ 데드라인 / 컵라면 수 1 2 3 4 5 6 7 1 1 3 3 2 2 6 6 7 2 1 4 5 1 동호가 먹을 수 있는 최대 컵라면 개수는? 풀이 문제를 보자마자 그리디인 건 알았지만 앞에서부터 정렬하는 방식으로는 도저히 방법이 떠오르지 않았다. 결국 답지를 슬쩍 봐서 뒤에서부터 시.. 2024. 3. 15. 백준 g2 1655 가운데를 말해요 c++ (set, priority queue) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 백준이가 N개의 숫자를 말한다. 백준이의 동생은 지금까지 나온 N개의 숫자 중 중간값을 말해야 한다. 만약 개수가 짝수일 경우에는 더 작은 수를 말한다. N -99 1 2 5 19 그대로 원래 개수가 짝수고, 새로운 값이 오른쪽에 추가 되는 경우 ex. 1 2 5 10 -> 1 2 2 5 10 cursor++ 원래 개수가 홀수고, 새로운 값이 왼쪽에 추가 되는 경우 ex. 1.. 2024. 3. 14. 백준 g4 13975 파일 합치기 3 c++ https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 문제 설명과 풀이는 https://kyj0032.tistory.com/95 참고. 그냥 똑같음 testcase, 장 수 (K), 각 장의 파일 크기가 다르므로 int -> long long 으로 바꿔주어야 함 전체 코드 /*boj g4 13975 파일 합치기 3*/ #include #include using namespace std; int T, N; int main(void) { ios::s.. 2024. 3. 14. 백준 g4 1715 카드 정렬하기 c++ https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 정렬된 카드 묶음 A, B가 있을 때 두 묶음을 합치는 방법은 (A + B)번 비교하는 것이다. N개의 카드 묶음이 있을 때, 최소 몇 번 비교해서 합칠 수 있는지 구하기 풀이 예를 들어 10 20 30 50이 있다고 하면 (10 + 20) > (30 + 30) -> (50 + 60) 이런 식으로 계산을 하게 된다. 앞에서 더해진 A+B의 합이 계속해서 다른 카드 묶음과 비교되.. 2024. 3. 14. 이전 1 2 3 4 5 6 7 8 ··· 16 다음
