joseph0528 코딩 블로그

문제를 풀기에 앞서, 문제에 대한 설명 하겠다. 이 문제는 n과 k가 주어지고 이후 n 줄에 걸쳐 점의 좌표가 주어진다.이때 n개중 k개를 제거해 n-k 개의 점에 대해 직선 y=ax+b에 대해 y좌표 차이가 최소가 되게 하는 거리를 구하는 문제다.즉 n-k개의 점을 고르고 다양한 y=ax+b를 그려보면서 거리 차이가 최소가 되게 하는 y=ax+b를 찾고, 그때의 거리를 구하라는 문제다. 위 그림은 예제를 좌표평면에 나타낸 것이다. 4개의 예제 중 k = 0 일 때를 알아보자.k = 0 은 모든 점에 대해 거리가 가장 가까운 점을 찾는 것이다.이때 답은 그림에서 나타난 두 직선의 중앙에 있는 직선이 된다. 그럼 이제 문제를 해결해 보자.문제를 해결하기 위해선 크게 2가지를 해결해야 한다. 1. y = ..

이 문제는 내용 자체는 간단하다.트리가 처음에 주어지고, 쿼리로 2가지 입력 중 하나가 들어온다. 1번 쿼리는 트리의 정점 u에서 정점 v로 이동하는 경로에 u부터 0, 1, 2, 3 ... v에 k을 더하는 쿼리다.2번 쿼리는 각 정점에 대해 얼마의 값이 더해졌는가, 그 합을 구하는 쿼리이다. 위 트리는 예제에서 제공하는 트리다.예제에 나온대로 쿼리를 진행해보자. 일단, 맨처음 1 3 5 쿼리가 주어진다. 3에서부터 5까지 0부터 k까지를 더하는 것이다.1번 쿼리를 진행하면 다음과 같이 될 것이다. 2번 쿼리는 1 4 5 이다. 이도 맞찬가지로 진행해주면,다음과 같이 만들어진다는 것을 알 수 있다.4에서부터 시작했기 때문에, 4에는 0, 3에는 1, 2에는 2, 5에는 3을 더해준 모습이다. 다음 쿼..

