1. border 어떤 문자열의 prefix이면서 동시에 suffix이기도 한 부분문자열을 border라고 부른다. 이 border와 관련된 문제를 해결하는데 z function이 매우 강력하다. z function의 정의에 대해 생각해본다면.. z[i]는 s와 s[i,...,n-1]의 가장 긴 공통 접두사의 길이를 뜻한다 https://deepdata.tistory.com/1000 문자열과 접미사의 가장 긴 공통 접두사의 길이를 찾는 z 알고리즘 배우기 1. z - function 길이 n인 문자열 s에 대하여 z[i]는 s의 i번째 접미사 s[i,i+1,...]과 s와의 최대 공통 접두사의 길이를 말한다 정의에 의하면 z[0]는 s와 s의 최대 공통 접두사의 길이로 s 그 자체의 길이 n deepda..
1. 문제 코딩테스트 연습 - 특정 옵션이 포함된 자동차 리스트 구하기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 options라는 변수에서 '네비게이션'이라는 값이 포함된 행을 추출하는 문제인데... options라는 변수 타입을 먼저 체크해보자. VARCHAR(255)라는걸 볼수 있는데 문자열이라는 소리다. 이 문자열에서 '네비게이션'이라는 부분문자열이 포함된 값을 가지는 행만을 추출하면 된다 문자열에서 특정 문자열이 들어있는지 체크하는 방법은 LIKE를 이용하는 것이다 https..
1. 부분문자열 검색 z-function의 대표적인 활용으로 특정한 문자열 t에 패턴 p가 몇번이나 존재하는지 찾아낼 수 있다. 이를 위해 새로운 문자열 s = p + # + t라는 문자열을 만들자. 여기서 #은 p와 t를 구분하기 위한 문자로, p,t 어디에도 등장하지 않는 문자여야한다. 이제 s에 대한 z-function을 계산하자. [0,len(t)-1]의 임의의 i에 대하여... z[i+len(p)+1]이 len(p)와 같다면, t의 i번째 위치에 p가 1번 등장한 것이다. 문자열 t 위에 있는 위치인 i+len(p)+1에 대하여.. z[i+len(p)+1]은 s와 일치하는 가장 큰 공통 접두사의 길이로, 이게 len(p)라는 것은 s의 접두사인 p의 길이와 일치하기 때문이다. 2. 연습문제 17..
1. z - function 길이 n인 문자열 s에 대하여 z[i]는 s의 i번째 접미사 s[i,i+1,...]과 s와의 최대 공통 접두사의 길이를 말한다 정의에 의하면 z[0]는 s와 s의 최대 공통 접두사의 길이로 s 그 자체의 길이 n이 될텐데 일반적으로 잘 정의하지 않는다. z[0] = 0으로 정의하기도 하고 문제에 따라 필요하다면 z[0] = n으로 정의하기도 한다. 예를 들어 'abacaba'에 대하여... z[1]은 'abacaba'와 'bacaba'의 최대 공통 접두사의 길이로... 공통 접두사가 존재하지 않으니 0 z[2]는 'abacaba'와 'acaba'의 최대 공통 접두사의 길이로 'a'가 있으니 z[2] = 1 z[3]은 'abacaba'와 'caba'의 최대 공통 접두사의 길이로..
1. 문제1 3216번: 다운로드 (acmicpc.net) 3216번: 다운로드 첫째 줄에, 다운로드 시작하고 몇 초 후에 노래를 듣기 시작하면, 끊김 없이 들을 수 있는지 출력한다. 그러한 시간이 여러개라면, 가장 빠른 것을 출력한다. www.acmicpc.net 2. 풀이 생각보다 어렵더라..? 다운로드 하면서 음악 재생시간을 누적해오고.. 어느 순간에 음악을 재생시키면.. 모든 다운로드 시간을 커버하면서 음악이 연속으로 흐를수 있게 할려면.. 다운로드가 언제 끝나는지 알아야하는데.. 이게 가능한가?? 리스트를 구성하면서 미리 더해서 남은 시간을 구해놓기도 하고.. 그리디의 기본인 정렬을 해서 짧은 시간부터 다운로드 해나가야하나? 생각은 했는데 정해진 순서대로 다운받아야하기 때문에.. 정렬은 할 수 ..
1. 문제1 23758번: 중앙값 제거 (acmicpc.net) 23758번: 중앙값 제거 $N$개의 자연수 $a_1$, $a_2$, $...$, $a_N$이 주어진다. 0을 좋아하는 amel은 $N$개의 수 중 0이 등장할 때까지 다음 연산을 반복하려고 한다. 중앙값을 2로 나누고 나머지는 버린다. 중앙값은 $N$개의 수 www.acmicpc.net 2. 풀이 어떤 정수를 2로 나누고 나머지를 버리는 과정을 반복할때, 언제 처음으로 0이 될 수 있을까? 1) 결국에 ? > ? > ? > ... ? > 1 > 0 이 되는 과정을 거친다. 즉 반드시 1에서만 0이 될 수 있다. 즉 "중앙값을 2로 나누고 나머지를 버리는 과정"을 계속 수행할때, 반드시 중앙값이 1이 되어야하고, 여기서 1번 더 수행하면 0..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
