https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 자체는 어렵지는 않다. DFS개념을 가지고 있다면 접근하는데는 큰 지장이 없다. 하지만 DFS에서 응용이 필요한데 이 부분에서 많이 헤맬 수 있다. 1차원적으로 생각해 2중배열에서의 DFS 코드를 짜고 제출해버리면 당연히 반례를 만나서 10%도 가지 못하고 틀렸다고 나온다. 다음 예시를 보자. n = 5 R R R B B G G B B B B B B R R B B R R R R R R..
Algorithms
https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다.www.acmicpc.net실버 1이라고 얕보다간 큰 코 다치는 문제이다. 본인은 이 문제를 보고 처음에는 Brute Force로 시도했지만 시간초과, 이후 DP로 시도해보려 했는데 예외가 발생해서 실패를 겪었다. 첫번째 풀이: 평범한 Brute Force(시간초과)#include #include #include using namespace std; int dist(string a, string b) { int cnt = 0; for (int i = 0; i < a.size(); i++) { if (a[i] != b[i])..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 동적계획법을 입문하기에 매우 좋다. 동적계획법(Dynamic Programming, DP)이라는 말은 도대체 뭘 설명하는지 알 수가 없지만 실상은 Memoization이라고 생각한다. DP에서 최적 부분 구조라는 특성이 있는데, 전체 구간의 계산 결과를 특정 구간들의 계산된 결과의 합으로 나타낼 수 있다는 것이다. Memoization은 이와 비슷한 말이지만 조금 다르다. Memoization은 Top-Down 또는 Bottom-Up 중 어떤 방식으로든지 이미 계산한 구간을 반복하여 계산하지 않도록 ..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 그림을 보자마자 DFS보다 Union Find가 먼저 떠올랐다. 문제를 풀었을 때도 DFS가 아니라 Union Find가 정석이라고 생각했다. 이 문제는 Union Find를 응용한 크루스칼 알고리즘을 한 번이라도 풀어본 사람이라면 DFS나 BFS를 쓰지 않고 쉽게 풀 수 있는 문제다. 크루스칼에서는 정점을 탐색하면서 사이클을 이루는지 판별하기 위해 Union Find를 쓴다. 먼저 이 문제를 DFS로..
https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 어떤 자연수 n까지의 소수를 모두 출력하라는 문제가 있을 때 일반적인 풀이 방법은 2부터 시작해서 그 수의 제곱근까지 mod 연산을 하여 소수 판별을 해주는 것이다. 이 작업은 √1+√2+√3+...+√n 의 횟수를 가지며 1+1+1+...+1 = n < √1+√2+√3+...+√n < n+n+n+...+n = n² 즉 O(N) 보다는 크지만 O(N^2) 보다는 작은 어딘가에 있을 것이다. 하지만 시간복잡도를 더 줄일..