이 문제는 "정보과학관"이라는 곳에서 출발해서 D번째에 다시 "정보과학관"에 있을 경우의 수를 구하는 문제다.D가 작다면 DP 를 이용해 풀어주면 되지만, 이 문제는 D가 10억까지 제공된다. 그럼 어떻게 풀 수 있을까? 우리는 여기서 모든 정점 간의 거리가 같음을 이용해야 한다. 위 그림은 문제에서 제공된 그림이고, 숫자는 각 정점에 부여해준 번호이다. 이제 위 그래프를 가지고 DP를 생각해 보자. DP [n][d] : n까지 오는데, d만큼 소요될 때 경우의 수 라고 DP를 정의할 수 있다. 그리고 n이 작으니 각 정점별로 DP 식을 정리해 보자. DP [1][d] = DP [2][d-1] + DP [3][d-1]DP [2][d] = DP [1][d-1] + DP [3][d-1] + DP [4][d..

문제를 요약하면 정의역 X={1,2,3 .... n} 에 대한 함수가 있고, c와 r 이 주어지면 f^c(r) 을 구하는 문제이다.f^c(r) 은 f 를 c번 합성하고 r 을넣은 함수다. 이와 같이 문제에 잘 나타나 있다.이때 1500번의 쿼리 안에 f^c(r) = c 를 만족하는 c와 r을 출력하면 된다. 이를 어떻게 풀 수 있을까? 여러 풀이가 존재하지만 이 문제는 놀랍게도 O(1) 에 해결할 수 있다. 함수 f를 생각하면 어떤 함수가 주어지더라도 c=n 이라면 최소 한번 이상 사이클이 돌게 될것이다.이는 자명하니 넘어가겠다. 이에 대해서는 몇가지 예제를 만들어보면 금방 알 수 있다. 그 이후 c=n과 임의의 r 을 제공했을 때 받은 값을 우리가 찾고자 하는 c라고 하자.그러면 우리는 이 값으로..

2024.06.01 자율주행차 제작 A to Z 시작 SW 미래채움에서 자율주행차 제작을 해보면서 자율주행차 만드는 거에 관심이 생겼다. 키트를 만드는건 재미없을 거 같아서 실제 사람이 탈 수 있는 자율주행차를 만들어보고자 한다.기획서도 만들었다.엄청나게 큰 프로젝트이기 때문에 혼자선 할 수 없다고 생각했고, 팀프로젝트로 진행해야겠다는 생각을 했다. 팀프로젝트라면 나뿐만 아니라 다른 친구들도 이점이 있어야 되니 각자가 원하는 방향성을 최대한 추구할 수 있게 프로젝트를 기획했다. 오늘 2024년 6월 1일부터 언제끝날지 모르겠지만 자율주행차 제작 일지?를 작성해보자.2024.06.04팀원 모집 오늘은 팀원을 뽑기 위해 신청 폼을 만들었다. 소프트웨어는 내가 한다고 해도, 하드웨어는 잘 모르니까 잘하는 친..

이 문제는 8 * 8 사이즈의 맵에서 특정 위치에 비료액을 뿌리는 자동 분무기 혹은 제초제를 뿌리는 자동 분무기가 위치해 있다.비료액 분무기는 해당 위치에서 십자가 모양으로 값을 1씩 더하고, 제초제 분무기는 해당 위치에서 십자가 모양으로 1씩 뺀다.예를 들어 위의 맵에서 X와 Y에 분무기가 있다고 할 때, X는 {a, b, c, d, e, f, g, h, i, j, k, l, m, n}에 영향을 미치고, Y는 {A, B, c, C, D, E, F, G, H, I, J, k, K, L}에 영향을 미친다.X가 비료액 분무기, Y가 제초제 분무기라고 한다면 문제에서 주어지면, 문제의 입력은 아래와 같이 주어지게 된다.이렇게 맵이 주어지면 분무기의 위치와 상태를 파악해서 맵을 출력하면 되는 문제다. 여기서 우..

이 문제는 노드 간 거리가 정해진 트리가 있을 때, 각 트리의 노드에서 거리 d만큼을 선택하거나 취소할 수 있는 쿼리가 주어진다.이때 쿼리마다 1번 노드에서 N번 노드까지 모두 선택되어 있는지를 쿼리마다 출력하는 문제이다.Q개의 쿼리에서 1 A B 가 들어오면 A에서 B만큼의 거리가 선택되는 것이고, 2 C 가 주어지면 C번째 시나리오(선택 쿼리)가 선택 해제가 된다.이 트리는 문제의 예제를 나타낸 것이다. 그 다음에 쿼리를 하나씩 진행해 보자.이렇게 계속 진행해 보자.5번 쿼리까지 진행한 모습이다. 아직 1에서 11까지 도달하지 못했기 때문에 NO를 출력한다.그럼 이제 6번 쿼리를 해보자. 6번 쿼리까지 진행하면 1부터 11까지 모두 선택이 가능하기 때문에 YES를 출력한다. 이후 7,8,9 번 쿼리..

이 문제를 요약하면 1번 점에서 N까지 갈 때 특정 시간 때에만 움직이며, 움직이지 않을 때는 숨을 수 있는 노드에 있어야 된다는 것이다.즉 자신을 숨길 수 없는 지점은 도로의 일부로서 취급해주고, 다익스트라를 진행해 주면 된다. N의 범위가 2000 이므로 O(N^2logN) 으로 모든 점간의 거리를 계산해 준다.그 뒤에 두 점간의 거리가 특정 시간대에 해당되는지를 봐주면 된다. 만약 거리가 움직일 수 없는 시간대를 포함하게 된다면, 그 도로는 N까지 도달할 수 없게 된다. 그러므로 두 점 사이 거리가 a(문제에서 주어진 입력) 보다 같거나 작은 경우만 저장해 준다.또 거리가 되더라도 자신을 숨길 수 없는, 즉 C_i = 1 인 지점의 경우 a이내에 도달하더라도 몸을 숨길 수 없기 때문에 새롭게 만들어..