codedoc

문제분류 및 정리 본문

정리

문제분류 및 정리

quince; 2016. 2. 7. 22:43

161015



시간복잡도 계산

koi 트리분할 문제

n*(1/n+2/n+...) -> nlgn


<팁>

좌표압축

1. pair & sort & unique

2. map

3. x*n+i

4방향탐색

- fx[], fy[]


iostream 사용 팁

ios::sync_with_stdio(false); 이거쓰면 빨라짐

endl은 '\n'보다 느리다 '\n' 사용추천


getchar가 scanf보다 더 빠름


<ad hoc>

2873번: 롤러코스터 https://www.acmicpc.net/problem/2873

2136번: 개미 https://www.acmicpc.net/problem/2136


<kth_element / stable_sort / sort>

11004번: K번째 수 https://www.acmicpc.net/problem/11004


<링크드 리스트>

5397번: 키로거 https://www.acmicpc.net/problem/5397


<brute force, 완전 검색>

9663번: N-Queen https://www.acmicpc.net/problem/9663


<분할정복>

11729번: 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729

1992번: 쿼드트리 https://www.acmicpc.net/problem/1992

1493번: 박스 채우기 https://www.acmicpc.net/problem/1493


<포함과배제>

2893번: XOR 도형 https://www.acmicpc.net/problem/2893


<xor>

10736번: XOR삼형제 2 http://codedoc.tistory.com/697

10464번: XOR https://www.acmicpc.net/problem/10464


<DFS>

10891번: Cactus? Not cactus? https://www.acmicpc.net/problem/10891


<kmp>

4354번: 문자열 제곱 https://www.acmicpc.net/problem/4354


<정렬 비교 함수>

2385번: Secret Sharing https://www.acmicpc.net/problem/2385


<inchworm>

2003번: 수들의 합 2 https://www.acmicpc.net/problem/2003


<잉여 역수>

11401번: 이항 계수 3 https://www.acmicpc.net/problem/11401


<큰 수>

10757번: 큰 수 A+B https://www.acmicpc.net/problem/10757


<정수론>

최대공약수, 최소공배수

약수

소수

소인수


<수학적 귀납법>

2163번: 초콜릿 자르기 https://www.acmicpc.net/problem/2163


재배열부등식

1026번: 보물 https://www.acmicpc.net/problem/1026


최대부분

2670번: 연속부분최대곱 https://www.acmicpc.net/problem/2670


LIS구하기

(그리디적요소가 있다 - 연관성)

11053번: 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053

12738번: 가장 긴 증가하는 부분 수열 3 https://www.acmicpc.net/problem/12738

2568번: 전깃줄 - 2 https://www.acmicpc.net/problem/2568


bit에서 update와 quer를 바꿔쓴다는 것은 무엇을 의미할까?

1~i의 합과 i~n의 합 차이이다.


단절선

참고로 어떤 두 정점 사이에 간선이 2개 이상 존재하는 경우, 자기 자신에 연결된 경우, 소스를 조금 수정해야 한다.


나중에 보자

http://contest.usaco.org/TESTDATA/OPEN08.nabor.htm


<이분검색>

1920번: 수 찾기 https://www.acmicpc.net/problem/1920

5624번: 좋은 수 https://www.acmicpc.net/problem/5624


<정렬>

2170번: 선 긋기 https://www.acmicpc.net/problem/2170


<스택>

1918번: 후위표기식 https://www.acmicpc.net/problem/1918


<힙>

1927번: 최소 힙 https://www.acmicpc.net/problem/1927


<다이나믹, 동적계획법, DP의 기초>

2011번: 암호코드 https://www.acmicpc.net/problem/2011

1932번: 숫자삼각형 https://www.acmicpc.net/problem/1932

2156번: 포도주 시식 https://www.acmicpc.net/problem/2156

2133번: 타일 채우기 https://www.acmicpc.net/problem/2133

1915번: 가장 큰 정사각형 https://www.acmicpc.net/problem/1915

1699번: 제곱수의 합 https://www.acmicpc.net/problem/1699

1687번: 행렬 찾기 https://www.acmicpc.net/problem/1687


2854번: 문제 출제 https://www.acmicpc.net/problem/2854

11025번: 조세퍼스 문제 3 https://www.acmicpc.net/problem/11025

2673번: 교차하지 않는 원의 현들의 최대집합 https://www.acmicpc.net/problem/2673

2197번: 분해 반응 https://www.acmicpc.net/problem/2197

11985번: オレンジの出荷 https://www.acmicpc.net/problem/11985


제 1종 스털링 수열

1413번: 박스 안의 열쇠 https://www.acmicpc.net/problem/1413


완전 순열

10978번: 기숙사 재배정 https://www.acmicpc.net/problem/10978


<DP최적화>

knuth optimization:

ZOJ Breaking Strings http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1860

11001번: 김치 https://www.acmicpc.net/problem/11001


divide and conquer optimization:

E. Ciel and Gondolas http://codeforces.com/contest/321/problem/E


<비트연산>

