코드 낙서장

1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 문제 확인 벡터의 특성과 벡터를 선택하는 조합 문제입니다. 풀이 문제에서 주의해야 할 점은 벡터의 합의 길이이므로 (0, 10), (0, -10) 벡터의 합은 (0, 0)이므로 길이는 0이 됩니다. 따라서 벡터의 합을 구할 때 단순히 sqrt((x1 - x2)^2 + (y1 - y2)^2)로 구하면 틀리게 됩니다. 전체 벡터 합을 구한 후 선택한 벡터들의 차를 이용하여 벡터의 합을 빠른 시간에 구할 수 있습니다. (x1, y1), (x2, y2) .....

9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 확인 다익스트라 알고리즘을 활용하는 문제입니다. 풀이 방법은 2가지가 있으며 두 방법 모두 비슷한 결과로 나옵니다. 1번의 다익스트라 알고리즘을 수행하면서 g-h 간선을 지나는 경우를 체크하는 방법 start-g + g-h + h-dest 혹은 start-h + h-g + g-dest 가 start-dest와 값이 같은지 확인하는 방법, 3번의 다익스트라 알고리즘을 수행 결과가 비슷한 이유는 기존 다익스트라 알고리즘 계산 시 dist, graph 배열..

문제 주소 : www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 문제 확인 문자열과 정렬을 이용해서 풀 수 있습니다. 풀이 입력받을 시 문자열 다음에는 공백 혹은 \0이 입력되고 이를 구분해서 풀 수 있습니다. fgets를 통해 한번에 문자열 집합을 입력받고 qsort 함수를 통해 정렬을 합니다. qsort 정렬 시 strcmp 함수를 통해 같은 굴에서 뻣어가는 굴일 경우 교차점 이전까지 문자가 모두 같기 때문에 사전 순서대로 정렬됨을 이용합니다..

문제 주소 : www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 문제 확인 브루트 포스 혹은 수학으로 풀 수 있는 문제입니다. 풀이 브루트 포스를 통해 ax + b 식을 구해 풀 수 있지만 느리므로 계산식을 이용해 풀었습니다. n = 1의 경우 뒤에 어떠한 숫자가 올 수 있으므로 A n = 2의 경우 x1 = x2 일 때 나올 수 있는 식은 y = x + 0, y = -x + 2 * x1로 2가지가 나옵니다. 하지만 x1 = x2 이므로 두 식의 결과는 항상 일정한 x1 값이 나오므로 x1을 출력합니다. 그 외의 경우는 나올 ..

문제 주소 : www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 문제 확인 위상 정렬 문제입니다. 위상 정렬이란 간단하게 말해서 사이클이 없는 방향 그래프에서 방향을 한쪽으로 몰아세우는 정렬 방법입니다. 자세한 설명은 다음 블로그에서 잘 해두었습니다. Topological Sort(위상 정렬) DAG에서 방향성을 거스르지 않게 정점들을 나열하는 알고리즘을 Topological sort(위상 정렬)이라 합니다. DAG란 Direc..