원당컴퓨터학원

정의 스택은 top 이라고 하는 한쪽 위치에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트 입니다. 후입선출(Last In First Out : LIFO) 의 특징을 가지고 있습니다. 스택에 원소 삽입 및 삭제 top 위치는 다음 데이터를 넣을 수 있는 위치를 가르킨다. push() 에서 top의 위치에 데이터를 입력 후 다음 데이터를 넣을 수 있는 위치로 이동한다. pop() 에서는 top의 위치를 이전의 위치로 먼저 이동 후에 그 위치의 값을 반환한다. 스택의 ADT(추상데이터타입) structure Stack objects: 0개 이상의 원소를 가진 유한 순서 리스트 functions: 모든 stack∈ Stack, item∈ element, max_stack_size∈ positi..

SCC(Strongly Connected Components) 란 SCC 알고리즘은 방향 그래프에서 그래프의 모든 정점들 간에 양방향으로 경로가 존재하면 강하게 연결 되었다고 하는데 이렇게 연결된 부분그래프를 찾는 알고리즘이다. 위의 그래프에서 a,b,e / f,g / c,d,h 와 같이 3개의 그룹을 찾는 알고리즘 SCC가 되기 위한 조건 1. 같은 SCC 내의 임의의 두정점 A,B 사이의 경로가 항상 존재한다. 2. 서로 다른 SCC에서 뽑은 임의의 두 점 A,B 사이의 경로 A->B로 가는 경로와 B->A로 가는 경로는 동시에 존재할 수 없다.(SCC끼리는 사이클이 존재하지 않는다.) SCC 알고리즘 - 코세라주 알고리즘 1978년 코사라주가ㅏ 설명하고 1981년 미샤 샤리르가 출판. 두번의 깊이 ..