2272번: 램프 https://www.acmicpc.net/problem/2272


<재귀호출의 의미>

1003번: 피보나치 함수 https://www.acmicpc.net/problem/1003

1914번: 하노이 탑 https://www.acmicpc.net/problem/1914


<prefix sum>

11441번: 합 구하기 https://www.acmicpc.net/problem/11441

10986번: 나머지 합 https://www.acmicpc.net/problem/10986

5541번: 釘 https://www.acmicpc.net/problem/5541


<이차원 누적합 구하기>

2167번: 2차원 배열의 합 https://www.acmicpc.net/problem/2167


<DAG의 특성>

1520번: 내리막 길 https://www.acmicpc.net/problem/1520

*1937번: 욕심쟁이 판다 https://www.acmicpc.net/problem/1937

2611번: 자동차경주 https://www.acmicpc.net/problem/2611


<knapsack문제>

2293번: 동전 1 https://www.acmicpc.net/problem/2293

2294번: 동전 2 https://www.acmicpc.net/problem/2294

JOI14_manju: http://oj.uz/problems/view/JOI14_manju

13137번: Exchange Problem https://www.acmicpc.net/problem/13137


Meet-in-the-middle:

1208번: 부분집합의 합 2 https://www.acmicpc.net/problem/1208

위키: https://en.wikipedia.org/wiki/Knapsack_problem#Meet-in-the-middle


<knapsack비슷?>

1226번: 국회 https://www.acmicpc.net/problem/1226


<최소신장트리>

1197번: 최소 스패닝 트리 https://www.acmicpc.net/problem/1197

1922번: 네트워크 연결 https://www.acmicpc.net/problem/1922

1185번: 유럽여행 https://www.acmicpc.net/problem/1185

10661번: Median Tree https://www.acmicpc.net/problem/10661


- 특별한 그래프 모양

<interval 그래프>

8030번: Intervals https://www.acmicpc.net/problem/8030

2543번: 초고속철도 https://www.acmicpc.net/problem/2543


<최대연속합 구하기>

1912번: 연속합 https://www.acmicpc.net/problem/1912


<LIS구하기>

1965번: 상자넣기 https://www.acmicpc.net/problem/1965

2631번: 줄세우기 https://www.acmicpc.net/problem/2631

2352번: 반도체 설계 https://www.acmicpc.net/problem/2352


<LCS구하기>

1958번: LCS 3 https://www.acmicpc.net/problem/1958


<그리디 기초>

11399번: ATM https://www.acmicpc.net/problem/11399

1931번: 회의실배정 https://www.acmicpc.net/problem/1931

2215번: 원형 네트워크 https://www.acmicpc.net/problem/2215

1202번: 보석 도둑 https://www.acmicpc.net/problem/1202

1700번: 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700

1781번: 컵라면 https://www.acmicpc.net/problem/1781

1201번: NMK https://www.acmicpc.net/problem/1201

2109번: 순회강연 https://www.acmicpc.net/problem/2109

1080번: 행렬 https://www.acmicpc.net/problem/1080

1826번: 연료 채우기 https://www.acmicpc.net/problem/1826


<그리디 심화>

1150번: 백업 https://www.acmicpc.net/problem/1150

5896번: Cow Coupons https://www.acmicpc.net/problem/5896


<파라매트릭 서치>

3487번: Copying Books https://www.acmicpc.net/problem/3487

2585번: 경비행기 https://www.acmicpc.net/problem/2585

1114번: 통나무 자르기 https://www.acmicpc.net/problem/1114


<bfs탐색>

6118번: Hide and Seek https://www.acmicpc.net/problem/6118

http://oj.uz/problems/view/APIO15_skyscraper


<flood fill>

1012번: 유기농 배추 https://www.acmicpc.net/problem/1012

2423번: 전구를 켜라 https://www.acmicpc.net/problem/2423

4963번: 섬의 개수 https://www.acmicpc.net/problem/4963

2665번: 미로만들기 https://www.acmicpc.net/problem/2665


<sqrt(n)까지만 보자>

6101번: 식당 https://www.acmicpc.net/problem/6101

6757번: 팰린드롬 진법 https://www.acmicpc.net/problem/6757


<조합의 기초>

10164번: 격자상의 경로 https://www.acmicpc.net/problem/10164

2225번: 합분해 https://www.acmicpc.net/problem/2225

1256번: 사전 https://www.acmicpc.net/problem/1256

5900번: Cow IDs https://www.acmicpc.net/problem/5900


<순서>

1722번: 순열의 순서 https://www.acmicpc.net/problem/1722

2201번: 이친수 찾기 https://www.acmicpc.net/problem/2201

2291번: Sequence https://www.acmicpc.net/problem/2291


<경우의 수>

1720번: 타일 코드 https://www.acmicpc.net/problem/1720


포여열거정리

6567번: Let it Bead https://www.acmicpc.net/problem/6567


<scc구하기>

4013번: ATM https://www.acmicpc.net/problem/4013


<최단거리구하기>

