알고리즘/백준 & swacademy108 BOJ 8986 - 전봇대 (삼분탐색) https://www.acmicpc.net/problem/8986 삼분탐색 설명 https://blog.naver.com/kks227/221432986308 unimodal 함수에 대한 설명 유념 삼분탐색에서 핵심은 이 문제를 예를들어 탐색할 큰범위가 1~1e9일때, 최소값이 들어있는 작은범위(1e3이하)를 찾아주는 것이다. (이분탐색처럼 딱 한가지 값이 나오도록 하면 무한루프에 빠질 위험이 크다.) 블로그에선 unimodal한 함수에 대해 얘기하는데, 다른 출처에선 convex한 그래프에서 적용할 수 있다고 표현하기도 했다. 1차원 축에 최대 1e5개의 전봇대가 distinct 위치에 설치돼 있다. 모든 전봇대가 같은 간격을 두고 서도록 전봇대를 움직일 때, 움직이는 횟수의 합의 최소를 구하라 간격이 .. 2020. 5. 12. BOJ 10167 - 금광 (세그트리, 분할정복) https://www.acmicpc.net/problem/10167 현장에서 100%받은 학생이 없었다는 문제 https://www.youtube.com/watch?v=NHf7v-_azYs&list=PLN3yisVKGPfh_sdb_pxGMP3lTF91DOgOr&index=31 위 영상 참고했습니다. www.acmicpc.net/problem/17975 유사문제 좌표평면 위에 최대 3000개의 정점이 주어진다. 각 정점마다 cost가 주어진다. 어떤 직사각형 안에 담을 수 있는 cost합의 최대를 구하라 1. 좌표압축을 해도 문제의 통일성을 해치지 않는다. 좌표값을 10의 9승에서 10의 3승정도로 줄일 수 있다. 2. 직사각형의 좌하단 꼭지점을 (x1,y1), 우상단 꼭지점을 (x2,y2)라고 뒀을 때 .. 2020. 5. 11. BOJ 14565 - 역원 구하기 (확장 유클리드) https://www.acmicpc.net/problem/14565 임의의 정수 a,n (a a; cout 2020. 5. 5. BOJ 2472 - 체인점 (다익스트라, 좌표압축, 세그트리, 수학) https://www.acmicpc.net/problem/2472 이런 문제 3문제를 3시간안에 중학생이 푼다 최대 n개의 정점으로 이뤄진 무방향 가중치 그래프가 주어진다. (n> u >> v >> w; g[u].push_back({ v,w }); g[v].push_back({ u,w }); } memset(d, 0x3f, sizeof(d)); for (int i = 0; i query; while (query--) { int i; cin >> i; cout 2020. 4. 22. 이전 1 2 3 4 5 6 7 8 ··· 27 다음
