N coding

백준 3392_화성지도 nywoo19.blog.me/221249202521 3392_화성지도 새로운 알고리즘을 알게 되었다. line sweeping, plane sweeping인데 초면이라 아직은 잘 모르겠다. 비슷한... blog.naver.com

백준 14459_소가 길을 건너간 이유 11 nywoo19.blog.me/221464265033 14459_소가 길을 건너간 이유 11 약간 seg lis 느낌??골드문제는 n^2 dp로 풀었는데 얘는 n이 10^5라서 안된다.​cross되는 횡단보도가 없으... blog.naver.com

백준 5922 above the median nywoo19.blog.me/221707499752 5922_Above the median 굉장히 단순한 문젠데 이상한 거에 집착해서 굉장히 복잡하게 풀었다.걍 앞에서부터 펜윅트리로 psum 쓰면 ... blog.naver.com

모든 q에 대해 a > x && b > y && c > z인 아이가 하나라도 있는지 확인하는 걸 어떻게 빠르게 할수있나 싶어서 한참 고민하다가 질문검색에서 솔루션을 봤는데 세그먼트 트리를 사용하는 새로운 방식(?)을 안 느낌이었다.진짜 다들 똑똑한듯... 우리가 비교해야하는 변수가 3개뿐이어서 가능한 방법인 것 같다. 1. 일단 A와의 거리를 기준으로 정렬해준다. 이러면 앞에 나오는 A가 자신보다 작거나 같다는 것은 확실해진다.2. B와의 거리를 좌표압축을 하여 세그먼트 트리상의 인덱스로 넘긴다.3. C와의 거리는 세그먼트 트리에 저장되는 값이 된다. 4. 이 때 거리가 0 ~ 자신의 거리 - 1 인 인덱스에 있는 애들 중에 MIN값을 추출해왔을 때 자신의 C보다 작다면 자신은 매장을 설치할 수 없는 구..

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109#include #include #include #include using namespace std;#define inf 10000000 int n, a, b, c, k, d, e;int mx = 0, mn = inf;int par[100001][21], maxx[100001][21], minn[100001][21];i..

계속 전함을 segment tree에 넣을 생각만 하고 있어서, 전함을 w 가 큰 거 부터 넣는다.끝나는 지점에 w를 넣고 시작지점-1 에 -w를 넣어서 레이저를 x부터 N까지 합을 구해볼까 등등..근데 이것저것 다 고민해도 삭제가 가장 걸림돌이 되었다. 그러다가 레이저는 기준점이 하나잖아? 라는 생각에서 레이저를 segment tree에 넣으면 모든게 챡챡 풀린다는 것을 깨달았다. 1. 레이저가 x점기준, y점기준으로 들어오니까 각각을 나눠서 세그먼트트리를 2개를 만든다.2. 세그먼트 트리는 좌표를 (좌표압축해야함) 표현하고 있고 안에 들어있는 값은 그 좌표를 뚫는 레이저의 가장 작은 인덱스이다. (가장 먼저나오니까)3. 각각의 전함의 x1 - x2 를 x좌표 세그트리에 넣어서 그 사이를 뚫는 레이저의..

되게 막연하게 생각되었는데처음에는 10^6이고 총 사용할 수 있는 엣지가 60개니까 1 -> 2 로 갈 때 0 ~ 9 * 10^i로 표현하려고 했다.근데 10진수로 하니까 L보다 큰 수를 막는 게 너무 어려워서 2진수로 방향을 틀었다이때 최대 노드 N이 20이고, 10^6이 최소 20개의 비트로 표현되므로 딱 맞다. 좀 거지같이 그리긴했지만이런 느낌으로 표현하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #include #include #include #inclu..

고통받은 문제 어렵진 않은데 처음에 문제 잘못생각해서 겁나 어렵게 생각하다가 그래프 구성 못하고 가만히 있다가잘못생각했다는 걸 깨닫고 짰는데 또오 출력 바로 하려고 하다가 오지게 틀린 문제다.결과값 개수를 이미 들은 것중에 후보에 나온 애들의 개수를 세서 totalflow에서 빼서 출력했는데생각해보니 그러면 음수값이 나올수도 있어서... 당연히 틀리는 코드였다 ㅠ 사전순으로 출력이 아니라면 그냥 유량으로 쉽게 풀리는데사전순으로 출력이어서 mcmf로 풀었다.이미 들은 과목이면 반드시 포함시키는 게 이득이니까 그럴수 있게 가중치를 0으로 주었고그렇지 않은 과목이면 사전순으로 가중치를 주었다. 이분매칭으로 푸신 분도 있고, 그냥 유량으로 푸신 분도 있더라 123456789101112131415161718192..

구현거지라서 고생함 i, j 까지 오는 세 점의 최단거리를 구하자 1) 두 죄수가 다른 탈출구로 나오는 경우 2) 두 죄수가 같은 탈출구로 나오는 경우 2번의 경우엔 그냥 각각 최단거리 구해주면 됨 1번의 경우엔 외부에서 들어오는 거 + 죄수1에서 나가는 거 + 죄수2에서 나가는 거 - (만약 그 점이 #이라면 겹치는 거 2 빼줌 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include #include #include #include #..

나는 이분탐색 + 유량으로 풀었는데, 사실 가중치가 1이라서 그냥 이분매칭이다.주차장 문제랑 좀비 아포칼립스 문제를 짬뽕시킨 느낌이었다.아마 이분 매칭이면서 시간에 따른 정점 분리도 해서 그런 것 같다. 탈출구를 시간에 따라 정점 분리를 해줬다. 1초일때의 탈출구, 2초일때의 탈출구... 그리고 각각 1의 가중치로 sink와 연결빈칸인애들은 가중치 1로 source와 연결해준다. (이 때 가중치 = 유량은 사람을 뜻함)빈칸이나 벽인 애들은 굳이 해 줄 필요가 없다. 그리고 빈칸에서부터 탈출구까지의 거리를 구했다.이 때 나는 모든 빈칸을 출발지로 하고 bfs를 돌렸는데, 플로이드 워셜로 하신 분도 있고아니면 탈출구의 갯수가 (일반적으로) 더 적으니까 탈출구를 기준으로 bfs 돌려도 될거같다. 정점개수가 작..