반응형 Computer Science84 [알고리즘/파이썬] 강한 연결 요소(Strongly Connected Component) 강한 연결 요소란? 강한 연결 요소(SCC)란 노드들이 서로 자유롭게 이동 가능한 모음집이다. 하나의 그래프에서 여러개의 SCC가 존재할 수 있고, 같은 SCC 내에서는 어느 두 노드를 선택하더라도 한 노드에서 다른 한 노드로 이동이 가능해야 한다. 강한 연결 요소(SCC) 예시 아래의 그래프에는 3개의 SCC가 존재한다. a, b가 같은 SCC에 존재한다. 이 말은, a에서 b로 이동이 가능하며 b에서 a로 이동이 가능하다는 뜻이다. b, f는 다른 SCC에 존재한다. b에서 f로 갈 수는 있지만 f에서 b로 갈 방법은 없다. 강한 연결 요소 특징 무향 그래프면 당연히 서로 왕래가 가능할 것이다. 유향 그래프, 즉 방향이 존재하는 간선으로 이루어진 그래프가 SCC를 갖게 된다. 시간복잡도 O(V+E)를.. 2022. 3. 28. [알고리즘/파이썬] 세그먼트 트리 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. 이전 1 2 3 4 5 6 7 ··· 14 다음 반응형
