BOJ 2887 행성 터널
www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제를 요약하자면 MST의 Cost를 구하는 문제이다. 단, 이 문제의 값 크기는 1 ≤ N ≤ 100,000 로 Naive하게 모든 행성들의 간선 거리를 구하려고 한다면 10^15가 되어 시간내에 풀지 못할 것이다. 이 문제에서 잘 봐야할 것은 터널을 연결할 때 드는 비용이다. "두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min..
라인 코딩 테스트 후기
1차 시험 120분에 총 4문제를 풀었다. 1,2,3,4 번 문제는 모두 구현 문제였다 1,2번은 쉽게 가져가는 문제였고, 3번 문제는 PS를 좀 해야 풀 수 있는 문제 4번은 PS보단 구현력이 더 필요한 문제였다. 특히 4번문제는 굳이 문제에서 보이는 자료구조를 사용하지 않고, parameter에서 naive하게 긁어와서 사용해도 충분히 풀 수 있는 문제였다. 언어는 c++, python을 이용했으며, 1,3번문제는 c++, 2,4번문제는 python을 이용했다 이번 코테에서는 1,2,4번을 풀고, 3번을 풀지 못했다. 3번은 그냥 구현문제인것 같은데 왜 쉽게 구현을 못하겠는지.... 이번 코테의 패착이라고 한다면, 1,2 번문제에서 시간을 줄이지 못했다는 것이다. 구현력이 좋은편도 아닌데 프로그래머스..
BOJ 13334 철로
www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 이 문제를 단순화 시킨다면 다음과 같이 정의할 수 있다. "시작점으로부터 거리 d (d > 0) 보다 가까이 있는 도착점의 개수 중 최대 값" 그래서 시작점, 도착점을 각각 벡터에 저장하여 정렬한 뒤, 2-pointer를 사용하여 문제를 해결하였다. 시작점으로부터 거리가 d 초과인 도착점이 나올 때 까지 도착점의 index를 하나씩 늘렸고, 그에 따라 loca..
