GOOD DAY TO CODE: 6월 2017

2017년 6월 28일 수요일

알고리즘 트레이닝 [책]

국내 서적으로는 구종만 님의 알고리즘 문제해결 전략이 많이 추천이 되고, 해외 서적으로는 Competitive Programming 이 많이 추천되어서 사서 보기 시작했습니다. 물론, 번역판이 있어서....

원서: Competitive Programming: The New Lower Bound of Programming Contests
혹은, Competitive Programming 3
(third edition 이다..)
Site: https://cpbook.net
UVa Online Judge 문제 모음: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=604

번역서: 알고리즘 트레이닝: 자료 구조, 알고리즘 문제 해결 핵심 노하우
(프로그래밍인사이트)

UVa Online Judge 문제를 풀면서 진행이 되는데,
백준님이 책을 출간하면 acmicpc.net 의 문제가 예제로 나오겠다는 생각이 들었네요..

< 목차 >
1장 도입
1.1 경진 프로그래밍
1.2 경진에 능숙해지기 위한 팁
1.2.1 1번 팁: 빠른 속도로 코딩하자!
1.2.2 2번 팁: 문제 유형을 빠르게 파악하자
1.2.3 3번 팁: 알고리즘 분석을 수행하자
1.2.4 4번 팁: 프로그래밍 언어에 능숙해지자
1.2.5 5번 팁: 코드를 테스트하는 기술에 능숙해지자
1.2.6 6번 팁: 연습하고 또 연습하자
1.2.7 7번 팁: (ICPC를 위한) 팀워크
1.3 첫걸음 떼기: 쉬운 문제들
1.3.1 프로그래밍 대회 문제 뜯어보기
1.3.2 자주 사용되는 입출력 루틴
1.3.3 여정의 시작
1.4 애드혹 문제
1.5 별표가 없는 연습 문제에 대한 풀이
1.6 이 장을 마치며

2장 자료 구조와 라이브러리
2.1 개요 및 동기
2.2 내장된 라이브러리가 있는 선형 자료 구조
2.3 내장된 라이브러리가 있는 비선형 자료 구조
2.4 자체적인 라이브러리가 필요한 자료 구조
2.4.1 그래프
2.4.2 유니온-파인드 상호 배타적 집합
2.4.3 구간 트리
2.4.4 이진 인덱스 트리(펜윅 트리)
2.5 별표가 없는 연습 문제에 대한 풀이
2.6 이 장을 마치며

