profile
SKKU Computer Education / ROKAF
post-thumbnail

프로그래머스 스킬체크 레벨 4

화이팅!

2022년 6월 22일
·
0개의 댓글

백준 2287번: 모노디지털 표현

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

2022년 6월 21일
·
0개의 댓글

백준 19608번: Searching for Strings

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

2022년 6월 7일
·
0개의 댓글

백준 17228번: 아름다운 만영로

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

2022년 6월 6일
·
0개의 댓글

백준 6206번: Milk Patterns

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

2022년 6월 3일
·
0개의 댓글

백준 3033번: 가장 긴 문자열

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

2022년 6월 3일
·
0개의 댓글

백준 24525번: SKK 문자열

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

2022년 5월 25일
·
0개의 댓글

백준 11585번: 속타는 저녁 메뉴

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

2022년 5월 6일
·
0개의 댓글

백준 4354번: 문자열 제곱

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

2022년 5월 5일
·
0개의 댓글

백준 13504번: XOR 합

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

2022년 4월 30일
·
0개의 댓글

백준 13710번: XOR 합 3

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

2022년 4월 28일
·
2개의 댓글

백준 2830번: 행성 X3

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

2022년 4월 28일
·
0개의 댓글

백준 10464번: XOR

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

2022년 4월 27일
·
0개의 댓글
post-thumbnail

백준 16903번: 수열과 쿼리 20

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

2022년 4월 26일
·
0개의 댓글

백준 5467번: Type Printer

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

2022년 4월 25일
·
0개의 댓글
post-thumbnail

백준 3080번: 아름다운 이름

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

2022년 4월 24일
·
0개의 댓글

백준 5446번: 용량 부족

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

2022년 4월 24일
·
0개의 댓글

백준 19585번: 전설

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

2022년 4월 23일
·
0개의 댓글

백준 16934번: 게임 닉네임

백준 16934번: 게임 닉네임단어를 루트에 삽입하면서 하나씩 출력한다. 그러다가 다음 알파벳이 자식 노드로 존재하지 않으면, print를 false로 변경하고 재귀호출한다. print가 true인 경우에만 알파벳을 출력한다.같은 닉네임으로 가입한 유저를 숫자로 구분하

2022년 4월 22일
·
0개의 댓글

백준 5670번: 휴대폰 자판

백준 5670번: 휴대폰 자판자동완성이 안되는 경우는 단어가 완성되는 경우, 혹은 자식이 2개 이상인 경우이다.모든 단어가 같은 알파벳으로 시작하더라도 처음에는 버튼을 한 번 눌러줘야 한다.다들 C-style 문자열(const char\*)로 trie를 구현하고, 그걸

2022년 4월 20일
·
0개의 댓글