알고리즘29 KMP 문자열 패턴 매칭 이 사이트에서 많이 공부를 했다. Python을 사용하다보면 문자열 처리에서 in을 단 한번이라도 써 본 사람이 많을 것이다. 물론 문자열 말고도 사용이 되지만 in의 역할은 문자열 내에 내가 찾고 싶은 패턴이 있는 문자열이 있는지 없는지에 대한 여부를 확인 가능하다고 한다. 그럼 다른 언어에서는? 이 궁금증을 해결하고자 찾아보니 KMP라는 좋은 알고리즘을 알게 되었다. (in도 이렇게 구현되지 않았을까...) 간단하게 KMP는 in 처럼 문자열 내에, 내가 찾고 싶은 문자열이 있느냐 없느냐를 판단하는 알고리즘이라 생각하면 된다. 시간 복잡도는 무려 O(n+m) // n은 비교 대상 문자열 길이, m은 찾고 싶은 문자열의 길이... 그럼 이 KMP가 과연 빠른가를 브루트 포스랑 비교해보.. 2023. 6. 10. [Baekjoon - 22862] 가장 긴 짝수 연속한 부분 수열 (large) with Python 주저리 주저리 투 포인터 문제 중 대표적인 문제 중 하나라고 생각한다. 이런 유형의 문제는 꼭 풀어봐야 생각하는게, 만약 코테에 이런 문제가 나올 시 이것이 투포인터 인지 아닌지 애매해서 못 풀수도 있을 거 같다라는 생각을 든다. 다들 알다시피 투 포인터는 대충 두 점을 같은 위치에서 시작하느냐 or 양 끝으로 시작하느냐의 문제가 대부분인 듯 하다. 난 개인적으로 같은 위치에서 시작을 하는 경우는 이제 특정 조건에 만족하는 길이를 구할때의 문제에 적용하고, 양 끝은 이제 양 끝에서 부터 접근해서 풀면 쉬울것 같다(?) 라고 판단시에 푸는 듯 한다. 문제 해결 이 문제는 k개의 원소를 지워 가장 긴 짝수 의 수열을 만드는 것이다. 그럼 당연하게도... 지우는 원소는 뭐가 되겠는가 => 홀수다 그래서 이 문.. 2023. 4. 25. 23032 - 서프라이즈~ with Python 주저리 주저리 맞춘 사람 43명 안에 든 행복이 든다? 문제는 두 그룹을 만들고, 그 그룹들의 무게 합의 차가 제일 작게한다. 대신 그룹원들은 서로 번호가 연속되어야한다... 고민이 많이 필요한 문제였다. 문제 해결 일단 이 문제에선 중요한 것은 그룹을 만들고, 그 들의 스테이크의 합의 차가 제일 작게 만들어야 한다. 따라서 그룹을 만드는 것이 제일 중요하다 볼 수 있다. 생각해보자 그룹을 만드는데 겨우 2그룹만 만들것이다. 그럼 간단하게 중간을 기준으로 삼아 그룹을 나누면 된다. 즉 mid값으로 시작해 1~n까지 돌면서 mid의 왼쪽과 오른쪽으로 그룹을 나누어 주면 된다. 여기서 중요한 점이 누적합 개념이다. 만약 그냥 저 그룹만 나누고 sum이런 것을 이용해 합을 구하면 시간 초과이다. (당연히도) .. 2023. 3. 30. 17609 - 회문 with Python 주저리 주저리 이 문제를 보자마자 그대로 문자를 뒤집어서 계산하는 것은 안 될까 싶었다. 하지만 유사 회문 덕에 모든 문자열을 탐색해야 함으로 O(n**2)이 걸릴 거라 생각하고 한번 짜봤는데, 역시 시간 초과... 당연히 다른 접근으로 접근해보자 문제 해결 회문을 탐색하는 방법으로는 그냥 맨 앞과 맨 뒤에 포인터를 두고 만약 두개의 포인터가 가리키는 문자가 서로 같으면 한 칸씩 움직이는 아주 간단한 방법이 존재한다. 다만 여기서는 유사 회문이 존재한다. 따라서 그냥 만약 다르다! 그러면 왼쪽과 오른쪽 둘 중 한 곳만 움직이게 해서 그 다음을 체크하면 될 것이다. 한번 코드로 직접 보면 더 이해가 쉽게 간다. 코드 import sys input = sys.stdin.readline t = int(inpu.. 2023. 3. 30. 이전 1 2 3 4 ··· 8 다음 728x90