3장 문제 해결 패러다임
3.1 개요 및 동기
3.2 완전 탐색
3.2.1 반복적 완전 탐색
- UVa 725 - Division
BOJ ?
- UVa 441 - Lotto
BOJ, 6603번: 로또 (https://www.acmicpc.net/problem/6603)
- UVa 11565 - Simple Equations
BOJ 유사 문제, 4690번: 완전 세제곱 (https://www.acmicpc.net/problem/4690)
BOJ 유사 문제, 10448번:유레카 이론 (https://www.acmicpc.net/problem/10448)
- UVa 11571 - Simple Equations - Extreme!!
BOJ ?
- UVa 11742 - Social Constraints
BOJ ?
3.2.2 재귀적 완전 탐색
- UVa 750 - 8 Queens Chess Problem
- UVa 11195 - Another n-Queen Problem
BOJ 유사 문제, 9663번: N-Queen (https://www.acmicpc.net/problem/9663)
3.2.3 팁
- UVa 10360 - Rat Attack
BOJ, 7563번: Rat Attack (https://www.acmicpc.net/problem/7563)
BOJ 유사문제, 7573번: 고기잡이 (https://www.acmicpc.net/problem/7573)
3.3 분할 정복
3.3.1 이진 탐색의 흥미로운 활용 예
- UVa 11935 - Through the Desert
3.4 탐욕법
3.4.1 예제
3.5 DP
3.5.1 DP의 예
- UVa 11450 - Wedding Shopping
3.5.2 고전적인 예제 문제들
- UVa 507 - Jill Rides Again
- UVa 108 - Maximum Sum
3.5.3 고전적이지 않은 예제 문제
3.6 별표가 없는 연습 문제에 대한 풀이
3.7 이 장을 마치며

4장 그래프
4.1 개요 및 동기
4.2 그래프 탐색
4.2.1 깊이 우선 탐색
4.2.2 너비 우선 탐색
4.2.3 연결된 컴포넌트 구하기(무방향 그래프)
4.2.4 플러드 필(연결된 컴포넌트에 번호를 붙이거나 색칠하기)
4.2.5 위상 정렬(사이클 없는 방향 그래프)
4.2.6 이분 그래프 검사
4.2.7 DFS 스패닝 트리를 이용한 그래프의 간선 속성 검사
4.2.8 절단점 및 다리 구하기(무방향 그래프)
4.2.9 강결합 컴포넌트 구하기(방향 그래프)
4.3 최소 스패닝 트리
4.3.1 개요 및 동기
4.3.2 크루스칼 알고리즘
4.3.3 프림 알고리즘
4.3.4 몇 가지 활용 예
4.4 단일 시작점 최단 경로
4.4.1 개요 및 동기
4.4.2 가중치 없는 그래프에 대한 단일 시작점 최단 경로
4.4.3 가중치 그래프에 대한 단일 시작점 최단 경로
4.4.4 음수 사이클이 존재하는 그래프에 대한 단일 시작점 최단 경로
4.5 모든 쌍 최단 경로
4.5.1 개요 및 동기
4.5.2 플로이드-워셜의 DP 풀이에 대한 설명
4.5.3 몇 가지 활용 예
4.6 네트워크 유량
4.6.1 개요 및 동기
4.6.2 포드-풀커슨 기법
4.6.3 에드몬드-카프 알고리즘
4.6.4 유량 그래프 모델링 - 1부
4.6.5 몇 가지 활용 예
4.6.6 유량 그래프 모델링 - 2부
4.7 특수 그래프
4.7.1 사이클 없는 방향 그래프
4.7.2 트리
4.7.3 오일러 그래프
4.7.4 이분 그래프
4.8 별표가 없는 연습 문제에 대한 풀이
4.9 이 장을 마치며

5장 수학
5.1 개요 및 동기
5.2 애드혹 수학 문제
5.3 Java BigInteger 클래스
5.3.1 기본 기능
5.3.2 부가 기능
5.4 조합론
5.4.1 피보나치 수
5.4.2 이항 계수
5.4.3 카탈란 수
5.4.4 프로그래밍 대회에서의 조합론에 대한 첨언
5.5 정수론
5.5.1 소수
5.5.2 최대공약수와 최소공배수
5.5.3 팩토리얼
5.5.4 최적화된 나눗셈 시도 방법으로 소인수 구하기
5.5.5 소인수 다루기
5.5.6 소인수를 다루는 함수
5.5.7 수정된 체
5.5.8 모듈로 연산
5.5.9 확장된 유클리드 알고리즘: 선형 디오판토스 방정식 풀기
5.5.10 프로그래밍 대회에서의 정수론에 대한 첨언
5.6 확률론
5.7 사이클 찾기
5.7.1 효율적인 자료 구조를 사용하는 풀이
5.7.2 플로이드의 사이클 찾기 알고리즘
5.8 게임 이론
5.8.1 결정 트리
5.8.2 풀이가 빨라지도록 하기 위한 수학적 통찰
5.8.3 님 게임
5.9 별표가 없는 연습 문제에 대한 풀이
5.10 이 장을 마치며

6장 문자열 처리
6.1 개요 및 동기
6.2 기본적 문자열 처리 기법
6.3 애드혹 문자열 처리 문제
6.4 문자열 매칭
6.4.1 라이브러리를 이용한 풀이
6.4.2 KMP 알고리즘
6.4.3 2차원 격자에 대한 문자열 매칭
6.5 동적 계획법을 이용한 문자열 처리
6.5.1 문자열 정렬(편집 거리)
6.5.2 최장 공통 부분 수열
6.5.3 DP로 풀 수 있는 고전적이지 않은 문자열 처리 문제
6.6 접미사 트라이?트리?배열
6.6.1 접미사 트라이 및 그 활용 예
6.6.2 접미사 트리
6.6.3 접미사 트리의 활용 예
6.6.4 접미사 배열
6.6.5 접미사 배열의 활용 예
6.7 별표가 없는 연습 문제에 대한 풀이
6.8 이 장을 마치며

7장 (계산) 기하
7.1 개요 및 동기
7.2 기본적인 도형 및 라이브러리
7.2.1 0차원 도형: 점
7.2.2 1차원 도형: 직선
7.2.3 2차원 도형: 원
7.2.4 2차원 도형: 삼각형
7.2.5 2차원 도형: 사각형
7.3 다각형 관련 알고리즘 및 라이브러리
7.3.1 다각형의 표현법
7.3.2 다각형의 둘레
7.3.3 다각형의 면적
7.3.4 다각형이 볼록한지 검사하기
7.3.5 어떤 점이 다각형 내부에 있는지 검사하기
7.3.6 다각형을 직선으로 자르기
7.3.7 점들의 집합의 볼록 껍질 구하기
7.4 별표가 없는 연습 문제에 대한 풀이
7.5 이 장을 마치며

8장 고급 주제
8.1 개요 및 동기
8.2 고급 탐색 기법
8.2.1 비트마스크를 이용한 퇴각 검색
8.2.2 가지치기를 많이 사용한 퇴각 검색
8.2.3 BFS나 다익스트라 알고리즘을 이용한 상태 공간 탐색
8.2.4 중간 만남 기법(양방향 탐색)
8.2.5 정보 탐색(A*와 IDA*)
8.3 고급 DP 기법
8.3.1 비트마스크를 이용한 DP
8.3.2 자주 사용되는 (DP) 인자 모음
8.3.3 오프셋 기법을 이용하여 인자의 값이 음수인 경우 처리하기
8.3.4 MLE? 메모 테이블로 균형 잡힌 이진 검색 트리를 사용하는 것을 검토해보자
8.3.5 MLE?TLE? 더 나은 상태 표현법을 사용하자
8.3.6 MLE?TLE? 인자를 하나 생략하고 다른 인자들을 사용하여 이를 복구하자
8.4 문제 분해하기
8.4.1 두 가지 요소: 답에 대한 이진 탐색과 다른 요소
8.4.2 두 가지 요소: 정적인 1차원 구간 합?최소?최대 질의 사용하기
8.4.3 두 가지 요소: 그래프 사전 처리와 DP
8.4.4 두 가지 요소: 그래프를 다루는 문제
8.4.5 두 가지 요소: 수학을 다루는 문제
8.4.6 두 가지 요소: 완전 탐색과 기하
8.4.7 두 가지 요소: 효율적인 자료 구조 사용하기
8.4.8 세 가지 요소
8.5 별표가 없는 연습 문제에 대한 풀이
8.6 이 장을 마치며

9장 희귀한 주제
9.1 개요 및 동기
9.2 2-SAT 문제
9.3 미술관 문제
9.4 바이토닉 여행하는 외판원 문제
9.5 괄호 짝 맞추기
9.6 중국인 우편배달부 문제
9.7 가장 가까운 쌍 문제
9.8 디닉 알고리즘
9.9 공식 및 정리
9.10 가우스 소거법 알고리즘
9.11 그래프 매칭
9.12 대원 거리
9.13 홉크로프트-카프 알고리즘
9.14 독립적이거나 간선이 상호 배타적인 경로
9.15 반전 인덱스
9.16 조세푸스 문제
9.17 나이트의 이동
9.18 코사라주 알고리즘
9.19 최소 공통 조상
9.20 (홀수 크기의) 마방진 만들기
9.21 행렬 곱셈 순서 문제
9.22 행렬의 거듭제곱
9.23 최대 가중치 독립 집합
9.24 최소 비용 (최대) 유량
9.25 DAG에 대한 최소 경로 덮개
9.26 팬케이크 정렬
9.27 폴라드 로 정수 소인수분해 알고리즘
9.28 후위 표현식 계산하기 및 변환하기
9.29 로마 숫자
9.30 선택 문제
9.31 더 빠른 최단 경로 알고리즘
9.32 슬라이딩 윈도
9.33 선형 시간 정렬
9.34 희소 테이블 자료 구조
9.35 하노이 탑
9.36 이 장을 마치며

2017년 6월 17일 토요일

International Olympiad in Informatics (IOI) 문제 정리

International Olympiad in Informatics (IOI) 문제는

Solutions/정답 코드: O
Testcase(TC)/Input, Output/입출력 데이터: O
BOJ: https://www.acmicpc.net/category/99
Link: https://ioinformatics.org/page/ioi-xxxx (xxxx 를 연도로..)

Test cases 와 Solutions to all problems 를 선택하시면 됩니다..

IOI 2017 (https://ioinformatics.org/page/ioi-2017)
IOI 2016 (https://ioinformatics.org/page/ioi-2016)
IOI 2015 (https://ioinformatics.org/page/ioi-2015)
IOI 2014 (https://ioinformatics.org/page/ioi-2014)
IOI 2013 (https://ioinformatics.org/page/ioi-2013)
IOI 2012 (https://ioinformatics.org/page/ioi-2012)
IOI 2011 ()
IOI 2010 ()
IOI 2009 ()
IOI 2008 ()
IOI 2007 ()
IOI 2006 ()
IOI 2005 ()
IOI 2004 ()
IOI 2003 ()
IOI 2002 ()
IOI 2001 ()
IOI 2000 ()
IOI 1999 ()
IOI 1998 ()
IOI 1997 ()
IOI 1996 ()
IOI 1995 ()
IOI 1994 ()

2017년 6월 5일 월요일

Mid-Atlantic Regional 문제 정리

Mid-Atlantic Regional 는

Solutions/정답 코드: △
Testcase(TC)/Input, Output/입출력 데이터: △
BOJ: https://www.acmicpc.net/category/38
LlNK1: http://midatl.fireduck.com/archive/