Codejam 2019 Qualification Round 문제 1: Foregone Solution 문제 링크 사용 알고리즘 : 문제 설명: 4가 포함된 자연수 N (ex) 14)을 4가 포함되지 않은 두 자연수 A,B로 쪼개는 문제다. N은 T번 주어진다. 풀이: 대회 당시 Visible Testcase는 N s; for(char x : s){ int t=x-'0'; if(t>=7&&t

문제 : BOJ 6989 채점 백준 채점 풀이 KOI 2008 고등부 1번 문제 링크 사용 알고리즘 : DP, 비트마스킹 문제 설명 : n(nn; for(int i=1;i>arr[i],sum[i]=sum[i-1]+arr[i]; for(int i=1;ik; } void solve(){ if(k>score[1][n]){ cout

문제 : BOJ 2453 부서 배치 문제 링크 사용 알고리즘 : 이분매칭 이분매칭이 무엇인지 이 문제를 통해 알았다. 풀이: 1) 문제 설명 테스트케이스 수는 5개다. (외국 형식) 1~n의 사람들이 있다. m번 사람들 사이의 관계가 주어진다. -1 1 2 는 1과 2는 적이라는 뜻이고 1 1 2 는 1과 2는 친구라는 뜻이다. 이 사람들은 KOI 회사에 배정된 신입 사원들인데, 2개 부서 중 하나로 들어가야 한다. 이때, 친구는 같은 부서에, 적은 다른 부서에 위치하도록 사람들을 배치해야 한다. 배치하는 방법 중에서 부서간 인원 수의 차이의 최솟값을 구하는 것이 목표다. 2) 풀이 1. 각 사람들을 그래프의 정점으로 생각하고 dfs 또는 bfs를 통해 친구 또는 적인 사람들의 팀을 정해준다. 예를 들어..

문제 : BOJ 2488 줄다리기 문제 링크 2009 KOI 전국본선 고등부 2번 사용 알고리즘 : 라인 스위핑 문제 분석 : 두 무리의 사람들이 있다. 각각의 무리를 A,B라 할 때 A 무리와 B 무리를 각각 3 모둠으로 분단한다. 사람들 a1,a2,a3,a4,a5 ,b1,b2,b3 가 있다고 하면 임의로 a1,a2 || a3,a4 || a5 b1 || b2 || b3 와 같이 사람들을 분단할 수 있다. 각각의 모둠을 순서대로 1,2,3이라 하고 A무리와 B 무리를 구별하여 A1,A2,A3,B1,B2,B3 모둠이라 하자. 이때 모든 사람들의 몸무게가 주어진다. 분단 시 규칙은 모든 i에 대하여 A i 모둠과 B i 모둠의 몸무게 차이는 50이하가 되어야 한다. 중요한 점은 모든 사람의 몸무게는 20 이..

문제 1: BOJ 8984 막대기 문제 링크:KOI 2013 고등부 2번 사용 알고리즘 : DP 다이나믹 프로그래밍 풀이: 막대기들 중에서 지그재그 형식으로 이어진 선을 찾자. 지그재그 선들 중에서 최대의 길이를 찾는 것이 목표다. 지그재그란 : a-b-e, c-d-f-g 와 같이 서로 이어지면서 교차하지 않는 선을 말한다. 특히 한 점에서 3개 이상의 선이 만날 수 없다. 선의 길이란: 수평거리 + 수직거리 = 절대값( 시작점 x좌표 - 끝점 x좌표) + L 을 의미한다. 먼저 좌표들을 높이로 Top , Down으로 분리하자. 그리고 좌표들을 Top 오름차순으로 정렬한 후 unique( v.begin(),v.end() ) 를 이용해 겹치는 것들을 제거한다. Top ,Down 에서 따로 DP를 정의할 건..

문제 1 : BOJ 2473 세 용액 문제 링크 사용 알고리즘 : 투 포인터 풀이: 투 포인터를 잘 모른다면 두 용액 문제를 먼저 풀고 오는 것이 좋다. 배열을 정렬하고 시작하자. 먼저 for 문을 이용해서 시작지점을 1부터 n까지 정한다. 시작지점을 s라 한다면 s+1 번째 부터 n번째 범위 안에서 두 용액을 더했을 때 -arr[s] 와 가장 근접한 두 용액을 찾는다. 순서대로 m,e 라 하자. 초기값은 m=s+1, e=n이다. abs(arr[s]+arr[m]+arr[e]) 가 기존에 구해놓았던 차이보다 작으면 답을 갱신해준다. 배열이 정렬되어 있으므로 arr[s]+arr[m]+arr[e]>0 이면 e-- 해주고 (용액의 합 감소) arr[s]+arr[m]+arr[e]

문제 : BOJ 10840 구간 성분 문제 링크 사용 알고리즘 : 1. STL set 2.해싱 풀이: 1. STL set을 사용한 풀이 각 부분 문자열에 대한 알파벳 개수를 벡터를 이용해 센다. 이때 문자열에서 길이별로 슬라이딩 윈도우를 이용해 개수를 빠르게 구해준다. 1번째 문자열에서는 크기 26의 벡터로 알파벳의 개수를 저장하고 set에 넣어준다. 2번째 문자열에서도 벡터를 구한 다음 set에서 확인한다. 이때 길이를 큰 것부터 확인하면 탐색 공간 배제가 가능하다. 2. 해싱을 사용한 풀이 각 알파벳을 소수에 대응한다. 각 부분 문자열에 대한 '구간 성분 값'은 소수의 곱을 mod 한 결과로 대응한다. 이때 해시 충돌 가능성이 있으므로, 다른 알파벳을 소수에 대응하여 이중 해싱을 해준다. (즉, 소수..

정보올림피아드 고등부 1,2번 정복기 https://www.acmicpc.net/workbook/view/4576 문제집: KOI 고등 1,2번 (pentagon03) www.acmicpc.net 친구 (Saycorn)과 3/28 부터 새로운 도전을 시작한다. 실행방법 1.매일 난이도에 따라 1~2문제를 정한다. 2.생각 시간을 30분~1시간 정도로 정한다. 3. 서로에게 풀이를 설명해주는 시간을 갖는다. i) 둘다 품 : 서로 풀이를 공유하고 좋은 점 찾기 ii) 한명만 품 : 푼 사람이 안 푼사람에게 알려주기 iii) 둘다 못품 : 지금까지 알아낸 것 공유 + 답지 분석 쟁점은 어떤 상황이든 이 문제의 풀이를 다른 사람에게 설명해주는 행위에 있다. 이 도전을 하게 된 계기는 아래 슬라이드를 읽은 것이..

코드업 3180 간단한 문제 첫째 줄에 수열의 길이 $N$이 주어진다. $(1 \le N \le 3*10^{5})$ 둘째 줄에 $A_{1}, A_{2}, ..., A_{N}$이 주어진다. $(-10^{9} \le A_{i} \le 10^{9})$ 셋째 줄에 질의의 개수 $M$이 주어진다, $(1 \le M \le 3*10^{5})$ 넷째 줄부터 쿼리가 한줄에 하나씩 주어진다. $(1 \le i \le j \le N, -10^{9} \le x \le 10^{9})$ codeup.kr https://codeforces.com/blog/entry/52477 qoo2p5 의 말이 핵심 How to find frequency of a given element in a range? - Codeforces codef..

https://booknu.github.io/2019/01/17/오일러의 체 오일러의 체 - 빠른 소인수분해, 소수 찾기 Content Similar Posts Comments booknu.github.io 이게 정말 효율적인 소수 판별법인데 주기적으로 복습하지 않으면 그 논리를 계속 까먹는다. 출처는 위 링크 코드 설명 spf[x] : x의 가장 작은 소인수 spf[x]==x 이면 x는 소수 pn: 지금까지 찾은 소수의 개수 pr[x] : x-1번째 소수 123456789101112131415#define FOR(i, f, n) for(int (i) = (f); (i) = pr[j]임을 확신할 수 있다. spf 를 이용하면 소인수 분해를 빠르게할 수 있다. 1234while(x!=1){ printf("..

*코드업에서 실행시간/코드 길이(시간 같을 경우) 1등인 문제 목록 (2020년 4월 24일) 개인적으로 4533 보물섬 과 4714 키 순서 문제가 레전드. https://codeup.kr/problem.php?id=2102 배수 (Hard) $0$과 $1$로 이루어진 $N$의 배수 중 가장 작은 자연수를 출력한다. 이때 출력되는 자연수의 맨 앞자리는 $1$이어야 한다. 조건을 만족하는 자연수가 unsigned long long형의 범위에 없을 경우 $0$을 출력한다. codeup.kr https://codeup.kr/problem.php?id=2782 편의점 가는 길 1 $(1,1)$에서 $(w,h)$ 까지 도달하는 최단 경로의 수를 $1,000,000,000$으로 나눈 나머지를 출력하시오. code..

※이 글은 사람이 10명 이하일 때의 알고리즘입니다. Large 문제의 해법은 0000 원하는 상태 ==> 1111 이 된다. 탐색 알고리즘 n이 7 이하이기 때문에 사람들이 분포될 수 있는 경우의 수는 2^7 * 2(배의 위치) = 256 으로 매우 작다. 그렇기 때문에 브루트 포스 (DFS)로 충분히 해결될 수 있을 것이라 보았지만 웬걸, 83퍼에서 시간 초과가 걸리고 말았다. 다시 생각해보니 256개의 정점이 있는 것이더라.. 일반적인 DFS로 풀 경우 지수함수에 비례하는 시간이 걸리므로 시간 초과가 날 수 밖에 없다. 그럼 지금 구해야 하는 것은 가중치 그래프에서의 최단 거리이다. 그렇다면 역시 다익스트라 알고리즘을 사용하자. 아래 풀이를 이해하기 위해서는 다익스트라 알고리즘에 대한 기본적인 이해..