LCA(Lowest Common Ancestor) 란? LCA 란 최소 공통 조상을 찾는 알고리즘 - 두 정점 u,v 에서 가장 가까운 공통조상을 찾는 과정을 말한다. LCA(Lowest Common Ancestor) 구현 방법 위의 그래프에서 LCA((4,8)=1 이 됩니다. 가장 단순한 방법은 한번에 하나씩 자신의 조상을 찾아 올라가는 방법입니다. 4의 조상은 2,8의 조상은 7,2의 조상은 1,7의 조상은 3,1의 조상은 루트이므로 대기,3의 조상은 1 에서 순차적으로 하나씩 찾아가다가 누군가가 먼저 지나간 자리에 도착하면 그곳이 공통조상이 됩니다. 하지만 이 알고리즘은 최대 O(N) 의 시간이 걸립니다. https://www.acmicpc.net/problem/11438 11438번: LCA 2 ..

Topological Sorting(위상정렬) 이란 위상정렬은 유향그래프(방향그래프)의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명하는 예는 선수과목의 구조를 예로 들 수 있다. 특정 수강과목에 선수과목이 있다면 그 선수과목을 먼저 수강해야 하므로 특정과목을 수강해야 할때 위상정렬을 통해 올바른 수강순서를 찾아 낼 수 있다. Topological Sorting(위상정렬) 조건 사이클이 없는 유향 그래프 Topological Sorting(위상정렬) 특징 모든 정점을 일렬로 나열 정점 x에서 정점 y로 가는 간선이 있다면 x는 반드시 y보다 앞에 위치한다. 일반적으로 임의의 유향 그래프에 대해 복수의 위상 순서가 존재한다. Topological Sorting(위..

트라이의 정의를 위키백과의 내용을 인용하면 다음과 같습니다. 트라이(trie)는 컴퓨터 과학에서 탐색트리의 일종이다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 트라이(trie) 란? 문자열 변수를 비교하는데는 최악의 경우 문자열의 길이에 비례하는 시간이 걸릴 수 있습니다. N개의 원소를 갖는 이진검색 트리에서 원하는 원소를 찾으려면 O(lgN)번의 비교만으로 찾을 수 있습니다. 이러한 이진 검색 트리에서 착안을 하여 고안된 문자열 특화 자료구조가 바로 트라이(trie) 로 집합 내에서 원소를 찾는 작업을 O(M) 시간만에 할 수 있습니다. 그렇다면 어떻게 가능한지 다음을 살펴 보시죠~ 그림은 문자열집합 S={"A","to","tea","ted","ten","inn"} 을 저장하..

비트연산 활용 1. 모든 부분집합 순회하기 예) 피자의 토핑 종류가 (페페로니,소시지,양파) 라고 하면 {페페로니},{페페로니,소시지},{페페로니,소시지,양파},{소시지},{소시지,양파},{양파} 와 같이 하나 하나 열거하는 경우 다음과 같이 처리 1 2 3 4 5 6 for (int subset = pizza; subset; subset = ((subset-1) & pizza)) { //subset 은 pizza의 부분 집합 } Colored by Color Scripter cs 2. 비트마스크를 활용하여 에라토스테네스 체 치기(체치는 메모리를 적게 잡기 때문에 훨씬 더 많은 양의 체를 칠 수 있다.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22..

비트마스크란? 컴퓨터는 모든 정수형변수를 이진수로 표현합니다. 이 때 이진수의 한 자리를 비트(bit)라고 부릅니다. 비트는 0 또는 1의 값을 가지며 컴퓨터가 표현하는 모든 자료의 근간이 됩니다. 이러한 이진수표현을 자료구조로 사용하는 기법을 비트마스크(BitMask) 라고 부릅니다. 비트마스크는 엄밀하게 ㅏ료구조라고 할 수는 없지만 굉장히 유용하게 사용 됩니다. 비트마스크를 왜 사용하는가? 1. 더 빠른 수행시간 : 비트마스크 연산은 O(1)으로 구현이 됨, 따라서 여러번 수행하는 경우에는 작은 최적화로 속도 향상을 가져올 수 있음 2. 더 간결한 코드 : 반복문 없으 한줄에 사용하므로 짧은 코드를 작성 3. 더 작은 메모리 사용 : 32비트형 정수형 자료형에 32개의 0/1 형태의 정보를 저장 비트..

2차원 펜윅트리를 구현하기 전에 1차원펜윅트리를 먼저 이해합니다.(https://wondangcom.tistory.com/1582) 1차원 배열이 여러개 인 행렬 구조의 데이터가 업데이트가 많은 경우 사용하게 되는데 1차원펜윅트리를 여러 개 이어 붙인 것이 2차원 펜윅트리라고 생각할 수 있다. 2차원의 구간합을 구하기 위해서 2개의 인덱스(y,x)가 필요하다. 그림으로 이해하면 다음과 같다. (x1,y1) ~ (x2,y2) 의 구간합을 구하는 방법을 살펴 보면 먼저 (0,0)~(x2,y2) 의 구간합을 구한다. 이때 녹색과 하늘색 부분인 (0,0) ~ (x1,y2), (0,0)~(x2,y1) 구역을 빼 주면 되는 것을 확인 할 수 있다. 이렇게 두개의 구간 합을 빼 주면 (0,0) ~ (x1,y1) 구간..

펜윅트리(Fenwick Tree)란? - Binary Indexed Tree 라고도 하며 이진수를 이용하여 위치값을 표현하는 세그먼트 트리와 유사한 트리 펜윅트리(Fenwick Tree) 의 개념 10진수 수를 이진수로 표현해 보면 다음과 같다. 3 = 00000011 4 = 00000100 5 = 00000101 6 = 00000110 8 = 00001000 9 = 00001001 10 = 00001010 11 = 00001011 12 = 00001100 16 = 00010000 여기서 이진수의 마지막 1의 위치를 확인하면 다음과 같다. 3= 왼쪽에서 첫번째 자리 (10진수의 값으로 1) 4= 왼쪽에서 3번째 자리 (10진수의 값으로 4) 5= 왼쪽에서 첫번째 자리(10진수의 값으로 1) ... 16 ..

세그먼트 트리(Segment Tree)란? - 주어진 쿼리에 대해 빠르게 응답하기 위해 만들어진 자료구조 - 구간 중에 Max,Min,Sum(최대,최소,구간의 합) 등을 빠르게 갱신할 수 있는 자료구조 세그먼트 트리(Segment Tree) 구현 목적 배열의 데이터 수 : 10개 배열의 데이터 A[10] = {1,2,3,4,5,6,7,8,9,10} 목적 : 구간에 대한 합 예) 4번째 부터 6번째까지의(배열의 3번지부터 5번지까지의) 구간합은? 15 이러한 구간합을 구하는 가장 간단한 방법은 합을 미리 구해 놓고 1번째 부터 6번째의 합 21 에서 1번째 부터 3번째의 합 6을 빼면 15가 나온다. 1 2 3 4 5 6 7 8 9 10 1 3 6 10 15 21 28 36 45 55 하지만 각 데이터가 ..