본문 바로가기
반응형

자료구조

[알고리즘/파이썬] 자료구조 - 투 포인터(Two pointers) | 백준 2018번: 수들의 합 5
Algorithm 2023. 7. 22. [알고리즘/파이썬] 자료구조 - 투 포인터(Two pointers) | 백준 2018번: 수들의 합 5 투 포인터(Two Pointers) 알고리즘 - 정렬된 배열의 부분합 또는 개수 구하기 등의 문제를 해결하는 데 자주 사용되는 알고리즘이다. - 기본 아이디어는 배열의 시작과 끝에서 하나씩 시작해서, 조건에 따라 양쪽 방향으로 포인터를 이동해 문제해결한다. - 문제에서 배열에 대한 순서나 시작점이 중요하지 않다면 이 알고리즘을 사용해서 빠르게 문제를 해결할 수 있다. 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 문제 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다..
[알고리즘/파이썬] 자료구조 - 슬라이딩 윈도우(Sliding window) | 백준 12891번: DNA 비밀번호
Algorithm 2023. 7. 18. [알고리즘/파이썬] 자료구조 - 슬라이딩 윈도우(Sliding window) | 백준 12891번: DNA 비밀번호 슬라이딩 윈도우(Sliding window) - 연속된 구간에서 일정 크기의 윈도우(슬라이딩)를 이동하면서 문제를 해결하는 것 - 배열 또는 리스트 등 순차적으로 접근할 수 있는 데이터에서 사용 접근방법 1. 데이터에서 일정 크기의 구간(윈도우)을 선택 2. 구간의 초기합을 계산 3. 구간을 우측으로 이동시키며, 구간의 값을 추가하거나 제거 4. 이동되면서 구간 속 값들을 계속 합산하며, 반복되는 계산으로 결과를 도출 5. 이동범위가 오른쪽으로 끝에 닿으면 알고리즘 종료 12891번: DNA 비밀번호 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을..
[알고리즘/파이썬] 자료구조 - 구간 합(Sum of Segment), 부분 합(Partial Sum) | 백준 11659번: 구간 합 구하기 4
Algorithm 2023. 7. 16. [알고리즘/파이썬] 자료구조 - 구간 합(Sum of Segment), 부분 합(Partial Sum) | 백준 11659번: 구간 합 구하기 4 구간 합 : 합 배열을 이용해 시간복잡도를 더 줄이기위한 알고리즘 > [1, 2, 3, 4, 5] - 부분합은 1, 3, 6, 10, 15 - 1~3 구간합 : 6 (1+2+3) 2~4 구간합 : 9 (2+3+4) 3~5 구간합 : 12 (3+4+5) 합 배열 s[i] = A[0] + A[1] + A[2] + _ + A[i-1] + A[i] #A[0]부터 A[i]까지의 합 합 배열 공식 S[i] = S[i-1] + A[i] 구간 합 공식 S[j] - S[i-1] #i에서 j까지 구간 합 11659번: 구간 합 구하기 4 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 ..
[알고리즘/파이썬] 자료구조 - 배열과 리스트 | 11720번: 숫자의 합, 1546번: 평균
Algorithm 2023. 7. 14. [알고리즘/파이썬] 자료구조 - 배열과 리스트 | 11720번: 숫자의 합, 1546번: 평균 배열의 특징 : 배열은 메모리에 연속된 공간에 값이 채워져있는 형태의 자료구조 인덱스를 사용해 값에 바로 접근가능하다. (장점) 값을 삽입하거나 삭제하려면 해당 인덱스 주변값을 이동시켜야 한다. 배열의 크기는 한번 선언하면 크기를 변경할 수 없다. (단점) 리스트의 특징 : 리스트는 노드(값과 포인터를 묶음)를 포인터로 연결한 자료구조 인덱스가 없어 순서대로 값에 접근해야한다.-속도가 느리다. (단점) 포인터로 연결되어 있어 삽입삭제 속도가 빠르다. 리스트의 크기가 가변적이다. -선언할때 크기지정필요x (장점) ⚠ 파이썬에서는 배열과 리스트를 구분하지 않는다. ⚠ 파이썬의 '리스트'는 배열의 특징까지 모두 가지도록 구현됨. 위에서 언급한 (장점)만 가져왔다. 11720번: 숫자의 합 11720번: 숫자의..
반응형

티스토리툴바