반응형 Computer Science84 [알고리즘/파이썬] 최소 공통 조상(LCA) 알아보기(코드) Lowest Common Ancestor(LCA)는 트리 구조에서 특정한 두 노드의 공통 조상 중 가장 가까운 조상을 뜻한다. 희소 테이블을 공부한 적 있다면 매우 유사한 방식으로 진행된다. LCA풀이는 다음의 순서로 진행된다. 1. dfs로 모든 노드의 깊이, 부모를 체크한다. 여기서 부모는 바로 위 직속 부모를 말한다. 2. 위의 결과를 이용해서 모든 노드의 2**i번째 부모를 찾아 그 결과를 저장한다. 3. 두 노드가 주어지면 둘 중 더 깊은 노드를 두 노드의 깊이가 같아질 때까지 거슬러 올려보낸다. 4. 최상단 노드부터 내려오며 두 노드의 공통 부모를 찾는다. 문제로 바로 알아보자. https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수.. 2022. 4. 9. [알고리즘/파이썬] Sparse Table 희소 테이블 알아보기(코드) Sparse table의 역할 배열에 대한 다양한 구간 쿼리를 할 수 있다. 생성에는 O(NlogN)이지만, 구간 쿼리는 O(1) (또는 O(logN))에 수행할 수 있다. 구간 쿼리에 대한 알고리즘으로 세그먼트 트리가 있는데, 그 역할과 매우 유사하다. 참고로 세그먼트 트리는 O(NlogN)시간에 생성하고 쿼리 처리는 O(logN)에 가능하다. 차이점이라면 세그먼트 트리는 mutable(변경 가능)한 자료구조이지만 sparse table은 immutable(변경 불가능)한 자료구조이다. Sparse table의 원리 sparse table은 위의 그림과 같이 2차원 배열을 갖게 된다. 이때 열 갯수는 배열 길이가 N일때 [logN]을 해주면 된다. 테이블이 어떤 방식으로 구성되어 있는 지 알아보자. s.. 2022. 4. 9. [컴퓨터구조] 컴퓨터의 구성 컴퓨터 종류>1. personal computer(pc)2. server computers- high performance3. supercomputers-high-end scientific and engineering calculations4. embedded computers- hidden as components of systems- 스마트폰, 태블릿pc 컴퓨터 숫자 단위>2^10 bytes = 1 Kilobyte2^20 bytes = 1 Megabyte2^30 bytes = 1 Gigabyte2^40 bytes = 1 Terabyte2^50 bytes = 1 Petabyte High-level language : C코드Assembly language: textual representation of .. 2022. 4. 8. [데이터베이스] 인덱스 알아보기 인덱스는 where 절에서 사용해야 효과가 있다. 예를 들어 '책' 테이블의 '출판사', '제목', '작가'가 있다고 하자. 이때 인덱스는 '출판사'에 걸려 있다. 1) SELECT * FROM '책' WHERE '작가' = '짱구'; 2) SELECT '제목' FROM '책' WHERE '출판사' = '스타'; 위의 두 쿼리 중 인덱스의 효과를 받을 수 있는 쿼리는 2번뿐이다. 인덱스는 무조건 많다고 좋지 않다. 인덱스가 많아질수록 무조건 검색 속도 향상을 기대할 수 있는 것은 아니다. 인덱스는 데이터베이스의 메모리를 사용하여 테이블 형태로 저장되므로 인덱스의 개수와 메모리 사용량은 비례한다. 자주 조회하고 고유한 값 위주로 설정하는 것이 좋다. DML의 경우 UPDATE, DELETE에선 WHERE절.. 2022. 4. 7. [운영체제] 2단계 페이징 테이블 기법 알아보기 페이징 기법 일반적인 페이징 기법에서의 주소 변환은 아래 그림과 같다. 논리적 주소에서 p는 페이지번호, d는 페이지 오프셋을 의미한다. 하지만 페이징 기법은 물리적 메모리 낭비가 심하다는 단점을 가지고 있다. 32비트 주소 체계 = 2의 32승 = 4G의 주소 공간을 가진 프로그램 지원 가능 이때 총 필요 용량 = 4G * 1바이트 = 4GB 프로그램의 필요 용량 4GB 1개 페이지가 약 4KB일 때, 4GB / 4KB = 1M개의 페이지가 필요. 즉 페이지 테이블에는 1M개 엔트리가 필요. 엔트리 하나 당 4B를 차지한다면, 페이지 테이블의 용량은 4MB가 됨. 헉 4MB나?? => 페이지 테이블이 메모리의 상당 부분을 차지하게 된다. 그래서 2단계 페이징 테이블 기법이 고안되었다. 2단계 페이징 테.. 2022. 4. 1. [알고리즘/ 파이썬] KMP 알고리즘 알아보기 KMP 알고리즘(Knuth-Morris-Pratt algorithm)이란 문자열 검색을 매우 빠르게 해주는 알고리즘이다. 특정 패턴이 주어졌을 때 전체 문자열을 빠르게 검색하여 그 패턴이 어디에 등장하는 지 찾아준다. KMP 알고리즘을 이해하려면 파이 배열에 대해 알아야 한다. 파이 배열의 i번째 성분은, 문자열의 i번째까지의 부분 문자열에서 접두사, 접미사가 같아지는 최대 길이를 뜻한다. 파이 배열의 예시는 아래와 같다. KMP 알고리즘은 2단계에 걸쳐 실행된다. 1. 주어진 패턴에 대해 파이 배열 만들어내기 2. 파이 배열을 활용하여 패턴의 등장 위치를 빠르게 찾아내기 1. 파이 배열 만들기 파이 배열의 0번째 값은 무조건 0이 된다. 한글자 짜리 문자열에는 접두사, 접미사가 없기 때문이다. 파이 배.. 2022. 3. 29. 이전 1 2 3 4 5 6 ··· 14 다음 반응형
