알고리즘98 백준 g5 2166 다각형의 면적 c++ https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 문제 N개의 점으로 이루어진 다각형의 넓이 구하기 N개의 x y 좌표가 주어진다. 풀이 어떻게 풀까 고민을 하다 CCW, 신발끈 정리라는 공식을 이용해서 푼 글들을 보았다. 다각형은 한 점을 기준으로 3개의 점으로 이루어진 삼각형들로 나눌 수 있다. 이들을 모두 더하면 된다. 혹시 음수가 나오면 그 부분은 방향이 반대이므로 음수가 나온 것이기 때문에 그냥 더해주면 된다. 마지막 최종 값에만 절댓값을 씌워주기만 하면 된다. .. 2024. 3. 20. 백준 g4 1043 거짓말 c++ https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 사람 수 N과 진실을 아는 사람들 번호가 주어진다. M개의 파티가 주어진다. 각각의 파티에서 지민이는 1. 진실을 아는 사람들이 왔을 때 2. 다른 곳에서 진실을 얘기했는데 똑같은 사람이 파티에 왔을 때, 그 파티에서 거짓말이 아니라 진실을 말해야 한다. 지민이가 거짓말을 할 수 있는 파티의 개수는? 풀이 문제를 정리하면, 진실을 아는 사람과 한 번이라도 같은 파티에 참여하는 사람들, 그런 사람들과 같.. 2024. 3. 19. 백준 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. 백준 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. 이전 1 2 3 4 5 ··· 11 다음
