백준

[baekjoon 11650] 좌표 정렬하기- 정렬 (C++)

www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 기본 vector container를 이용한 정렬 문제이다. 저번에 언급했던 compare 함수를 임의로 정의해서 sort 해주었다. 파라미터는 vector의 내용물인 pair로 받아주었다. 또한 &로 받아서 값의 복사가 아닌 참조를 해주어야 시간을 절약할 수 있다. #include #include #include using namespace std; int..

[baekjoon 1978] 소수 찾기- 소수, 에라토스테네스의 체 (C++)

www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 소수 판정 알고리즘인 에라토스테네스의 체를 이용해서 풀었다. - 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. (baekjoon 2960 에라토스테네스의 체 문제에서 참고) 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. 따라서 소수 P를 찾은..

[baekjoon 2468] 안전영역 - 그래프탐색(BFS, DFS)

www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 기본적으로 배열에 데이터를 받아서 그래프 탐색을 수행하는 문제였다. 다만 문제 마지막 조건에 아무 지역도 물에 잠기지 않을 수 있다는 조건으로 바로 맞추진 못했다.. #include #include using namespace std; int bound[101][101], N, height, resultMax, xmove[4] = { 1, -1, 0, 0 }, ymove[4] = { 0, 0, 1, -1 }; bool..

[baekjoon 14438] 수열과 쿼리 17 - 세그먼트 트리

www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net 기본적인 세그먼트 트리 문제. 최근에 전공 기말프로젝트 하느라 문제를 못풀었더니 바로 풀리진 않았다. 함수는 init, 구간의 최솟값을 저장해주는 minTree, update 함수로 구성하였다. update함수를 구현할때 diff값을 이용해서 (기존 값 - 변경하려는 값) 했었는데 곱셈이나 나눗셈 등 애매한 경우가 있어서 아예 ta..