N coding

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

Manacher's Algorithm 시간복잡도 O(N) 문자열의 길이 N만큼의 숫자 배열 A를 만든다. 이 때 A[i]는 i를 중심으로 한 팰린드롬의 최대길이이다. -> str[i-a[i] : i + a[i]] 는 팰린드롬 문자열이고 str[i-a[i]-1 : i + a[i]+1] 은 팰린드롬이 아니다. 알고리즘 진행 1. i 는 0 ~ N-1까지 진행된다. 2. j r 인 경우, i 이전의 팰린드롬 중 i를 포함하는 팰린드롬이 없다. A[i]는 0 i str[h + A[h] +1] != str[h - A..

해야 하는 것 1. 접두사 == 접미사인 애들의 길이를 찾는다.2. 걔네가 몇 번 나오는지 찾는다. 내가 문자열과 쿼리를 푼 방법으로 찾았다. 접두사 == 접미사이려면 suffix array를 구했을 때, 1. 원본 문자열과 lcp가 존재해야하고, 그 lcp의 길이가 자기 자신의 길이와 같아야한다.2. 그리고 그 cnt는 원본 문자열과 자기 자신의 sa상에서 떨어진 거리이다. sfx상에서 원본 문자열보다 위쪽에 있는 애들은 그냥 구해주면 된다.아래쪽에 있는 애들도 그냥 구해주면 된다.다만 위쪽에 있는 애들이 아래쪽에도 계속 공통으로 나올 수 있고그 한계는 자신의 길이보다 짧은 lcp가 나올때 이므로 minn값이 바뀔때마다그 minn길이의 ans가 있는 지 확인한 후 있으면 cnt를 넣어주었다.더해줄때 하..

진짜 극혐... 어제부터 계속 붙잡고 있었다.딱히 붙잡고 있을만큼 영양가 있는 문제는 아니었는데이게 풀이가 suffix array랑 아호코라식 두개가 있는데 suffix 풀이가 궁금해서 내가 그나마 풀 수 있는 아호코라식으로 열심히 비벼봄..ㅠcoci에 솔루션은 있는데 정답 코드가 없다. 일단 나는 보자마자 아호코라식이 생각나서 그걸로 접근했다-> 26*4*5000*5000하면 당연히 메모리 터짐그냥 Trie면 내가 아름다운 이름을 푼 방식이나 그렇게 접근할텐데아호코라식이라 queue에서 bfs를 돌 때 구하기 좀 빡세서.. 쥬륵map으로 해봐도 안되고 -> 근데 아름다운 이름에서도 map을 써본 결과 map은 딱히 메모리를 엄청나게 줄여주진 않는 거 같다. 얘는 쓸때마다 터짐결국 질문검색에서 찾다가 v..

구현문제 나는 삼성 B형 연습중이었어서 dfs말고 bfs쓰고, queue도 직접 구현하였다. 디코딩하고 그림을 찾아내면 된다. 그림은 그 내부의 빈공간의 개수를 기준으로 찾으면 됨. 나는 일단 검은부분을 각각 idx를 올리면서 구해주고 - 각각의 그림은 다른 값을 갖게됨 다음으로 하얀부분에 들어가는데 그 하얀부분이 만나는 검은 부분의 값이 한 개일때 idx의 내부빈공간++을 해줌 그리고 counting sort로 출력~! (외부로 나가는 건 또 따로 처리) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747..