본문 바로가기

전체 글

BOJ)1849 순열 문제: icpc.me/1849 (A[i]=i보다 큰 수들의 개수)일 때 원래 수열을 구하는 프로그램을 작성하면 된다. 작은 수 부터 채워 나간다고 할 때 A[1]이 5 라면 1은 수열의 6번째 수가 될 것이다. 우리는 수열을 세그먼트 트리를 이용하여 구해보자. 먼저 리프에 해당하는 모든 노드를 1로 채워준 후 구간합을 업데이트 시켜준다. 이후 a[i]를 확인 할 때 a[i]+1번째에 해당하는 노드를 찾아준 뒤 수열의 해당하는 자리에 i를 저장해 준다. 이후 노드 i를 0으로 초기화 시켜준다. 이런 방식으로 나보다 큰 수들중에서만 내가 몇번째 위치에 있는지 확인 하여 수열을 채워 나간다. 1234567891011121314151617181920212223242526272829303132333435#incl.. 더보기
BOJ)4195 친구 네트워크 문제 : icpc.me/4195 친구 관계가 생길 때 마다 가입한 두사람의 친구 네트워크에 몇명이 있는지 구하는 문제이다. 문제의 답은 union_find를 통하여 쉽게 구해줄 수 있지만 string으로 들어오는 입력 때문에 좌표 압축이나 map을 이용한 테크닉이 필요하다. -좌표압축 이용123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #include #include #include #include using namespace std;int par[200010];int t, n;int num[200010];vect.. 더보기
BOJ)9345 디지털 비디오 디스크(DVDs) 문제:icpc.me/9345 번호 순서대로 있던 DVD를 쿼리에 따라서 바꿔줄 때 a번부터 b번까지 DVD를 가져왔을 때 a~b번까지 DVD가 모두 있나 확인하는 문제이다. a~b번까지 DVD가 모두 있나 확인할 수 있는 방법은 a~b까지의 최댓값과 최솟값을 구해주어 a와 b인지 확인해주는 작업을 해주면 된다. 이는 세그먼트 트리를 이용하여 구해줄 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #define MAX_N 100000#define INF 987654321using namespace std;.. 더보기

티스토리툴바