백준 25406번: 식사 계획 세우기이전에 먹지 않은 음식 중에서 가장 인덱스가 앞에 있는 음식을 먹는다. 이 때 한 종류의 음식이 과반수를 넘어가면 그 음식 먼저 먹는다. 과반수를 넘는지 확인하기 위해 set 하나, 이전에 먹지 않은 음식 중 가장 인덱스가 앞에 있는

백준 25402번: 트리와 쿼리S에 속한 노드끼리 union하면서 몇개인지 함께 기록한다. n(n-1)/2 계산하면 정답.NPC 선발 문제였는데 기한이 지나버렸다..왜 틀렸는지 며칠 내내 봤는데 25만개짜리 배열에 memset을 100만번 해버렸다.. 난 바보야..각

화이팅!

백준 2287번: 모노디지털 표현숫자 i개 사용해서 만든 수 +\*-/ 숫자 j개 사용해서 만든 수 = cachei+j뺄셈, 나눗셈은 순서에 영향을 받기 때문에 뒤집어서도 해준다.이렇게 하면 괄호 생각 안하고 풀어도 됨. 아니 진짜 개어렵다.. 프로그래머스 스킬체크 레

백준 19608번: Searching for Strings모든 permutation에 대해 해시를 계산할 순 없고 그냥 알파벳 개수만 세서 a~z 개수가 같고, 해시값이 us에 없으면 집어넣는다. 이게 P4?..

아름다운 만영로 백준 17228번: 아름다운 만영로 아이디어 dfs로 탐색하면서 현재 해쉬값을 가지고 간다. 맨 처음에 계산한 P랑 일치하면 정답 개수 증가. 지금까지 거쳐간 알파벳들을 벡터에 push, 롤링해쉬 계산. 함수 호출 끝나면 pop. 코드 여담 >

백준 6206번: Milk Patternschar이 아니라 int를 쓰고, 해싱 충돌했을 경우 완전히 일치하는 개수를 세서 k-1개 이상인 경우 답을 갱신한다.라빈카프 넘 어렵다

백준 3033번: 가장 긴 문자열문자열 해싱. ABCED - > 2^4A + 2^3B + 2^2C + 2^1D + 2^0\*E부분 문자열마다 계속 해쉬값을 구하지 않고, 이전에 구한 값을 재활용해서 구할 수 있다. 개어렵다.. 해쉬값을 인덱스로 가지는 부분 문자열의 시

백준 24525번: SKK 문자열문자열에 포함된 K의 개수가 S의 개수의 2배여야 한다. S는 2, K는 -1, 그 외 글자는 0으로 해서 배열을 만들고, prefix sum을 구한다. 각 prefix sum의 값을 가지는 최소 인덱스를 기록하면 가장 긴 부분 문자열의

백준 11585번: 속타는 저녁 메뉴문자열을 두 개 이어 붙인 다음 거기서 찾으면 한바퀴 돌리면서 찾는거랑 똑같음. 이 때 처음부터 끝까지 찾으면 하나 더 찾을수도 있으므로 한칸 건너 뛴다. ex) ABCABC에서 ABC 찾기오늘 저녁 짬이 뭐더라..

백준 4354번: 문자열 제곱실패함수에서 fs.length-1은 가장 긴 접두사이면서 접미사의 길이이다. 우리가 구하는 n은 s.length/(s.length-fs.length-1)이다. 이 때 ABCAB같은 반례가 있기 때문에 나누어 떨어지는 경우에만 n으로 채택하도

백준 13504번: XOR 합입력받은 수열의 누적 XOR을 계산해놓는다. 이 값을 전부 트라이에 삽입하고, 각각의 값과 XOR했을 때 최댓값이 부분수열 XOR의 최댓값이다. trie를 이런식으로 만드는게 훨씬 간편한듯. 노드 번호를 전역 변수로 관리한다. 새로운 노드를

백준 13710번: XOR 합 3앞에 올린 두가지 문제를 응용하면 된다. vl-1^vr = al^al+1^..ar-1^ar이라는 사실과비트별로 쪼개서 n번째 비트에 1이 몇 개 있는지 구하고 1의 개수 × 0의 개수 하면 값을 알 수 있다. XOR 고수의 길.. x^x

백준 2830번: 행성 X3입력받은 모든 정수중 a번 비트에 1이 몇개 있는지 기록한다. 최대 100만이니까 0번 비트 ~ 19번 비트까지 기록하면 됨. 이제 각 비트별로 1의 개수 × 0의 개수 하면 합을 구할 수 있다!수학 넘 어렵다.

백준 10464번: XORvi = a1^a2^a3^...ai라 하자. 이 때 i%4 == 3인 경우 vi 가 0이 된다!또 al^al+1^...ar-1^ar = vl-1^vr이다. 이를 이용하면 쉽게 문제를 풀 수 있다.누적합 느낌?

백준 16903번: 수열과 쿼리 200이랑 1만 있는 트라이를 만든다. 입력받는 정수의 맨 앞쪽 비트 (2^29)부터 쭉 훑으면서 둘 다 있으면 XOR값을 최대로 할 수 있도록 선택, 둘 중 하나만 있으면 그거 선택. 다 더하면 정답!삭제 연산은 cnt를 감소시킨다.

백준 5467번: Type PrinterTrie를 구성하고 재귀적으로 깊이가 얕은 글자부터 출력한다.마지막에 최대한 긴 단어를 치고 지우지 않고 끝내야 한다.

백준 3080번: 아름다운 이름노드 자식 개수만큼 permutation 구하면서 올라가면 된다. 로직 짜는건 쉬운데 그냥 Trie child26 해도 MLE, map<char, Trie> child해도 MLE.. 그나마 메모리 제일 적게 사용하는 vector 만들

백준 5446번: 용량 부족지워야 하는 파일, 지우면 안 되는 파일 둘 다 트라이에 insert. 이 때 지워야 하는 파일은 노드 마지막에 종료 표시, 지우면 안 되는 파일은 모든 노드에 지울 수 없다고 표시. 노드 하나가 removable 하면 그 모든 자식들도 re

백준 19585번: 전설색상은 trie에 insert, 닉네임은 unordered_set에 insert.그리고 쿼리 앞부분부터 트라이에서 찾는다. 트라이에 알파벳이 존재하지 않으면 return false, 트라이에 해당 색상이 존재하고, 뒷쪽 substring이 uno