joseph0528 코딩 블로그

solved.ac 티어 : 플래티넘 2 www.acmicpc.net/problem/1348 1348번: 주차장 세준 주차장은 R*C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평 www.acmicpc.net bfs를 사용해서 각 자동차(C)마다 모든 주차구역(P)과의 거리를 저장해주고 이분 탐색하면서 이분 매칭으로 나올 수 있는 최솟값을 찾아주면 된다. 이분 탐색은 mid가 있을 때 각 자동차마다 주차구역을 가는 거리가 mid이하인 값들만 가지고 이분 매칭을 해주면 된다. 이때 이분매칭 했을 때의 값이 자동차 개수와 동일하다면 mid와 저장되어있는 최솟값을 비교하여 더 작을 ..

solved.ac 티어 : 골드 4 www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 아주 간단한 mst문제이다. 점의 y, x가 주어지고 정점 개수-1개의 간선을 이어야 되니 모든 점을 이어준다. 이때 가중치는 두 점의 거리가 된다. 그러므로 두 점의 x좌표의 차 제곱 + 두 점의 y좌표 차 제곱을 루트 해준 값이 두 점 사이의 거리가 된다. import sys,math sys.setrecursionlimit(10**9) def find(a): if uf[a]

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 이문제는 기본 mst(최소 스패닝 트리)에서 간선을 추가할 때 두 점이 다른 점이라면 추가하는 방식으로 하면 된다. 그리고 마지막에 -1 처리를 해주면 된다. import sys sys.setrecursionlimit(10**9) def find(a): if uf[a]

solved.ac 티어 : 플래 2 www.acmicpc.net/problem/2570 2570번: 비숍2 서양장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. 과 같이 크기가 5인 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 www.acmicpc.net 이문제는 joseph0528.tistory.com/30 BOJ 9525(룩 배치하기)풀이 solved.ac 티어 : 플래 3 www.acmicpc.net/problem/9525 9525번: 룩 배치하기 체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 변형 joseph0528.tistory...

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/9525 9525번: 룩 배치하기 체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 변형해서 N-Rook 문제를 만들 수 있다. Rook(룩) 은 체스에서 같은 행이 www.acmicpc.net 이 그림은 노란색 행을 선택했을 때 선택될 수 있는 초록색 열이다. 이 그림은 파란색 행을 선택했을때 선택될수 있는 보라색 열이다. 이거처럼 행을 기준으로 나올 수 있는 열에 번호를 매겨서 이분 매칭을 해주면 된다. 위 그림을 번호를 매겨 줬을 때 빨간색은 1, 주황색은 2, 노란색은 3, 초록색은 4, 하늘색은 5, 보라색은 6, 핑크색은 7로 잡아주고(..

solved.ac 티어 : 실버 1 www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 이문제는 joseph0528.tistory.com/25 BOJ 2352(반도체 설계)풀이 solved.ac 티어 : 골드 3 www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야.. joseph0528.tistory...

현재 봇 2개를 가지고 있는데 갑자기 한 생각이 떠올랐다. "봇끼리 대화가 될까?" 그래서 양쪽 봇에다가 hello를 넣어주고 한쪽 봇에서 시작을 했을 때 계속 이어지는지 테스트를 해봤다 결과는 서로 대화를 한다였다. 테스트를 마치고 깜박하고 봇을 안꺼놨더니 채팅이 수도 없이 많이 와있었다;;

문제 제출 여부랑 맞았는지 틀렸는지가 나오게 해 줬고 24시간 봇이 아니고 그냥 틀고 싶을 때 트는 봇이라 db는 안 쓰고 메모장이랑 엑셀을 사용해서 이 봇에서 boj연동을 하는 거를 넣어줬다 한 사람당 한 계정만 추가할 수 있고 다른 사람이 ~add 백준 닉네임 이렇게 치면 계정이 추가된다. 만약 닉네임을 잘못 칠경 우 없는 닉네임으로 뜨게 해 줬다. 그리고 모든 404 에러 날 곳에 다 except 해줬다. 게임을 넣어달라는 분들이 있는데 게임은 나중에 추가해볼 생각이다. 근데 파이썬이라 느리다 근데 잡봇이라 이상한 게 많다 어떤 분들이 넣어달라고 하셔서 넣긴 했다 코드 설명은 안 넣겠다 어차피 속도가 너무 느려서 사용 안 하는 게 더 좋다 이봇이 어디까지 발전할지 궁금하다 import discord..

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/2912 2912번: 백설공주와 난쟁이 첫째 줄에 난쟁이의 수 N과 모자 색상의 수 C가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ C ≤ 10,000) 둘째 줄에는 각 난쟁이가 쓰고 있는 모자의 색상이 줄을 서 있는 순서대로 주어진다. 셋째 줄에는 사진 www.acmicpc.net 이문제는 수열과 쿼리 6을 응용하면 된다. 6 코드에서 값을 재일 마지막에 구해주면 된다. 처음에는 안될 줄 알았는데 이렇게 해줘도 시간이 여유롭게 남는다. void add(int u){ cn[cnt[u]]--; cn[cnt[u]+1]++; } void ms(int u){ cn[cnt[u]]--; cn[cnt[u]-1]++; } fcnt=0..

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 이문제는 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 나올 수 있는 최대 개수를 구하는 것이다. 이때 이문제에서 꼬이지 않게 하려면 i번째의 값보다 i+1번째 값이 더 커야 된다. 즉 이문제는 LIS(최장 증가 부분 수열)이라는 거다. 그러므로 이분탐색 LIS를 구해주면 된다. import sys sys.setrecursionlimit(10000..