알고리즘

[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 14425] 문자열 집합- 문자열, map (C++)

www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 요즘 map 자료구조를 연습 중이다. 이 문제는 간단한 문제인데 map 자료구조를 사용해서 해당 string key 값을 통해 value값을 비교해서 풀어주었다. #include #include #include using namespace std; int N, M, cnt; string word; int main() { ios::sync_with_stdio(false); cin...

[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..