![]()
https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 겉보기에는 단순한 문제이다. 세 점이 이루는 두 선분의 방향이 시계인지 반시계인지를 알아내는 것은 딱 생각했을 때 다음과 같다. 점 A, B, C를 A(x1, y1), B(x2, y2), C(x3, y3) 라고 정의할 때, 점AB가 이루는 직선상에 점C가 있는 경우 0을 출력하면 된다. 그리고 직선상에 있지 않은 경우에는 둘로 나..
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 방문하지 않은 정점을 탐색하는 그래프 이론을 알고 있다면 접근자체는 쉬운 문제다. 파티에 속한 사람들을 연결리스트로 나타낸 이중배열과 각 사람이 속한 파티를 연결리스트로 나타낸 이중배열을 만들었다. 굳이 각 사람에 대한 이중배열을 또 만든 이유는 어떤 사람이 어떤 파티에 있는지를 찾는 데에 필요한 시간을 줄이기 위해서이다. 진실을 알고 있는 사람부터 dfs로 탐색하여 그 사람이 속한 파티를 전체 파티에서 제..
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제는 DP 유형임을 깨닫고 코드를 적어 제출하기 까지 시간은 얼마 안 걸렸지만 반례를 넘기지 못해서 1시간을 초과해버렸다. 뱀과 사다리 게임은 보드게임 중 하나라고 소개돼있다. 1번 칸부터 100번 칸까지 주사위를 굴려서 1~6칸씩 이동하는데 사다리를 만나면 사다리를 타고 여러 칸을 건너뛰지만 뱀을 만나면 뱀을 타고 여러 칸을 다시 돌아온다. 주..
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..
![]()
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) 보다는 작은 어딘가에 있을 것이다. 하지만 시간복잡도를 더 줄일..
