본문 바로가기 메뉴 바로가기

weekly ps

  1. Beginner 커리큘럼
  2. Student 커리큘럼
  3. Expert 커리큘럼
  4. Master 커리큘럼
  5. 프로그래밍 대회
  • [C언어] 0. 개요
  • [C언어] 1.C언어 프로그램의 기본 구조
  • [C언어] 2.printf 함수와 이스케이프 시퀀스
  • [C언어] 3.이진수와 비트 단위
  • [C언어] 4.변수(1) (정수형 변수 int)
  • [C언어] 5.변수(2) (실수형 변수)
  • [C언어] 6.조건문 (if, else, else if, switch case)
  • [C언어] 7.변수 (3) (변수형 char)
  • [C언어] 8.반복문 (for, while, do while)
  • [C언어] 9.변수와 상수
  • [C언어] 10.다중 반복문
  • [C언어] 11.이진수와 비트연산자
  • [C언어] 12.배열
  • [C언어] 13.연산자 우선순위
  • [C언어] 14.문자열
  • [C언어] 15.형 변환
  • [C언어] 16.포인터
  • [C언어] 17.문자열 관련 함수
  • [C언어] 18.함수
  • [C언어] 19.구조체
  • 0. 시간복잡도
  • 1. 자료구조
  • 2. 스택
  • 3. 힙
  • 4. 유니온 파인드
  • 5. 스파스 테이블
  • 0. 시간복잡도
  • 1. 에라토스테네스의 체
  • 2. 검색
  • 3. 병합 정렬
  • 4. 유클리드 호제법
  • 5. 페르마의 소정리
  • 6. 동적 계획법
  • 7. 크루스칼 알고리즘
  • 8. 프림 알고리즘
  • 9. 오일러 피 함수
  • 10. 트리의 지름
  • 11. 컨벡스 헐 트릭
  • 12. 모스 알고리즘
  • 13. 모스 알고리즘 on 트리
  • 분류 전체보기 (83)
    • 커리큘럼 (4)
    • C, C++ (20)
    • 검색 ( Search ) (1)
    • 정렬 ( Sort ) (1)
    • 선형 자료구조 (2)
    • 동적 계획법( Dynamic Programming.. (2)
    • 정수론 ( Number Theory ) (4)
    • 그래프 ( Graph ) (4)
    • 그래프 - 트리 ( Tree ) (1)
    • 범위 쿼리 처리 ( Range Query ) (3)
    • 프로그래밍 대회 (1)
      • ACM-ICPC (1)
    • 문제 풀이 (36)
    • 기본 이론 (2)







  단계별로 프로그래밍 능력을 향상시키세요.


weekly ps



Beginner

프로그래밍을 처음 접하는 분들을 위한 커리큘럼입니다.

C언어를 배우고, 기본 문제들을 해결하면서 프로그래밍 세계에 입문합니다.



Student (공사중)

대학교 수업, 취업 코딩 테스트 등을 대비할 수 있는 커리큘럼입니다.

기본 자료구조 / 알고리즘에 대한 학습을 통해 프로그래머로서의 기본기를 갈고 닦습니다.



Expert (공사중)

각종 프로그래밍 대회와 코딩 테스트를 대비할 수 있는 커리큘럼입니다.

다양한 자료구조 / 알고리즘을 응용하여 어려운 문제들을 해결합니다.



Master (공사중)

프로그래밍 대회 상위 수상에 도전하기 위한 커리큘럼입니다.

심화 자료구조 / 알고리즘에 대해 학습합니다.
[BOJ 13518] 트리와 쿼리 9

풀이는 http://weeklyps.com/entry/%ED%8A%B8%EB%A6%AC%EC%97%90%EC%84%9C%EC%9D%98-%EB%AA%A8%EC%8A%A4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%99%9C%EC%9A%A9-Mos-algorithm-on-tree 이 곳에 서술 되어 있으므로, 상세한 사항은 아래의 소스로 대신한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979..

문제 풀이 2017. 11. 3. 01:56
모스 알고리즘 ( Mo's algorithm )

Table of Contents 개요쿼리 처리쿼리 정렬문제 1. 개요 https://www.acmicpc.net/problem/13547 먼저 위의 문제를 읽어주시길 바랍니다. 범위 쿼리를 처리하는 상황에서 가끔 이런 상황들이 있습니다. 배열 Array[1...N], 함수 Function, 범위 [L, R] 이 주어질 때Function(Array[L], Array[L+1], ..., Array[R]) 계산하는데, 배열에 저장된 값을 고치는 update 연산은 없는 상황입니다. 위의 문제가 그 예시이지요. 이런 상황을 만나면 Segment tree 나 Sparse table 로 접근하는 경우가 많습니다. 하지만 이 두 자료구조를 활용한 접근은 대체로, 온라인 처리가 아닌 배치 처리가 가능하다는 점을 사용하..

범위 쿼리 처리 ( Range Query ) 2017. 11. 2. 11:06
문의 rikang93@gmail.com | Blog is powered by Tistory / Designed by Tistory

티스토리툴바