PS(201)
-
[도전 15일차] 경비행기, 두 배열의 합 - KOI 고등부 풀이
※복습 : 문제 1 : 백준 2585 경비행기 문제 링크 사용 알고리즘 : 이분탐색 (Parametric Search), BFS 풀이: 기름 용량이 X일 때 시작점 부터 도착점까지 경로 중 경유지 수의 최소값을 B(X) 라 하자. 기름 용량이 크면 클수록, 한 경유지에서 갈 수 있는 경유지의 수가 많아지므로 Xi = B(Xj) 이다. 이분탐색은 정렬되어 있는 집합에서 사용할 수 있으므로 X가 1~(시작점-도착점 거리) 일 때 B(X) 집합에 대하여 이분탐색을 수행할 수 있다. BFS를 수행하면서 거리를 중복 계산할 수 있기 때문에 모든 거리를 미리 구해 놓았다. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..
2020.04.15 -
[도전 14일차] 양팔저울 - KOI 고등부 풀이
※복습 : ※ 백준 2629 양팔저울 문제와 다른 문제입니다. 문제 : 백준 1653 (KOI 2005 고등부 1번) 문제 링크 사용 알고리즘 : 완전탐색 (백트래킹) 풀이: 도전 6일차 때 풀었던 KOI채점과 같은 맥락으로 K가 10억까지 가능한 것처럼 묘사해 놓았지만, 실제로는 가능한 추의 크기가 9개 이하로 제한되어 있으므로 가능한 모든 추 배치는 3^9 * 5! * 5! 개 미만이다. ( 왼쪽에 넣거나, 넣지 않거나, 오른쪽에 넣는다 + Permutation) 이를 계산하면 2*10^8 정도 인데, 실제로 가능한 배치는 적으므로 완전탐색으로 평형점수지 확인한 다음 정렬해주면 문제를 해결할 수 있다. 내 코드는 980ms로 AC 받았다. 허허.. 정말 간당간당해서 오히려 더 성취감이 더 크다. 지난..
2020.04.14 -
[도전 13일차] 잠수함 식별 - KOI 고등부 풀이
※복습 : 문제 : BOJ 2671 잠수함 식별 문제 링크 사용 알고리즘 : 오토마타 이론 풀이: 문제를 읽어보자. 주어진 이진문자열이 (100~1~|01)~ 의 패턴을 가지는지 식별해야 한다. 처음 접근으로는 문자열의 처음부터 살펴보면서 처음에 1이면 그 후에 100~1~ 의 패턴을 가지는지 검사, 0이면 01인지 검사, 이런식으로 쭉쭉 나아가는 방법이 있다. 한번 상상해보자 벌써 무수히 많은 if문의 향연이 상상되지 않는가? 상태를 체계적으로 결정하는 것이 바로 오토마타를 이용한 매칭이다. 오토마타 이론은 상태 간 연관 관계를 이용하여 변환 후 최종 상태를 결정할 때 이용할 수 있다. 순서도와 비슷해 보인다. 힘듦과 행복이라는 상태간 연관 관계를 표시해 보았다. 오토마타가 무엇인지 알았으니, 이제 문..
2020.04.13 -
[도전 12일차] 돌다리 건너기 - KOI 고등부 풀이
※복습 : 문제 : BOJ 2602 돌다리 건너기 문제 링크 사용 알고리즘 : DP 풀이: 전형적인 DP 문제다. 1. DP 정의를 하자. DP(c, r, k) => c번째 열,r(0or1)번 행부터 문자열 끝까지 k번째 글자부터 채워 나갈 때 나올 수 있는 경우의 수 2. 점화식을 세우자 DP(c, r, k) = DP(c+1,r,k) + DP(c+1, !r, k+1) 단, DP(c+1,!r,k+1) 은 c번째 k번 행이 k번째 문자일 때만 적용된다. 3. 구현을 하자. 자열의 길이가 100 정도로 아주 작으므로 재귀함수 + 메모이제이션으로 구현하자. (직관적이다.) 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 //pentagon..
2020.04.13 -
(※도전 완료) [도전 11일차] 백준 6990 달팽이
풀었습니다. howtoliveworldnice.tistory.com/129 [도전 28일차] 기하 구현 끝판왕, 달팽이 백준 6990 달팽이 2020/04/09 - [Problem Solving/KOI 고등부] - (※재도전 시급) [도전 11일차] 백준 6990 달팽이 4월 9일에 포기했던 문제를 6개월만에 다시 잡다. 6개월 전 시청한 IOI Korea님의 풀이와 나의.. howtoliveworldnice.tistory.com ※복습 : 문제 : BOJ 6990 달팽이 문제 링크 사용 알고리즘 : 기하 풀이: IOI Korea 류호석님 지금 실력으로는 구현이 불가. 직전까지 짠 코드만을 첨부함. 다음 문제로 넘어가는 것이 현명. 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..
2020.04.09 -
Scheduling/스케줄링 알고리즘
Code SASA가 다시 열린 기념으로 선배들이 만든 문제를 풀었다. 그러던 도중 예전에 풀었던 문제를 발견했다. https://code.sasa.hs.kr/problem.php?id=1297 SASA OJ 영화를 좋아하는 세종이는 쉬는날인 오늘 영화관에 가서 하루종일 영화를 보려고 한다. 오늘 상영하는 영화의 개수를 N, 각각의 영화의 상영 시작 시간을 S, 상영 종료 시간을 E라고 할 때, 오늘 세종이가 볼 수 있는 영화의 최대 수를 출력하여라. (단, 오늘 24시 이전에 시작하여 다음날에 끝나는 영화도 오늘 상영하는 영화에 포함하며, 상영시간이 24시간 이상인 영화는 없다.) code.sasa.hs.kr (전형적으로 보이는) 영화 스케줄링 문제이다. 어떻게 풀었나 싶어 봤더니 웬걸 N=100 인데도..
2020.04.09 -
[도전 10일차] 백준 2300 기지국
※복습 : 문제 : BOJ 2300 기지국 문제 링크 사용 알고리즘 : 다이나믹 프로그래밍 풀이: 점화식을 세우자. DP(n) 을 1~n번째 기지국까지 보았을 때 기지국 설치비용의 최솟값이라 정의하자. 건물들의 좌표를 x좌표 기준 오름차순으로 정렬했을 때 다음 점화식이 성립한다. $$ DP(n) = \min_{1>arr[i].second; sort(arr+1,arr+n+1); cout
2020.04.08 -
[도전 9일차] 2541 점
※복습 : 문제 : BOJ 2541 점 문제 링크 KOI 2007 고등부 1번 사용 알고리즘 : 수학 아이디어 제공 : hongjun님의 블로그 풀이: 초기에 점 (x,y)가 주어진다. (규칙 1) 점 (x, y)가 S에 속해 있다면, 점 (x+1, y+1)을 S에 추가한다. (규칙 2) 점 (x, y)가 S에 속해 있고, x와 y가 모두 짝수이면, 점 (x/2, y/2)를 S에 추가한다. (규칙 3) 두 점 (x, y)와 (y, z)가 S에 속해 있다면, 점 (x, z)를 S에 추가한다. 그 후 주어지는 5개의 점에 대해 S에 속할 수 있는지 판별하는 문제다. 단순하게 생각해도 x,y의 범위가 1~10^5이므로 백트래킹과 같은 방법은 시간 제한안에 수행되지 못한다. 규칙을 분석하여 가능한 점들의 특징을..
2020.04.07 -
[도전 8일차] 체인점 - KOI 고등부 2번
※복습 : 문제 : BOJ 2472 체인점 KOI 2010 고등부 2번 체인점 문제 링크 사용 알고리즘 : 다익스트라, 세그먼트 트리 문제 요약 : N ( x 이고 b > y 이고 c > z이면 p에는 매장을 설치하지 않는다. M개의 후보지 번호가 입력으로 주어질 때, 각각의 후보지가 매장이 될 수 있을 지 YES / NO 로 구분해 출력하는 것이 목표다. 풀이: 중요한 것은 후보지로부터 아파트까지의 거리이므로 반대로 생각하면 아파트부터 후보지까지의 거리이다. 가중치 그래프에서 최단경로를 구하는 것이므로 아파트 3군데에서 다익스트라 알고리즘을 사용하자. 정점의 수 V>=1; } if(l==r) res=min(res,tree[l]); return res; } }; vector B; inline int ge..
2020.04.05 -
[도전 7일차] Codejam 2019 예선 (1)
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
2020.04.03 -
[도전 6일차] 채점 - KOI 고등부 풀이
문제 : 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
2020.04.03 -
[도전 5일차] 2453 부서 배치
문제 : BOJ 2453 부서 배치 문제 링크 사용 알고리즘 : 이분매칭 이분매칭이 무엇인지 이 문제를 통해 알았다. 풀이: 1) 문제 설명 테스트케이스 수는 5개다. (외국 형식) 1~n의 사람들이 있다. m번 사람들 사이의 관계가 주어진다. -1 1 2 는 1과 2는 적이라는 뜻이고 1 1 2 는 1과 2는 친구라는 뜻이다. 이 사람들은 KOI 회사에 배정된 신입 사원들인데, 2개 부서 중 하나로 들어가야 한다. 이때, 친구는 같은 부서에, 적은 다른 부서에 위치하도록 사람들을 배치해야 한다. 배치하는 방법 중에서 부서간 인원 수의 차이의 최솟값을 구하는 것이 목표다. 2) 풀이 1. 각 사람들을 그래프의 정점으로 생각하고 dfs 또는 bfs를 통해 친구 또는 적인 사람들의 팀을 정해준다. 예를 들어..
2020.04.02 -
[도전 4일차] 2488 줄다리기
문제 : 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 이..
2020.04.01 -
[도전 3일차] 막대기, 섞기 수열
문제 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를 정의할 건..
2020.03.30 -
[도전 2일차] 세 용액, 버스 노선
문제 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]
2020.03.29 -
[도전 1일차] 10840 구간 성분
문제 : BOJ 10840 구간 성분 문제 링크 사용 알고리즘 : 1. STL set 2.해싱 풀이: 1. STL set을 사용한 풀이 각 부분 문자열에 대한 알파벳 개수를 벡터를 이용해 센다. 이때 문자열에서 길이별로 슬라이딩 윈도우를 이용해 개수를 빠르게 구해준다. 1번째 문자열에서는 크기 26의 벡터로 알파벳의 개수를 저장하고 set에 넣어준다. 2번째 문자열에서도 벡터를 구한 다음 set에서 확인한다. 이때 길이를 큰 것부터 확인하면 탐색 공간 배제가 가능하다. 2. 해싱을 사용한 풀이 각 알파벳을 소수에 대응한다. 각 부분 문자열에 대한 '구간 성분 값'은 소수의 곱을 mod 한 결과로 대응한다. 이때 해시 충돌 가능성이 있으므로, 다른 알파벳을 소수에 대응하여 이중 해싱을 해준다. (즉, 소수..
2020.03.29 -
[도전] KOI 고등부 1,2번 정복
정보올림피아드 고등부 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) 둘다 못품 : 지금까지 알아낸 것 공유 + 답지 분석 쟁점은 어떤 상황이든 이 문제의 풀이를 다른 사람에게 설명해주는 행위에 있다. 이 도전을 하게 된 계기는 아래 슬라이드를 읽은 것이..
2020.03.29 -
Codeup/코드업 3180 간단한 문제 풀기 위해 공부 했던 것들
코드업 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..
2020.03.26 -
내가 보려고 만든 소인수분해 방법 정리글
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("..
2020.02.26 -
CodeUp에서 기억나는 문제
*코드업에서 실행시간/코드 길이(시간 같을 경우) 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..
2020.02.20 -
강 건너기 문제
※이 글은 사람이 10명 이하일 때의 알고리즘입니다. Large 문제의 해법은 0000 원하는 상태 ==> 1111 이 된다. 탐색 알고리즘 n이 7 이하이기 때문에 사람들이 분포될 수 있는 경우의 수는 2^7 * 2(배의 위치) = 256 으로 매우 작다. 그렇기 때문에 브루트 포스 (DFS)로 충분히 해결될 수 있을 것이라 보았지만 웬걸, 83퍼에서 시간 초과가 걸리고 말았다. 다시 생각해보니 256개의 정점이 있는 것이더라.. 일반적인 DFS로 풀 경우 지수함수에 비례하는 시간이 걸리므로 시간 초과가 날 수 밖에 없다. 그럼 지금 구해야 하는 것은 가중치 그래프에서의 최단 거리이다. 그렇다면 역시 다익스트라 알고리즘을 사용하자. 아래 풀이를 이해하기 위해서는 다익스트라 알고리즘에 대한 기본적인 이해..
2020.02.02