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 쓰는게 제일 무난한 듯...

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

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

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) 의 경우에 여러 입력값 중에 물고기의 최대값은 얼마 안 된다는 것을 보고, 좌표 기준이 아닌 물고기 기준으로 검색해 보면 되는 것을 알아내면 금방 푸는 문제... 입력값을 잘 보자....

INTRODUCTION TO ALGORITHMS [책]

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

• 영문 PDF: bayanbox.ir/view/4177858657730907268/introduction-to-algorithms-3rd-edition.pdf

• 위키: https://ko.wikipedia.org/wiki/Introduction_to_Algorithms

• MIT OpenCourseWare(6.006, Fall 2011): https://www.youtube.com/watch?v=HtSuA80QTyo&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb
• 수업계획서: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/Syllabus/
• 이 강의는 구글이 원하는 소프트웨어 엔지니어가 갖춰야 하는 기술들에 대한 내용 중에 알고리즘 항목에 소개까지 하는 강의
• https://codingsec.net/2016/07/skills-companies-like-google-expect-software-engineers/
• 6 번. Understand data structures and algorithms 에 보면 언급되어 있다
• MIT OpenCourseWare 의 수강 순서
• 6.006 (Undergraduate) => 6.046J (Undergraduate) => 6.854J (Graduate)
• Code: https://github.com/gzc/CLRS

영문과 번역본의 목차를 비교해 보니 영문은 졸업생(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장. 다항식과 FFT	30 Polynomials and the FFT
30.1 다항식의 표현	30.1 Representing polynomials
30.2 DFT와 FFT	30.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