joseph0528 코딩 블로그

1교시를 완전히 망쳐서 가채점 나오기 전까지 0점도 가능할 거같다라는 생각을 했었는데 생각보다 40점이라는 높은? 점수가 나왔고 2교시는 작년보다는 어려웠지만 그렇게 많이 어려운 정도는 또 아닌지라 200점을 받고 총 240점이라는 점수로 전체 6.309%, 일반고 2.299% 로 은상 2개를 받으면서 본선을 가게 되었다. import sys,math inf=math.inf input=sys.stdin.readline a,b=map(int,input().split()) l=[list(map(int,input().split()))for i in range(a)] t=[[0 for i in range(100)]for g in range(100)] for i in range(a): for g in range(..

문제에 쓰여있는 그대로 R를 루트노드라고 하고 LCA(U, V)를 구해주면 끝인 문제이다. 이 문제를 처음 봤을 때 LCA의 sparse table를 입력마다 갱신하는 방법이 바로 떠오르겠지만 그럴 경우 코드를 작성하지 않아도 안된다는 것을 알 수 있다. 그럼 어떻게 해야 할까 이 그림은 위 문제의 테스트케이스를 그래프로 나타낸 것이다. 이때 (U, V)에 대해 R의 위치는 1. R 이 LCA(U, V) 보다 위에 있을 때, 2. R 이 V -> LCA(U, V) 사이에 있는 노드와 연결되어 있을 때, 3. R 이 U -> LCA(U,V) 사이에 있는 노드와 연결되어있을 때, 4. R이 루트 노드를 거쳐 U, V를 가야 할 때 이렇게 총 4개가 나오게 된다. 그럼 처음부터 따져보자. 위 그림은 1번 경우..

이번 연도 글이 매우 뜸 했는데 현생을 열심히 살다 보니 글을 못 올리게 되었다. 글을 못 올리는 동안 여러 가지 활동을 했는데 처음으로 소개할 것은 한국 코드 페어이다. 방학 때부터 시작해 한국 코드 페어 해커톤 부분 본선에 들어서 11월에 킨텍스를 갔다 왔다. 해커톤 본선 대회에 참가해 시각장애인을 위한 편의점 메뉴 판별 프로그램이라는 것을 만들었고 최종적으로 대상(장관상)을 수상하게 되어 12월 말 수상 예정이다. 두 번째는 koi 다. 알고리즘 공부를 열심히 못했고 예선은 중등부 전국부분 은상, 지역 부분 동상으로 무난하게 합격을 하였지만 본선은 예선보다 더 어렵기 때문에 상만 받자는 생각으로 참가를 하였고 최종적으로 151점을 받아 동상 끝자락일 거라고 예상했지만 의외로 2번 문제를 못 푼 참가..

보호되어 있는 글입니다.

이 문제는 여러 가지 풀이 방법이 있지만 이 글에선 유니온 파인드(줄여서 유파)를 이용한 풀이를 사용하겠다. 이 문제를 간단히 요약하면 사용할 수 있는 정점이 주어지면 한 정점에서 다른 정점으로 갈 수 있는 모든 경우의 수를 구하라는 문제이다. 이때 n개의 정점들이 이어져있다고 해보자. n개의 정점들은 자신을 제외한 모든 정점에게 갈수 있다고 할 때 이 그룹에서 나올 수 있는 경우의 수는 n*(n-1)/2 개가 된다. 이 글에선 이걸 이용할 것이다. 일단 처음에 한 정점을 기준으로 번호를 다시 부여해준다.(이 글에선 1번 정점을 기준으로 했다.) 번호를 부여할때 자신의 부모 노드의 번호를 같이 저장한 뒤 입력을 받을 때 새로 부여된 자신의 번호와 부모의 번호를 함께 저장한다. 그 뒤 자신에게 부여된 번호..

문제를 간단하게 요약하면 처음부터 i를 증가하며 카운팅을 하는데 i번째 값이 i 라면 그 값을 지우고 카운팅을 1부터 다시 한다. 이렇게 계속 반복해서 값을 계속 지우는데 지워지는 값이 1부터 차례대로 지워지게 하는 크기가 K이 배열에서 n개의 인덱스가 주어지면 그 위치의 값을 출력하는 문제이다. K=5 일 때 [1, 3, 2, 5, 4] 이렇게 배열을 만들면 차례로 값을 지울 수 있다. 처음에는 i가 1이고 값도 1이므로 1을 지우고 3부터 다시 i=1을 시작해서 카운팅 해 나가면 2가 지워지고 계속 반복하게 되면 1, 2, 3, 4, 5 순서대로 지워지게 된다. 여기서 한가지 알 수 있는 사실은 i 번째 값이 지워졌다면 다음 값은 i+(i+1) = 2i+1 위치에 있어야 한다. 그러므로 1부터 K까지..

문제 설명이 이게 다인 문제 설명은 간단한 문제이다. 이 문제를 처음 볼 때 이상한 수학으로 풀어야 되는 건가 싶을 수 있지만 사실 세그를 사용해서 풀 수 있다. 일단 |p [i]-p [j]| 를 1번이라고 하고 |q [i]-q [j]| 를 2번이라고 하겠다. 이 문제는 1번과 2번 중 작은 값을 골라야 하기 때문에 1번이 작은 경우와 2번이 작은 경우 이렇게 2개로 나눌 수 있다. 1번이 작거나 같은 경우부터 생각해보자. 1번이 작거나 같을려면 (j = p[j] 일때 p[i] < p[j] 일때 p[i]-p[j]

(한별이가 나오는 몇 안 되는 희귀한 문제이다.) 이 문제는 한가지 관찰만 하면 쉽게 풀 수 있다. 그 관찰은 바로 많아도 3개의 용기만 있으면 꽉 찬 용기를 만들 수 있다는 것이다. 만약 a 용기에 0ml가 있고 b 용기에 1ml가 있고 총용량이 10ml 일 때 a와 b를 합치면 1+5=6ml가 된다. 그리고 c 용기에 2ml가 있다고 하고 앞에서 구한 6ml 용기와 c를 더하면 6+2+5로 10ml를 넘어간다. 이걸 하나의 식으로 나열하면 a+b+c+10/2+10/2 가 된다. 즉 a, b, c 모두 0ml 이어도 10/2 가 두 번 더해져 10으로 꽉 찬 용기가 되기 때문에 최대 3개의 용기만 있으면 꽉 찬 용기를 만들 수 있는 것이다. 맨 처음에 정렬을 해준 뒤 C[i]가 X와 같다면 혼자서도 꽉..

문제를 요약하면 기존 입력에 N-M+1 개의 가중치가 L 인 간선을 추가로 만들어 모든 점끼리 갈 수 있게 할 때 두 빌라봉을 오가는데 드는 비용 중 가장 큰 값이 가장 작도록 N-M+1 개의 간선을 만드는 것이다. 즉 그래프가 1개 이상이라는 것인데 이때 각 그래프에서 점 하나를 골랐을 때 그 점과 한 그래프의 나머지 점들끼리의 거리의 최댓값이 가장 작은 점을 고른 뒤 한 그래프를 한 점이라고 했을 때 점들을 연결했을 때 점들 간의 거리의 최댓값이 가장 작아야 되기 때문에 점이라고 정의한 그래프의 값 중 가장 큰 값을 중앙에 두고 중앙을 중심으로 다른 점들이 중앙 점과 연결을 할 때 가장 작은 값을 찾을 수 있다. 맨 처음 그래프 내에서 거리의 최댓값이 가장 작은 값을 고르는 방법은 이전에 설명했던 사..

https://www.acmicpc.net/problem/17163 17163번: 가희의 수열놀이 (Large) 첫 번째 줄에는 쿼리의 수를 의미하는 정수 Q와 나누는 정수 mod 가 공백으로 구분되어 주어집니다. (1 ≤ Q ≤ 106, 1 ≤ mod ≤ 2×109) 이후 Q개의 줄에 걸쳐서, 다음 세 종류의 쿼리 중 하나가 주어 www.acmicpc.net 문제에 쿼리가 있어 세그라는 생각을 할 수 있지만 1