본문 바로가기

SYSTEM_ERROR_CODE:0

백준 9251번 - LCS (Longest Common Subsequence) * 문제 링크 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 내용 요약 문자열이 2개 주어지면 (최대 길이 1000자), 공통된 부분 수열 중 가장 긴 거 길이를 출력해라. (Longest Common Subsequence = 최장 공통 부분 수열) 접근법 매우 유명한 다이나믹 프로그래밍 문제 2 정도로 보면 된다. 항상 그렇듯이, 무엇을 어떻게 메모할지를 정하는 것이 중요하다. 첫번째 힌트로.. 더보기
백준 2565번 - 전깃줄 * 문제 링크 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 내용 요약 전봇대에 높이에 따라 1번부터 500번까지 있는데, 전깃줄은 두 전봇대 각각의 번호 한 쌍을 연결한다. 근데 이게 교차되면 합선되니까 교차가 안되게 제거할 전깃줄의 최소 개수를 구해라 접근법 단계별로 풀어보기에도 나와있지만, 이 문제 또한 LIS의 응용 문제다. LIS에 관한 설명은 아래의 링크를 참고하자. https://syerco0.com/22 백준 11053번 - 가장.. 더보기
백준 11054번 - 가장 긴 바이토닉 부분 수열 * 문제 링크 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 내용 요약 어떤 수 S_k 를 기준으로 S_1 부터 S_k 까지 증가, S_k 부터 S_n 까지 감소하는 형태면 바이토닉 부분 수열이라고 부른다. 수열이 주어지면 가장 긴 바이토닉 부분 수열의 길이를 구하여라. 접근법 일단은 이 문제를 풀기 전에 LIS 문제부터 풀고 오는 것을 추천한다. https://syerco0.com/22 백준 11053번 - 가장 긴 증가하는 부분 수열 (LIS) * 문제.. 더보기
아니메컵 1쿨 어영부영 참가 후기 ※ 이 글은 대회가 열린 날 밤에 작성자의 기억을 바탕으로 작성되어 저장해놨던 글로, 그때의 감상 및 시점을 기준으로 작성되었음을 미리 알려드립니다. ※ 정말 어영부영 참가하고 어영부영 글 쓰는 것이라 영양가 없음 주의 ※ 작성자는 BOJHelp의 이용규칙을 읽고 왔습니다. (발견해서 읽었습니다.) 이용 규칙에 어긋나지 않게 글을 쓰려고 했지만, 미처 어긋난 부분이 있을 경우 알려주시면, 알게되는대로 수정/삭제하겠습니다. * (23.02.08 추가) 대회 링크 있으면 좋을 거 같아서 https://www.acmicpc.net/contest/view/938 아니메컵 1쿨 www.acmicpc.net 그냥 지나가다가... 그냥 평소처럼 솔브닥 잔디 심어야지 하는데 대회를 열어보니 아니메컵 1쿨이 진행 중이었.. 더보기
백준 11376번 - 열혈강호 2 * 문제 링크 https://www.acmicpc.net/problem/11376 11376번: 열혈강호 2 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, www.acmicpc.net 문제 내용 요약 강호네 회사에서는 또 직원 N명과 할 일 M개가 있다. (1 ≤ N,M ≤ 1000) 직원 한 명은 2 개의 일만 가능하고, 한 일에는 한 명만 배정되어야 한다. 최대 몇 개의 일을 할 수 있을까? 접근법 11375번 열혈강호 문제를 먼저 풀어오기를 추천한다. https://syerco0.tistory.com/19 백준 11375번 - 열혈강호 * 문제 링.. 더보기
백준 11375번 - 열혈강호 * 문제 링크 https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 문제 내용 요약 강호네 회사에서는 직원 N명과 할 일 M개가 있다. (1 ≤ N,M ≤ 1000) 직원 한 명은 한 개의 일만 가능하고, 한 일에는 한 명만 배정되어야 한다. 최대 몇 개의 일을 할 수 있을까? 접근법 하나의 직원에 하나의 일을 매칭하는, 즉 2개의 집합의 원소를 일대일로 매칭시키는 문제다. 가장 기본적인 "이분 매칭(Bipartite Matching)" 문제.. 더보기
디스코드 봇 개발 일지 2023-01-26 - Embed ※ 작성자가 작성한 내용이 일부 틀릴 수도 있음 주의 ※ 작성자가 코드 쓰다가 계속 코드 수정함 주의 그동안 약간씩의 수정은 있었으나... 디코 봇 마지막 글 이후 2주의 시간이 지났는데... 특별히 글로 쓸만한 새로운 개념은 없었다. 그런데 쓰다보니 하도 명령어 채널을 글로 뒤덮기도 하고 Queue 를 출력하는 데에 10번의 출력을 반복하는 것 자체도 비효율적일 뿐더러 (대충 짜놓고 방치했었음) 채널이 좀 지저분해지는 것이 있었다. 그래서 좀 찾아보니, 메시지를 send 하는 데에 있어, "Embed" 라는 데이터 클래스가 있었고 많이 귀찮기는 한데 예쁘게 출력하기는 좋아서 사용했다. Discord.Embed 아래는 대충 기본형태 및 주요 변수들을 나열한 것들이다. class discord.Embed(.. 더보기
백준 3878번 - 점 분리 * 문제 링크 https://www.acmicpc.net/problem/3878 3878번: 점 분리 평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 www.acmicpc.net 문제 내용 요약 2차원 좌표 1사분면에 검정 점과 흰 점이 많이 있는데 (1 ≤ N,M ≤ 100) 얘네들을 직선 하나로 색깔별로 분리하려고 한다. 직선은 어떤 점도 만나면 안된다. 분리가 되는지 안 되는지 판단하자 (그림은 문제 링크 참고) 필요 배경 지식 두 가지 배경 지식이 필요하다. 컨벡스 헐과 선분 교차 판정 두 가지다. 이에 대한 기본적인 내용은 아래의 두 글을 참고하길 바.. 더보기

728x90
반응형