kth990303의 코딩 블로그

오랜만에 수학 문제가 풀고 싶어졌습니다. 그렇다고 막 IQ 문제 풀고 싶은게 아니라, 적절한 도구를 이용해서 해결할 수 있는 문제를 풀고 싶었어요. 그래서 에라토스테네스 문제나, 유클리드 호제법 문제를 풀려고 solved에서 고르던 중 발견한 좋은 문제입니다~ www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 딱 봐도 '소수' 가 붙어있으니, 에라토스테네스의 체 (sieve) 문제일 거 같다는 생각이 들지 않나요? 다행히 예상을 빗나가지 않았습니다! 의식의 흐름. 도대..

dp문제를 풀다가 어서 아이디어 까먹기 전에 기록해야겠다고 생각해 허겁지겁 포스팅하게 되었습니다. (원래 오늘 안쓰려 했는데 ㅠㅠ) www.acmicpc.net/problem/2229 2229번: 조 짜기 알고스팟 캠프에 N(1≤N≤1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 학 www.acmicpc.net 백준 2229번. 조 짜기 문제입니다. 이 문제는 친구가 추천해준 문제인데, 개인적으로 저한테는 생각보다 얻어갈 점이 많아서 좋았던 문제입니다. 의식의 흐름. 처음엔 문제를 잘못 읽어서 pair로 나이, 점수를 저장시켜야 된다고 생각해 꽤나 어려운 dp라 생각했습니다. 그런데, ..

오늘은 그래프와 dp를 모두 좋아하시는 분이라면 아주 신이 날 문제(...)를 리뷰하게 됐습니다! www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 바로 백준 15681번. 트리와 쿼리 문제입니다~~ ???: 아니, 골드5잖아요? 왜 제목엔 실버 상위권이라 써놨습니까?!? 저는 제목에 solved.ac 티어를 쓰기보다는, 제가 생각하는 이 문제의 난이도를 씁니다. 대체로, solved.ac 티어는 ..

지난번에 제가 개인적으로 운영하는 그룹에서 모의대회 연습에 있었던 문제입니다. 바로, 백준 5710번. 전기 요금 문제입니다. www.acmicpc.net/problem/5710 5710번: 전기 요금 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 두 정수 A와 B가 주어진다. (1 ≤ A, B ≤ 109) 항상 정답이 유일한 경우만 주어지며, 입력으로 주어지 www.acmicpc.net H번으로 있었는데, 이 때 저는 저 문항을 시간초과를 받고 틀렸었죠. 오늘 낮에 다시 풀어봤는데 맞왜틀하길래 뭔가 했는데, 함수 계산식을 하나 잘못 썼었습니다... 이 문제 자체가, 로직은 맞더라도 실수로 틀리기 쉬운 문제인 듯 합니다. 의식의 흐름. 처음에 봤을 땐 수학..

www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X www.acmicpc.net 백준 16564번. 히오스 프로게이머 문제. 무난한 이분탐색 문제이다. 의식의 흐름. 음... 일단 K가 10억이니까 시간복잡도가 log인 계산이 무조건 들어가겠네. 이거 딱봐도 이분탐색으로 해결해야되네. lower_bound로 제발 해결 가능했음 좋겠다. 아씨 lower_bound로 어떻게 해결해야 되는지 안보여. 그냥 while문으로..