CS ﹒ Algorithm/Baekjoon
2022. 9. 12.
백준 java 문제풀이 (43) 12891 : DNA 비밀번호
주어진 문자열의 연속된 부분 문자열 중 조건에 만족하는 문자열의 개수를 찾는 문제다. 우선 출력값이 0인 예제는 보통 도움이 안되므로 2번 예제를 확인해보자. 음.. 끄덕끄덕.. 그렇게 푸는 문제군요. 이런 연속된 값도 그냥 투포인터로 풀어도 되겠지만 입력값의 최대값이 1,000,000이라고 한다. 더 효율적인 방법은 없을까? 그렇다면 당신은 슬라이딩 윈도우입니다. 슬라이딩 윈도우는 기본적으로 네트워크 패킷 교환에 사용되는 알고리즘이며, 그 외에도 여러가지 데이터 가공 목적으로 활용되는 알고리즘이다. 더 궁금하면 검색해보고.. 아무튼 구해야하는 값이 연속적이며, 크기가 일정하다면 문자열 뿐 아니라 구간합 구하기 같은 문제에도 활용할 수 있다. 처음 봤던 예제를 다시 한 번 보자. 전체 배열의 크기는 4,..
