Hello

: )

2016년 7월 24일 일요일

cin 과 scanf 에 대해서


10815번: 숫자 카드(https://www.acmicpc.net/problem/10815) 문제는 500,000 개의 입력값이 주어는지는 문제로 cin / cout 을 쓰면 시간 초과가 발생한다.

해결책으로는 scanf / printf 를 사용하거나, cin / cout 전에 std::ios::sync_with_stdio(false) 를 미리 호출해주어서 시간 지연을 막는 방법이 있다.

입출력 방법별 시간 측정값 참고자료: https://algospot.com/forum/read/2496/


하지만, 이 방법이 만능이 될 수는 없는 듯

API Reference: http://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio 에 보면 아래와 같이 언급되어 있다.

If the synchronization is turned off, the C++ standard streams are allowed to buffer their I/O independently, which may be considerably faster in some cases.


상황에 따라서 다를 수 있다는 얘기..

같은 문제는 아니지만, 유사 질문에 대한 백준님의 comments 를 보자
위치: https://www.acmicpc.net/board/view/1294


결론은 scanf / printf 쓰는게 제일 무난한 듯...

2016년 7월 23일 토요일

알고리즘 문제 해석 능력에 관해서

당연한 얘기겠지만, 문제를 읽고 해석하는 능력이 문제를 쉽고 빨리 풀 수 있는 중요한 요인인 것 같다

7569 번: 토마토 (https://www.acmicpc.net/problem/7569) 의 경우 토마토가 익는 과정을 BFS 를 이용한 가장 먼 곳을 찾으면 되는 것임을 깨닫는 과정에 많은 시간 낭비가 있었다

6359 번: 만취한 상범(https://www.acmicpc.net/problem/6359) 은 1 인 경우 +1 을 하면서 반대로 문을 설정하고, 2 인 경우 +2 하면서 반대로 문을 설정하고, 3 인 경우 +3 하면서 반대로 문을 설정하고, n 인 경우 +n 하면서 반대로 문을 설정하는 단순한 조건의 문제이다. 하지만, 문제 설명으로는 무슨 문제인지 이해자체를 못해서 결과를 보고 이해를 했는데, 문제 설명을 계산 문제로 전환할 수 있는 능력이 중요하다가 다시 한 번 느끼게 된 문제...

3055 번: 탈출 (https://www.acmicpc.net/problem/3055) 은 물(*)이 여러 개일 수 있다는 생각을 처음에 할 수 있어야 한다. TC 에서도 마지막에만 있고, 심지어 1 개로 가정하고 먼저 나오는 물을 시작점을 처리하면 예상 결과값이 나온다. 문제를 잘 읽어야 한다는 것을 또 생각하게 해준 문제..

7573 번: 고기잡이 (https://www.acmicpc.net/problem/7573) 의 경우에 여러 입력값 중에 물고기의 최대값은 얼마 안 된다는 것을 보고, 좌표 기준이 아닌 물고기 기준으로 검색해 보면 되는 것을 알아내면 금방 푸는 문제... 입력값을 잘 보자....

2016년 7월 4일 월요일

INTRODUCTION TO ALGORITHMS [책]


알고리즘 공부를 위한 책을 추천해 달라는 글에 자주 보여서 어떤 책인지 살펴봤는데, 이걸 다 볼 엄두는 안나고 필요한 내용을 참고하는 정도로 쓰면 좋을 듯 하다





영문과 번역본의 목차를 비교해 보니 영문은 졸업생(Graduate)들을 위한 내용은 ★ 표기가 있는데, 번역판은 따로 표시가 없다 0_0;;

I 기초I Foundations
개요Introduction
1장. 알고리즘의 역할1 The Role of Algorithms in Computing
1.1 알고리즘1.1 Algorithms
1.2 기술로서의 알고리즘1.2 Algorithms as a technology
2장. 시작하기2 Getting Started
2.1 삽입 정렬2.1 Insertion sort
2.2 알고리즘의 분석2.2 Analyzing algorithms
2.3 알고리즘의 설계2.3 Designing algorithms
3장. 함수의 증가3 Growth of Functions
3.1 점근적 표기3.1 Asymptotic notation
3.2 표준 표기법과 흔히 사용되는 함수3.2 Standard notations and common functions
4장. 분할정복4 Divide-and-Conquer
4.1 최대 부분배열 문제4.1 The maximum-subarray problem
4.2 행렬 곱셈을 위한 스트라센 알고리즘4.2 Strassen’s algorithm for matrix multiplication
4.3 점화식을 풀기 위한 치환법4.3 The substitution method for solving recurrences
4.4 점화식을 풀기 위한 재귀 트리 방법4.4 The recursion-tree method for solving recurrences
4.5 점화식을 풀기 위한 마스터방법4.5 The master method for solving recurrences
4.6 마스터 정리의 증명★ 4.6 Proof of the master theorem
5장. 확률적 분석과 랜덤화된 알고리즘5 Probabilistic Analysis and Randomized Algorithms
5.1 고용 문제5.1 The hiring problem
5.2 지표 확률 변수5.2 Indicator random variables
5.3 랜덤화된 알고리즘5.3 Randomized algorithms
5.4 확률적 분석과 지표 확률 변수의 기타 활용★ 5.4 Probabilistic analysis and further uses of indicator random variables
II 정렬과 순서 통계량II Sorting and Order Statistics
개요Introduction
6장. 힙 정렬6 Heapsort
6.1 힙6.1 Heaps
6.2 힙 특성 유지하기6.2 Maintaining the heap property
6.3 힙 만들기6.3 Building a heap
6.4 힙 정렬 알고리즘6.4 The heapsort algorithm
6.5 우선순위 큐6.5 Priority queues
7장. 퀵 정렬7 Quicksort
7.1 퀵 정렬7.1 Description of quicksort
7.2 퀵 정렬의 성능7.2 Performance of quicksort
7.3 랜덤화된 퀵 정렬7.3 A randomized version of quicksort
7.4 퀵 정렬 분석7.4 Analysis of quicksort
8장. 선형 시간 정렬8 Sorting in Linear Time
8.1 정렬의 하한8.1 Lower bounds for sorting
8.2 계수 정렬8.2 Counting sort
8.3 기수 정렬8.3 Radix sort
8.4 버킷 정렬8.4 Bucket sort
9장. 중앙값과 순서 통계량9 Medians and Order Statistics
9.1 최솟값과 최댓값9.1 Minimum and maximum
9.2 선형적인 평균 수행시간에 선택하기9.2 Selection in expected linear time
9.3 최악의 경우선형 시간에 선택하기9.3 Selection in worst-case linear time
III 자료구조III Data Structures
개요Introduction
10장. 기본 자료구조10 Elementary Data Structures
10.1 스택과 큐10.1 Stacks and queues
10.2 연결 리스트10.2 Linked lists
10.3 포인터와 객체 구현하기10.3 Implementing pointers and objects
10.4 루트 있는 트리 표현하기10.4 Representing rooted trees
11장. 해시 테이블11 Hash Tables
11.1 직접 주소 테이블11.1 Direct-address tables
11.2 해시 테이블11.2 Hash tables
11.3 해시 함수11.3 Hash functions
11.4 개방 주소화 방법11.4 Open addressing
11.5 완전 해싱★ 11.5 Perfect hashing
12장. 이진 검색 트리12 Binary Search Trees
12.1 이진 검색 트리의 개념12.1 What is a binary search tree?
12.2 이진 검색 트리에 대한 질의12.2 Querying a binary search tree
12.3 삽입과 삭제12.3 Insertion and deletion
12.4 임의로 만들어진 이진 검색 트리★ 12.4 Randomly built binary search trees
13장. 레드블랙 트리13 Red-Black Trees
13.1 레드블랙 트리의 특성13.1 Properties of red-black trees
13.2 회전13.2 Rotations
13.3 삽입13.3 Insertion
13.4 삭제13.4 Deletion
14장. 자료구조의 확장14 Augmenting Data Structures
14.1 동적 순서 통계량14.1 Dynamic order statistics
14.2 자료구조 확장 기법14.2 How to augment a data structure
14.3 구간 트리14.3 Interval trees
IV 고급 설계 및 분석 기법IV Advanced Design and Analysis Techniques
개요Introduction
15장. 동적 프로그래밍15 Dynamic Programming
15.1 막대 자르기15.1 Rod cutting
15.2 행렬-체인 곱셈15.2 Matrix-chain multiplication
15.3 동적 프로그래밍의 요소15.3 Elements of dynamic programming
15.4 최장 공통 부분 시퀀스15.4 Longest common subsequence
15.5 최적 이진검색 트리15.5 Optimal binary search trees
16장. 그리디 알고리즘16 Greedy Algorithms
16.1 활동 선택 문제16.1 An activity-selection problem
16.2 그리디 방법의 요소들16.2 Elements of the greedy strategy
16.3 허프만 코드16.3 Huffman codes
16.4 매트로이드와 그리디 방법★ 16.4 Matroids and greedy methods
16.5 매트로이드로 작업 일정짜기 문제★ 16.5 A task-scheduling problem as a matroid
17장. 분할상환 분석17 Amortized Analysis
17.1 총계 분석17.1 Aggregate analysis
17.2 결산 방법17.2 The accounting method
17.3 잠재 비용 방법17.3 The potential method
17.4 동적 테이블17.4 Dynamic tables
V 고급 자료 구조V Advanced Data Structures
개요Introduction
18장. B-트리18 B-Trees
18.1 B-트리의 개념18.1 Definition of B-trees
18.2 B-트리의 기본연산18.2 Basic operations on B-trees
18.3 B-트리에서 키삭제하기18.3 Deleting a key from a B-tree
19장. 피보나치 힙19 Fibonacci Heaps
19.1 피보나치 힙의 구조19.1 Structure of Fibonacci heaps
19.2 병합 가능한 힙 연산19.2 Mergeable-heap operations
19.3 키 감소시키기와 노드 삭제하기19.3 Decreasing a key and deleting a node
19.4 최대 차수의 한계 정하기19.4 Bounding the maximum degree
20장. 반 엠데 보아스 트리20 van Emde Boas Trees
20.1 기본 방법20.1 Preliminary approaches
20.2 재귀 구조20.2 A recursive structure
20.3 반 엠데 보아스트리20.3 The van Emde Boas tree
21장 서로 소 집합의 자료구조21 Data Structures for Disjoint Sets
21.1 서로 소 집합의 연산21.1 Disjoint-set operations
21.2 서로 소 집합의 연결 리스트 표현21.2 Linked-list representation of disjoint sets
21.3 서로 소 집합 포리스트21.3 Disjoint-set forests
21.4 경로 압축을 이용한 순위에 의한 합병의 분석★ 21.4 Analysis of union by rank with path compression
VI 그래프 알고리즘VI Graph Algorithms
개요Introduction
22장. 기본 그래프 알고리즘22 Elementary Graph Algorithms
22.1 그래프의 표현22.1 Representations of graphs
22.2 너비 우선 검색22.2 Breadth-first search
22.3 깊이 우선 검색22.3 Depth-first search
22.4 위상 정렬22.4 Topological sort
22.5 강한 연결 요소22.5 Strongly connected components
23장. 최소 신장 트리23 Minimum Spanning Trees
23.1 최소 신장 트리의 확장23.1 Growing a minimum spanning tree
23.2 크루스칼 알고리즘과 프림 알고리즘23.2 The algorithms of Kruskal and Prim
24장. 단일 출발지 최단 경로24 Single-Source Shortest Paths
24.1 벨만-포드 알고리즘24.1 The Bellman-Ford algorithm
24.2 방향 비순환 그래프에서의 단일 출발점 최단 경로24.2 Single-source shortest paths in directed acyclic graphs
24.3 다익스트라 알고리즘24.3 Dijkstra’s algorithm
24.4 차이 제약 조건과 최단 경로24.4 Difference constraints and shortest paths
24.5 최단 경로특성의 증명24.5 Proofs of shortest-paths properties
25장. 모든 쌍의 최단 경로25 All-Pairs Shortest Paths
25.1 최단 경로와 행렬 곱셈25.1 Shortest paths and matrix multiplication
25.2 플로이드-워샬 알고리즘25.2 The Floyd-Warshall algorithm
25.3 희소 그래프에 대한 존슨 알고리즘25.3 Johnson’s algorithm for sparse graphs
26장. 최대 플로우26 Maximum Flow
26.1 플로우 네트워크26.1 Flow networks
26.2 포드-풀커슨 방법26.2 The Ford-Fulkerson method
26.3 최대 이분 매칭26.3 Maximum bipartite matching
26.4 푸시-재명명 알고리즘★ 26.4 Push-relabel algorithms
26.5 재명명후-앞보내기 알고리즘★ 26.5 The relabel-to-front algorithm
VII 알고리즘 분야의 중요한 토픽VII Selected Topics
개요Introduction
27장 멀티스레드 알고리즘27 Multithreaded Algorithms
27.1 동적 멀티스레딩의 기본27.1 The basics of dynamic multithreading
27.2 멀티스레드 행렬의 곱셈27.2 Multithreaded matrix multiplication
27.3 멀티스레드 병합 정렬27.3 Multithreaded merge sort
28장. 행렬의 연산28 Matrix Operations
28.1 선형 연립방정식의 해28.1 Solving systems of linear equations
28.2 역행렬28.2 Inverting matrices
28.3 양으로 정의된 대칭 행렬과 최소-제곱 근사28.3 Symmetric positive-definite matrices and least-squares approximation
29장. 선형 계획법29 Linear Programming
29.1 정규형과 이완형29.1 Standard and slack forms
29.2 문제의 선형 계획법 구성29.2 Formulating problems as linear programs
29.3 심플렉스 알고리즘29.3 The simplex algorithm
29.4 쌍대성29.4 Duality
29.5 초기 가능한 기본해29.5 The initial basic feasible solution
30장. 다항식과 FFT30 Polynomials and the FFT
30.1 다항식의 표현30.1 Representing polynomials
30.2 DFT와 FFT30.2 The DFT and FFT
30.3 효율적인 FFT의 구현30.3 Efficient FFT implementations
31장. 정수론 알고리즘31 Number-Theoretic Algorithms
31.1 기초 정수론31.1 Elementary number-theoretic notions
31.2 최대공약수31.2 Greatest common divisor
31.3 모듈로 연산31.3 Modular arithmetic
31.4 모듈로 선형 방정식의 해31.4 Solving modular linear equations
31.5 중국인의 나머지 정리31.5 The Chinese remainder theorem
31.6 원소의 거듭제곱31.6 Powers of an element
31.7 RSA 공개키 암호 시스템31.7 The RSA public-key cryptosystem
31.8 소수 판정★ 31.8 Primality testing
31.9 정수의 인수분해★ 31.9 Integer factorization
32장. 스트링 매칭32 String Matching
32.1 단순 스트링 매칭 알고리즘32.1 The naive string-matching algorithm
32.2 라빈-카프 알고리즘32.2 The Rabin-Karp algorithm
32.3 유한 오토마타를 이용한 스트링 매칭32.3 String matching with finite automata
32.4 크누스-모리스-프랫 알고리즘★ 32.4 The Knuth-Morris-Pratt algorithm
33장. 계산 기하학33 Computational Geometry
33.1 선분의 특징33.1 Line-segment properties
33.2 선분의 교차성 결정33.2 Determining whether any pair of segments intersects
33.3 볼록 껍질의 발견33.3 Finding the convex hull
33.4 가장 가까운 점들의 쌍 구하기33.4 Finding the closest pair of points
34장. NP-완비성34 NP-Completeness
34.1 다항 시간34.1 Polynomial time
34.2 다항 시간 확인34.2 Polynomial-time verification
34.3 NP-완비성과 환원 가능성34.3 NP-completeness and reducibility
34.4 NP-완비성 증명34.4 NP-completeness proofs
34.5 NP-완비 문제들34.5 NP-complete problems
35장. 근사 알고리즘35 Approximation Algorithms
35.1 정점 덮개 문제35.1 The vertex-cover problem
35.2 순회 판매원 문제35.2 The traveling-salesman problem
35.3 집합 덮개 문제35.3 The set-covering problem
35.4 랜덤화와 선형 계획법35.4 Randomization and linear programming
35.5 부분 집합의 합 문제35.5 The subset-sum problem
VIII 부록 : 수학적 기초VIII Appendix: Mathematical Background
개요Introduction
부록 A. 합A Summations
A.1 덧셈 공식과 특성A.1 Summation formulas and properties
A.2 합의 한계A.2 Bounding summations
부록 B. 집합과 기타B Sets, Etc.
B.1 집합B.1 Sets
B.2 관계B.2 Relations
B.3 함수B.3 Functions
B.4 그래프B.4 Graphs
B.5 트리B.5 Trees
부록 C. 계산과 통계C Counting and Probability
C.1 계산C.1 Counting
C.2 확률C.2 Probability
C.3 이산 확률 변수C.3 Discrete random variables
C.4 기하 분포와 이항 분포C.4 The geometric and binomial distributions
C.5 이항 분포의 꼬리★ C.5 The tails of the binomial distribution
부록 D. 행렬D Matrices
D.1 행렬과 행렬 연산D.1 Matrices and matrix operations
D.2 행렬의 기본 특성D.2 Basic matrix properties
참고문헌Bibliography
찾아보기Index