joseph0528 코딩 블로그

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네 첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판 www.acmicpc.net 이문제는 트리에 어떤 노드가 선택되었을 때 그 노드와 노드의 자식들에게 w만큼 값이 더해지는 문제다 대신 이 문제는 다른 평범한 세그먼트 트리처럼 이진트리가 아니다. 그럼 어떻게 할 수 있을까? 예시에 있는 입력을 가지고 트리를 만들면 이렇게 된다.(좀 이상한 건 어쩔 수 없다) A부터 E까지 순서대로 1,2,3,4,5라고 할 때 A..

solved.ac : 골드 3 각 점들마다 ccw를 구해서 교차했는지 안 했는지 판별하면 된다. 한 선분의 두점과 다른 선분의 점과 ccw를 했을 때 1,-1 또는 -1,1 또는 0,0 이면 교차한다. 반대도 해주면 된다. def q(x1,y1,x2,y2,x3,y3): r=x1*y2+x2*y3+x3*y1;r=r-y1*x2-y2*x3-y3*x1 if r>0:return 1 elif r

solved.ac 티어 : 골드 2 S와 모든 K 간의 거리를 구해서 스패닝 트리를 구해주면 된다. import sys from collections import deque sys.setrecursionlimit(10**9) def find(a): if uf[a]

solved.ac 티어 : 골드 4 www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 코드업의 극장 좌석 배치 2를 풀고 하면 쉽게 할 수 있다. codeup.kr/problem.php?id=2652 극장 좌석 배치 2 극장에 nn개의 빈 좌석이 있다. kk명의 관객들이 영화를 보기 위해서 왔다. 이 관객들이 nn개의 좌석에 앉을 수 있는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오. (단, kk명의 사람 codeup.kr 이 문제와 색상환의 다른 점은 색상환은 양..

후기 : 수학대회라 2솔만 하자 했었는데 3솔이나 해서 기분이 좋았지만 b랑 c에서 어이없는 실수를 너무 해서 아쉽다. D는 배웠는데 생각이 안 나서 못 푼 게 아쉽고 일단 3솔해서 좋지만 좀 아쉬운 대회였다. 풀이 : A 더보기 A는 요약하면 우승할 수 있는 사람 수다. 그러므로 정렬을 한 다음 가장 작은 값들을 제거하고 남은 값들은 모두 우승할 수 있다. import sys,math,queue #sys.setrecursionlimit(10**9) input=sys.stdin.readline t=int(input()) for _ in range(t): n=int(input()) l=list(map(int,input().split())) l.sort() g=0 for i in range(1,n): if ..

오랜만에 버추얼을 돌려봤는데 2 솔밖에 못했다. 바로 풀이를 쓰자면 A import sys input=sys.stdin.readline t=int(input()) for _ in range(t): n=int(input()) l=list(map(int,input().split())) r=[0]*200 s=0 for i in range(n): r[l[i]]+=1 s=max(s,r[l[i]]) print(s) 그냥 가장 많이 중복되는 개수를 출력하면 끝이다. B import sys input=sys.stdin.readline t=int(input()) def p(x): #print(x) if int(x)

solved.ac 티어 : 골드 4 www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 이문제는 설명은 길지만 요약하자면 m개의 줄에 2개의 점이 주어질 때 그 2개의 점이 같은 집합에 속하는 번째수를 출력하는 것이다. 이문제는 유니온 파인드로 풀 수 있다. import sys sys.setrecursionlimit(10**9) input=sys.stdin.readline n,m=map(int,input().split()) uf=[-1]*(n+1) def ..

solved.ac 티어 : 골드 2 www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 이문제는 단순하게 입력으로 들어오는 구간마다 하나씩 비교하면서 처리하는 방식은 시간 초과가 난다. 그럼 어떻게 할 수 있을까? 예를 들어 1 2 1 1 2 1 이면 배열이 있고 1 6이라는 입력이 들어왔다. 1 2 1 1 2 1은 팰린드롬이기 때문에 1을 출력해야 한다. 이때 양끝을 제외한 나머지가 팰린드롬이고 양쪽이 같을 경우 팰린드롬이 된다. 이걸 계속 적용한다면 범위의 값이 팰린드롬인지 아닌지를 알 수 있고 ..

solved.ac 티어 : 다이아 4 www.acmicpc.net/problem/16910 16910번: mex와 쿼리 mex는 어떤 수열에 포함되지 않은 수 중에서 가장 작은 자연수를 찾는 함수이다. 예를 들어, mex([1,2,3]) = 4, mex([5,3,1,1,4]) = 2, mex([1,5,2,1,5,2,1,2]) = 3이다. 비어있는 배열 A와 쿼리 N개가 주어졌을 때, www.acmicpc.net 생각보다 간단한 세그레이지이다. 1 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에 추가한다. 배열에 이미 있는 자연수는 또 추가하지 않는다. 2 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에서 제거한다. 3 l r: 구간 [l, r]에 속하는 모든 자연수 x에 대해서,..

바뀐 내용은 일단 프로필이 이름, 랭킹, 링크만 있어서 허전했는데 solved.ac 사이트 프로필 사진과 티어를 넣어줬고 만약 프로필 사진이 없는 경우 따로 물음표 사진을 출력하게 해 줬고 가장 크게 바뀐 거는 기존 urlopen에서 json을 사용해서 파싱 하는 방법으로 바뀌어서 속도가 좀 더 빨라진 게 크게 바뀐 거고 문제 입력했을 때 문제 티어 출력하는 거만 추가했다. 없어진 거는 틀린 문제 맞은 문제 제출했지만 다 맞지 못 한문제 이렇게 나눠져 있던 거를 푼 문제 안 푼 문제로 2개로 줄였다 그리고 solved.ac에 레이팅 기능이 생겼는데 계산 방법이 제대로 정해지진 않아서 나중에 정해질 경우 추가 예정 그리고 urlopen 대부분을 json으로 바꿀 예정 (팩트는 아무도 안 쓴다는 거) 잡봇이..