분류 전체보기 검색 결과
278 개의 검색 결과가 있습니다.
코딩/백준 (C++)

백준 11375번: 열혈강호 (C++)

접근 https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 이전에 풀었던 돌멩이 제거하는 문제와 같은 방식의 네트워크플로우 최대이분매칭을 이용한 문제였다. https://ca.ramel.be/248 백준 1867번: 돌멩이 제거 (C++) 접근 https://www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩..

2022. 6. 6. 16:31
코딩/백준 (C++)

백준 1867번: 돌멩이 제거 (C++)

접근 https://www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다. 입 www.acmicpc.net 각 줄의 돌의 수를 찾아 가장 많은 돌을 가진 줄부터 삭제하는 방향의 그리디 알고리즘으로 먼저 풀어보았다가 예상대로 틀렸다. 푸는 방향을 못찾아 다른 분의 풀이를 참고하였고, 네트워크 플로우의 한 종류인 최대 이분 매칭 알고리즘을 이용하여 푼다는 것을 확인했다. 알고리즘에 대한 이해는 아래 글을 참고하였다. https://cocoon1787.tistory.com..

2022. 6. 5. 23:17
코딩/백준 (C++)

백준 7420번: 맹독 방벽 (C++)

접근 https://www.acmicpc.net/problem/7420 7420번: 맹독 방벽 첫 번째 줄에 건물의 수 N과 거리 L이 주어진다. (3 ≤ N ≤ 1000, 1 ≤ L ≤ 1000, N과 L은 정수) 다음 N개의 줄에 거쳐 건물의 좌표 Xi와 Yi가 정수로 주어진다. (-10000 ≤ Xi, Yi ≤ 10000) 모든 건물의 좌 www.acmicpc.net 백준 1708번 볼록껍질에서 사용한 컨벡스헐 알고리즘을 이용하면 매우 쉽게 풀 수 있다. https://ca.ramel.be/245 백준 1708번 : 볼록 껍질 (C++) 접근 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. ..

2022. 5. 24. 00:38
코딩/백준 (C++)

백준 9240번 : 로버트 후드 (C++)

접근 https://www.acmicpc.net/problem/9240 9240번: 로버트 후드 첫째 줄에 로버트 후드가 발사한 화살의 수 C (2 ≤ C ≤ 100,000)가 주어진다. 다음 C개 줄에는 화살의 좌표가 주어진다. 좌표는 정수이고, 절댓값은 1,000을 넘지 않는다. www.acmicpc.net 백준 1708번 볼록 껍질 문제를 풀 때 쓰였던 convex hull 알고리즘을 이용하고, 구해진 볼록 다각형의 각 꼭짓점을 돌면서 최대 거리를 갱신하면서 탐색하면 풀 수 있는 문제였다. https://ca.ramel.be/245 백준 1708번 : 볼록 껍질 (C++) 접근 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ ..

2022. 5. 20. 23:21
코딩/백준 (C++)

백준 1708번 : 볼록 껍질 (C++)

접근 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 기하 문제에 볼록 다각형을 구하는 문제라서 ccw를 이용하는 것이라고 짐작은 했고, 혼자 풀어보려고 이리 저리 헤메다가 결국 실패하고 다른 분의 풀이를 참고하였다. 그 과정에서 sort 의 비교 함수를 제대로 사용해보았다. 이해하고 풀기는 했지만, 아직 누군가에게 설명할 정도로 이해하진 못해서 참고가 된 다른 글을 링크해두고 다음 기회에 설명을 이어나가려고 한다. http..

2022. 5. 20. 01:28
코딩/백준 (C++)

백준 11658번: 구간 합 구하기 3 (C++)

접근 https://www.acmicpc.net/problem/11658 11658번: 구간 합 구하기 3 첫째 줄에 표의 크기 N과 수행해야 하는 연산의 수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 www.acmicpc.net 세그먼트 트리의 응용 알고리즘인 펜윅 트리 알고리즘을 이용하여 문제를 해결하였다. 펜윅 트리가 무엇인지 아주 자세히 설명해놓은 글이 있어 링크를 남긴다. https://yabmoons.tistory.com/438 [ 펜윅트리(FenwickTree) ] 개념과 구현방법 (C++) 이번 글에서는 펜윅트리(FenwickTree) 에 대해서 이야기해보자. 이 ..

2022. 5. 19. 21:36
반응형