분류 전체보기113 [자료구조] 세그먼트 트리(Segment Tree) 세그먼트 트리(Segment Tree)는 부분 합을 트리 구조에 저장해서, 값이 바뀔 수 있는 상황에서도 부분합을 빠르게 구할 수 있는 방법이다. 세그먼트 트리를 그려보면 이런 느낌이다. 위의 대괄호 안에 들어있는 숫자는 각 노드의 인덱스이고, 아래 큰 숫자는 부분합의 범위이다. 즉 루트 노드인 [0]에는 배열의 0~9번째 값들의 합이 저장되어 있고, [11] 노드에는 배열의 5~6번째 값들의 합이 저장되어 있는 식이다. 구현 | 1. init 배열의 초기 값을 세그먼트 트리에 처음 넣는 함수이다. 이때는 루트 노드 [0]부터 아래로 내려간다. 한 노드에 값을 채울 때는 자식 노드에 값을 먼저 채우고 그 뒤에 그 합을 쓰면 되는 것이다. 그런 식으로 말단 노드 (예를 들어, 6번째부터 6번째까지의 합 노.. 2020. 4. 14. [알고리즘] 강한 연결 요소(Strongly Connected Component) 강한 연결 요소(Strongly Connected Component, SCC)는 어떤 양방향 그래프 내에서 다음 조건을 만족하는 부분집합이다. 임의의 강한 연결 요소 내부의 모든 정점끼리는 서로 이어진 경로가 존재한다. 임의의 강한 연결 요소 내부의 정점과 외부의 정점끼리는 서로 이어진 경로가 존재하지 않는다. 즉 이는 어떤 한 정점에 대해 첫번째 조건을 만족하는 최대의 부분집합이라고 할 수 있다. 위 그래프에서 {A, B, C, E}, {D, G, H}, {F}, {I}가 강한 연결 요소이다. 어떤 그래프에서의 SCC를 찾는 알고리즘으로는 코사라주 알고리즘이 있다. 코사라주 알고리즘 | 코사라주 알고리즘은 DFS를 이용한 위상 정렬을 토대로 SCC를 찾는 알고리즘이다. 그래프와 역방향 그래프를 준비한다.. 2020. 4. 13. [픽셀아트] 0410 동아리방 선을 좀 더 명확하게 쓰는 연습을 했다. 찍을 때는 긴가민가 했는데, 완성본을 보고 나니 확실히 깔끔하다. 테이블 위에 올려진 유리 질감 표현하는 게 재밌었다. 테이블 다리 열심히 찍었는데 가려져서 아쉬움. 그림자 넣은 게 신의 한 수인 것 같다. 2020. 4. 12. [자료구조] 큐(Queue) 큐(Queue) | 한 쪽 끝에서는 자료를 넣고, 반대쪽 끝에서는 자료를 뺄 수 있는 선형 자료구조. FIFO(First-In-First-Out) | 먼저 들어간 자료가 먼저 나온다. 인큐(Enqueue) | 큐에 자료를 넣는 것. 디큐(Dequeue) | 큐에서 자료를 빼는 것. 사이즈(Size) | 큐의 크기. 큐에 들어 있는 자료 수. 프론트(Front) | 큐의 가장 앞에 있는 자료. 백(Back) | 큐의 가장 뒤에 있는 자료. 2019. 11. 11. [자료구조] 스택(Stack) 스택(Stack) | 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 자료구조. LIFO(Last-In-First-Out) | 먼저 들어간 자료가 나중에 나온다. 푸시(Push) | 스택에 자료를 넣는 것. 팝(Pop) | 스택에서 자료를 빼는 것. 사이즈(Size) | 스택의 크기. 스택에 들어 있는 자료 수. 탑(Top) | 스택의 가장 위에 있는 자료. (접근 가능한 자료.) 2019. 11. 3. 이전 1 ··· 7 8 9 10 다음
tokki
