슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결합니다.이때 범위가 윈도우가 되고, 이동하는 것을 슬라이딩이라고 합니다.투 포인터 알고리즘과 비슷합니다. 12891번평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문..

투 포인터 알고리즘이란배열에서 두 개의 포인터(인덱스)를이용하여 원하는 결과를 얻는 이론입니다. 딱히 특별한 알고리즘보다는 코딩 테스트에서 사용할 수 있는 유용한 팁에 가깝습니다.2018번어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다.예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다.N을 입력받아 가지수를 출력하는 프로그램을 작성하시오.입력: 첫 줄에 정수 N이 주어진다.출력: 입..

구간 합합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다. 어떠한 배열이 있을 때, 그 배열 중 특정 범위에 있는 원소 값들의 합을 구간 합 알고리즘으로 쉽게 구할 수 있습니다.이 알고리즘을 활용하려면 합 배열을 알아야 합니다. 합 배열 S의 정의배열 A가 있을 때 합 배열 S는 다음과 같이 정의합니다.S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합 S[4]는 A[0]부터 A[4]까지 더한 합인거죠.합 배열은 기존의 배열을 전처리한 배열입니다. 이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소합니다. 위 그림에서 S[4] = A[..

배열과 리스트 중 어느 것을 선택해야 할까?배열과 리스트는코딩테스트에서 가장 많이 쓰는 자료구조입니다.둘의 성격으로 고려하여 어느 것을 사용할지 선택합니다. 데이터의 수가 변하지 않고, 데이터 접근이 많은 경우 인덱스를 통해 빠르게 값을 읽을 수 있는 배열을,데이터의 수가 정해져있지 않고, 데이터 삽입과 삭제가 많은 경우 리스트를 사용합니다. 11720번문제: N개의 숫자가 공백 없이 써있다. 이 숫자를 모두 합해 출력하는 프로그램을 작성하시오.입력: 1번재 줄에 숫자의 개수 N(1다음과 같은 입력에서는 그리 어렵지 않게 문제를 풀 수 있습니다.554321 5+4+3+2+1을 하면 됩니다. 그런데 이 문제에서 주의할 점은 N의 크기에 있습니다.만약 1번째 줄에 100이 있고, 2번째 줄의 수가 100개가..