N coding

해야 하는 것 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..

ucpc c번 구현이 극혐이긴한데 또 생각보다 별거 없기도 하다. 내가 https://www.acmicpc.net/problem/13016 문제를 푼거랑 비슷한 방식의 트리dp를 사용하면 된다. ucpc 당시에는 원래 그래프에서 트리의 지름을 하나 구하고 트리의 지름에 속하지 않는 노드를 가지고 다시 sub지름을 구해서 잘 연결해준다. 로 접근했었는데 이러면 트리에 같은 크기를 갖는 지름이 여러개 있을 경우 어떤 지름을 원래 지름으로 선택하느냐에 따라서 최대값이 이상하게 나올 수 있다. 그래서 정해는 모든 간선을 잘라본다. 이다. 근데 모든 간선을 자를때마다 subtree의 지름과 그 subtree를 제외한 나머지 트리의 지름을 구해서 연결하면 O(n^2)이 된다. 본선당시에 다들 n^2까진 생각했을 것..

타워 디펜스를 풀고나서 이 문제를 풀면 비슷하게 보인다. black인 노드를 기준으로 세로방향(위 t, 아래 f) 가로방향 (왼 t, 아래 f)의 두가지 상태를 가진다. black인 노드의 사방을 보면서 만약 위나 아래중에 하나만 존재한다면 얘는 반드시 그 하나랑 연결되야 하므로 논리식을 세워준다. (black i의 위 or black i의 위) 역시 가로방향도 마찬가지로 해준다. 만약 black i가 위에 잇는 w랑 연결이 된다면 그 w랑 연결될 수 잇는 가능성이 있는 다른 아이들은 다 연결불가이다. 그런 의미에서 w를 타고 들어가서 (black i의 아래 or black j의 ~방향)의 논리식을 세워줬다. 12345678910111213141516171819202122232425262728293031..

https://www.acmicpc.net/problem/3789 suffix array nlog n으로 짠 코드plzrun님 블로그에서 많이 참고하고 마리오블로그에서 lcp부분만 참고했다. 어떤 password가 주어졌을때그걸 왼쪽으로 1번씩 민 각각의 문자열 중에 가장 사전순으로 작은 아이의 시작 인덱스를 출력하면 된다. alabla 를 한번씩 민다면lablaaablaalblaala ... 이런식으로 총 n개가 나올 것이다이것들을 사전 순으로 정렬했을때 가장 위에 오는 문자열의 맨 처음 문자가 원래 문자열의 몇번째 애인지 출력하는 거임. 결국에는 환형이 되므로 나는 입력받은 문자열을 붙여서 2배로 늘리고가장 먼저 나오는 n보다 작은 인덱스를 출력하는데,문자열이 사전 순으로 같은 경우 인덱스가 작은 걸..