반응형 Computer Science77 [알고리즘/파이썬] 세그먼트 트리 segment tree 세그먼트 트리는 언제 쓰나? 배열과 같은 자료형에서 특정 구간에 속한 원소들의 연산(합, 최솟값, 최댓값 등)을 알아볼 때 선형 탐색보다 좀 더 효율적인 탐색이 가능하다. 그럼 누적합이랑 비슷한거 아닌가? 합만을 알려주는 누적합보다 좀 더 폭넓게 활용이 가능하다. 특히 특정 데이터가 변경되었을 때 누적합은 O(N)으로 누적합 데이터를 업데이트해줘야 하지만, 세그먼트는 O(logN)에 특정 데이터 변경을 반영할 수 있다. 사실 알고리즘보다는 자료구조에 가깝다. 대략 아래의 그림처럼, 어떤 배열이 존재할 때 세그먼트 트리는 그 배열의 특정 구간에 대한 정보를 추가로 담고 있게 된다. 이해가 안되면 그림을 보면 된다. 아래의 그림에서 트리의 루트 노드는 0~8번 데이터를 포함하는 정보를 담고 있다. 예를 들어.. 2022. 3. 27. [알고리즘] 부분합, 누적합 (Prefix Sum) 쉽게 알아보기(파이썬) 부분합, 누적합이라고 불리우는 배열의 일부 구간에 대한 합을 매우 빠르게 구할 수 있게 해주는 스킬이다. N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 부분합을 이용하면 모든 부분합을 O(1)에 바로바로 구할 수 있다. 1차원 배열 - 직관적으로 매우 쉽게 이해가 가능하다. arr을 순차 탐색하면서 sum 배열을 만들어주면 된다. sum[i]에는 arr[0] + arr[1] + ... + arr[i-1]의 정보가 담겨 있다고 생각하면 된다. - 활용법 arr의 i항부터 j항까지의 합을 S(i, j)라고 하자. 이때 S(i, j) = sum[j+1] - sum[i]이다. 2차원 배열 - 2차원 배열도 같은 방식이다. arr을 순차 탐색하면서 sum.. 2022. 3. 25. [컴퓨터 구조] 슈퍼 스칼라 프로세서 * 지난 번에 공부했던 명령어 파이프라인 내용과 이어진다. 그 내용을 숙지하고 있어야 이번 글 내용이 이해가 될 것이다. 보러 가기: https://yiyj1030.tistory.com/485?category=514953 [컴퓨터 구조] 명령어 파이프라이닝 명령어 파이프라이닝이란? 명령어 파이프라이닝은 한 번에 하나의 명령어만 실행하는 것이 아니라 하나의 명령어가 실행되는 도중에 다른 명령어의 실행을 시작함으로써 동시에 명령어 여러 yiyj1030.tistory.com 슈퍼스칼라 프로세서란? 슈퍼스칼라 프로세서는 여러 파이프라인을 이용하여 독립적으로 명령어를 실행함으로써 명령어를 프로그램 순서와 다르게 실행할 수 있다. 슈퍼스칼라 프로세서의 기본 구조에서는 파이프라인으로 구현된 여러 개의 기능 유닛이 명.. 2022. 3. 22. [컴퓨터 구조] 명령어 파이프라이닝 명령어 파이프라이닝이란? 명령어 파이프라이닝은 한 번에 하나의 명령어만 실행하는 것이 아니라 하나의 명령어가 실행되는 도중에 다른 명령어의 실행을 시작함으로써 동시에 명령어 여러 개를 실행하는 방식이다. 2단계 명령어 파이프라인 명령어를 실행하는 하드웨어를 인출 단계와 실행 단계라는 독립적인 파이프라인 모듈로 분리하여 수행하는 방법이다. 명령어 처리 속도가 2배 정도 향상되지만 만약 두 단계의 처리 시간이 동일하지 않다면 속도가 2배 향상을 기대할 수 없다. 즉 각 명령어의 인출 단계와 실행 단계의 처리 시간이 동일해야 파이프라인으로 인한 성능 향상을 기대할 수 있다. 단계의 처리 시간이 동일하지 않은 경우 속도가 향상되지 않는 문제를 극복하려면 파이프라인의 단계 수를 증가시켜서 각 단계의 처리 시간을 .. 2022. 3. 22. [ 컴퓨터 구조] 캐시 기억 장치와 적중률, 평균 기억 장치 접근 시간 계산법 캐시 기억 장치란? CPU가 데이터를 처리할 때 저장 장치는 필요한 데이터를 인출하여 제공하거나 처리된 데이터를 저장한다. 그러나 CPU는 저장 장치에 비해 고속이라 저장 장치가 읽기/쓰기 동작을 하는 동안 기다려야 한다. 이 문제를 해결하기 위해 CPU의 처리 속도만큼 빠른 고속 저장 장치인 레지스터를 CPU 내의 저장 장치로 사용한다. 한편 주기억 장치(main memory)는 외부의 보조 기억 장치(HDD, SSD 등)에 저장된 프로그램을 저장하는 장치로, CPU와 보조 기억 장치 간의 속도 차이를 극복하기 위해 사용한다. 주기억 장치는 보조 기억 장치보다 빠르지만 CPU에 비하면 매우 느리다. 이에 주기억 장치보다 빠른 저장 장치로 캐시 기억 장치가 등장하게 되었다. 캐시 기억 장치는 수행할 명령.. 2022. 3. 22. [주제 별 탐구] 프로세스와 스레드 [프로세스의 의미] 프로세스가 가지는 의미는 다양하지만 일반적인 프로세스의 정의는 '실행중인 프로그램'이다. 프로그램은 컴파일한 코드와 초기화 전역변수, 문자열과 문자열 상수 등 정적인 데이터를 포함하는 정적 개체다. 디스크에 있던 프로그램이 메모리에 적재되어 운영체제의 제어를 받는 상태가 되면 프로세스가 되는 것이다. 이는 자신만의 메모리 공간이 있다는 뜻이 된다. 프로세스는 프로그램 카운터나 레지스터처럼 현재 어떤 자원을 사용하는지 관련 정보가 들어 있는 동적 개체이다. [프로세스의 일반적인 메모리 구조] - 스택 데이터를 일시적으로 저장하는 영역. 지역 변수에 사용하고, 변수가 범위 밖으로 이동하면 공간을 해제한다. 호출한 함수의 반환 주소, 반환 값, 매개변수 등에 사용하고, 함수를 호출할 수록 .. 2022. 2. 21. 이전 1 2 3 4 5 6 ··· 13 다음 반응형
