기타4 (1)자료구조 ④ 슬라이딩 윈도우 *️⃣ 슬라이딩 윈도우 2개의 포인터로 범위를 지정한 다음, 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결합니다. 투포인터 알고리즘과 매우 비슷하고 원리도 간단한 편입니다. 1. DNA 비밀번호 문제 Q. 평소 문자열을 이용해 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA문자열은 모든 문자열에 등장하는 문자가 {'A','C','G''T'}인 문자열을 말한다. 예를 들어 "ACKA" 는 DNA 문자열이 아니지만, "ACCA"는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA문자열을 만들고 만들어진 DNA 문자열의 부분 문자열을 비밀번호로 사용하기로 마음 먹었다. 하지만 민호는 이 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA.. 2024. 4. 11. (1)자료구조 ③ 투 포인터 *️⃣ 투포인터 - 투 포인터는 2개의 포인터로 알고리즘의 시간복잡도를 최적화 한다. - 시간 인덱스와 종료 인덱스를 투포인터로 지정하여 문제에 접근하는 방식 1. 연속된 자연수의 합 구하기 문제 Q. 어떠한 자연수 N은 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1≤N≤10,000,000)을 몇 개의 연속된 자연수는 N이어야 한다. 예를 들어 15을 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5이다. 반면, 10을 나타내는 방법은 10, 1+2+3+4이다. N을 입력받아 연속된 자연수의 합으로 나타내는 가짓수를 출력하는 프로그램을 작성하시오. [입력] [출력] 1번째 줄에 정수 N (1≤N ≤10,000,000)이 주어진다. 입력된 자연수 N을 연속된 자연.. 2024. 4. 10. (1)자료구조 ② 구간합 1. 구간 합 구하기1 문제 Q. 수 N개가 주어졌을 때 i번째 수에서 j번째 수까지의 합을 구하는 프로그램을 작성하시오. [입력] [출력] 1번째 줄에 숫자의 개수 N (1≤N ≤100,000) 합을 구해야 하는 횟수 (1≤M ≤100,000) 총 M개의 줄에 입력으로 주어진 i번째 수에서 j번째 수까지의 합을 출력한다. 2번째 줄에 N개 수가 주어진다. (각 수는 1,000보다 작거나 같은 자연수다.) 3번째 줄부터는 M개의 줄에 합을 구해야 하는 구간 i와 j가 주어진다. 풀이방법 1. N개의 수를 입력받은 동시에 합배열 생성 * 합배열 >>>> S[i] = S[i-1] + A[i] 2. i~j 가 주어지면 구간합을 구하는 공식으로 정답 출력 * 구간합 >>> S[j] - S[i-1] 코드 순서 1.. 2024. 4. 9. (1)자료구조 ① 배열과 리스트 1. 숫자의 합 구하기 문제 Q. N개의 숫자가 공백 없이 써 있다. 이 숫자를 합해 출력하는 프로그램을 작성하시오. [입력] [출력] 1번째 줄에 숫자의 개수 N (1≤N ≤100), 2번째 줄에 숫자 N개가 공백 없이 주어진다. 입력으로 주어진 숫자 N개의 합을 출력한다. 풀이방법 1. numbers = '10987654321' 2. numbers -> 정수형으로 변환 3. 결과값에 더하여 누적 코드 순서 1. n값 받기 2. numbers 변수에 list 함수를 이용하여 숫자를 한 자리씩 나누어 받기 3. sum 변수 선언 4. for numbers 탐색 : sum 변수에서 numbers에 있는 각 자리수를 가져와 더하기 5. sum 출력 정답 n = input() numbers = list(inp.. 2024. 4. 9. 이전 1 다음 LIST