5551번: 쇼핑몰 https://www.acmicpc.net/problem/5551

2398번: 3인통화 https://www.acmicpc.net/problem/2398

1854번: k번째 최단경로 찾기 https://www.acmicpc.net/problem/1854

1162번: 도로포장 https://www.acmicpc.net/problem/1162


<플로이드>

1507번: 궁금한 민호 https://www.acmicpc.net/problem/1507

7577번: 탐사 https://www.acmicpc.net/problem/7577

10159번: 저울 https://www.acmicpc.net/problem/10159


<lca구하기>

11437번: LCA https://www.acmicpc.net/problem/11437

11438번: LCA 2 https://www.acmicpc.net/problem/11438

1761번: 정점들의 거리 https://www.acmicpc.net/problem/1761

3176번: 도로 네트워크 https://www.acmicpc.net/problem/3176

5916번: Grass Planting https://www.acmicpc.net/problem/5916



<유한 오토마타>

1013번: Contact https://www.acmicpc.net/problem/1013

10160번: 암호 https://www.acmicpc.net/problem/10160


<sparse테이블>

10868번: 최소값 https://www.acmicpc.net/problem/10868


<단절점/단절선>

11266번: 단절점 https://www.acmicpc.net/problem/11266

11400번: 단절선 https://www.acmicpc.net/problem/11400

10806번: https://www.acmicpc.net/problem/10806


<2-sat>

11277번: 2-SAT - 1 https://www.acmicpc.net/problem/11277

11278번: 2-SAT - 2 https://www.acmicpc.net/problem/11278

11280번: 2-SAT - 3 https://www.acmicpc.net/problem/11280

11281번: 2-SAT - 4 https://www.acmicpc.net/problem/11281


<이분 매칭>

1298번: 노트북의 주인을 찾아서 https://www.acmicpc.net/problem/1298

1017번: 소수 쌍 https://www.acmicpc.net/problem/1017

1671번: 상어의 저녁식사 https://www.acmicpc.net/problem/1671

2570번: 비숍2 https://www.acmicpc.net/problem/2570


<max flow / min cut>

6102번: Earthquake Damage 2 https://www.acmicpc.net/problem/6102


<비둘기집의 원리>

2261번: 가장 가까운 두 점 https://www.acmicpc.net/problem/2261


<데큐 / 슬라이드 최솟값 / monotone priority queue>

2905번: 홍준이와 울타리 https://www.acmicpc.net/problem/2905

10782번: Hacker https://www.acmicpc.net/problem/10782

1725번: 히스토그램 https://www.acmicpc.net/problem/1725


<세그먼트 트리>

7469번: K번째 숫자 https://www.acmicpc.net/problem/7469

2042번: 구간 합 구하기 https://www.acmicpc.net/problem/2042

JOI13_koala http://oj.uz/problems/view/JOI13_koala

JOI14_pinball http://oj.uz/problems/view/JOI14_pinball

2336번: 굉장한 학생 https://www.acmicpc.net/problem/2336

1849번: 순열 https://www.acmicpc.net/problem/1849


<bit>

2934번: LRH 식물 https://www.acmicpc.net/problem/2934

3990번: 화면 보호기 https://www.acmicpc.net/problem/3990

7585번: 공장 https://www.acmicpc.net/problem/7578

1517번: 버블 소트 https://www.acmicpc.net/problem/1517

3653번: 영화 수집 https://www.acmicpc.net/problem/3653


<기하>

5897번: Symmetry https://www.acmicpc.net/problem/5897


<plane sweeping>

7728번: Painting patter https://www.acmicpc.net/problem/7728

2185번: 직사각형의 합집합 https://www.acmicpc.net/problem/2185

2601번: 도서실카펫 https://www.acmicpc.net/problem/2601


<일차 변환 / 선형 변환>

2381번: 최대 거리 https://www.acmicpc.net/problem/2381

2888번: KRALJEVI https://www.acmicpc.net/problem/2888


<필승전략>

2826번: 수학 게임 https://www.acmicpc.net/problem/2862


<볼록껍질/컨벡스헐트릭 비슷>

2821번: 컨베이어 벨트 https://www.acmicpc.net/problem/2821


<트리순회>

2820번: 자동차 공장 https://www.acmicpc.net/problem/2820


<트리의 지름>

1967번: 트리의 지름 https://www.acmicpc.net/problem/1967

2970번: 두더지 https://www.acmicpc.net/problem/2970


<다른 트리문제>

1289번: 트리의 가중치 https://www.acmicpc.net/problem/1289


<생성함수>

1665번: 화물열차 https://www.acmicpc.net/problem/1665


<위상정렬>

1005번: ACM Craft https://www.acmicpc.net/problem/1005


<오일러서킷>

1199번: 오일러 회로 https://www.acmicpc.net/problem/1199

3204번: 커플 깨기 https://www.acmicpc.net/problem/3204


<tsp>

2098번: 외판원 순회 https://www.acmicpc.net/problem/2098

0 Comments
댓글쓰기 폼