PS/도전(56)
-
[도전 25일차] 수열 축소 - KOI
※복습 : 문제 : KOI 2000 고등부 1번 수열축소 코드업/Codeup 4466 수열축소 문제 링크 사용 알고리즘 : Dynamic Programming 지난 포스팅에서 BOJ 수열 축소 문제를 다뤘는데, 2020/04/24 - [Problem Solving/KOI 고등부] - [도전 24일차] 수열 축소 - 백준 원조 KOI 문제랑 조건이 꽤나 달랐다. 코드업에 KOI 문제가 있길래, 오늘은 이 문제를 다루어 보겠다. 풀이: 이 문제는 CON(i) 연산을 수행 했을 때 단순히 a(i)에서 a(i+1) 를 빼는 것이 아니라, 그 것에 절대값을 취한다. 그렇기 때문에 a2가 무조건 빼진다는 것조차 보장되지 않는다. 그런데 놀랍게도 이 문제의 경우 n이 30 이하, a의 원소도 30이하로 수의 범위가 ..
2020.04.25 -
[도전 24일차] 수열 축소 - 백준
※복습 : 문제 : 백준 2237 수열 축소 문제 링크 사용 알고리즘 : Dynamic Programming 풀이: 1. CON 연산에 쫄 필요 없다. n=3, n=4인 경우에 해보면 대충 감이 잡힌다. n=4일 때 T로 가능한 값은 a1 - a2 - a3 - a4 a1 - a2 - a3 + a4 a1 - a2 + a3 - a4 a1 - a2 + a3 + a4 로 총 4가지다. a1은 무조건 더해야 하고, a2는 무조건 빼야 한다. 그리고 뒤에 것들은 어떤 부호이든 가능한 것이 핵심이다. 어떤 수열에 대해서 2번째 지점에 오는 친구는 무조건 빼야 되는게 핵심이다. CON(1)을 실시하면 a3를 a2로 땡겨오게 된다. 그러면 이제 a3도 빼야 한다. CON(2)를 실시하면 a3을 a2에서 뺀다. 그런데, ..
2020.04.24 -
[도전 23일차] 교차하지 않는 원의 현들의 최대 집합 풀이
※복습 : 문제 : 백준 2673 교차하지 않는 원의 현들의 최대집합 문제 링크 사용 알고리즘 : DP 풀이: 일단 먼저 두 현이 겹치는지 파악하는 방법을 생각해보자. 두 현을 각각 (a,b) , (c,d)라고 하면 교차하는지 파악하는 방법은 다음과 같다. bool cross(int a,int b,int c,int d){ if(a>b)a^=b^=a^=b; return (a
2020.04.23 -
[도전 22일차] 로봇 - KOI 고등부 풀이
※복습 : 문제 : BOJ 2633 로봇 문제 링크 3연속 BFS 문제! 사용 알고리즘 : BFS 풀이: 이번엔 시작점에서 목표점까지 가는데 꺾어야 하는 횟수를 묻는다. 좌표값의 범위가 작으므로 지난 문제 미로 만들기처럼 관심있는 값(꺾은 횟수)를 들고 다니면서 BFS를 수행해주면 된다. 장애물의 경계에 놓인 경우 강제적으로 꺾어주면 된다. (방향이 2개로 정해진다.) 장애물의 경계에 놓인 것을 판정하는 것이 핵심인데 필자는 각각의 점에 대해 (최대 10000개) 가능한 방향을 체크해주는 것으로 해결했다. 장애물의 가능한 모양은 다음과 같다. 이제 p1을 기준으로 장애물을 구분하고, 각각의 경계의 점에 대하여 가능한 방향을 정해주면 된다. 이때 각 경계선에 있는 점마다 탐색이 불가능한 방향이 있는 것을 ..
2020.04.22 -
[도전 21일차] 통나무 옮기기 - KOI 고등부 풀이
※복습 : 문제 : BOJ 1938 통나무 옮기기 문제 링크 사용 알고리즘 : BFS 풀이: 최단 횟수를 구하는 문제는 대부분 무가중치 그래프에서의 최단 거리 문제로 변형되고, 이는 BFS로 해결 가능하다. 앞서 풀었던 미로만들기 문제 와 비슷하다. 입력은 공백으로 구분되어 입력되므로 scanf(" %c",&chr); 과 같이 입력 받아 처리해주면 된다. 통나무의 세 점을 모두 들고 다니는 것은 번거로우므로 중심점과 방향(가로/세로)으로 구조화 하자. 입력 받을 때 배열에 'B' ,'C' 인 경우 따로 표시를 해두어, 각각 2번째로 찾은 위치가 통나무의 중심 좌표다. 탐색을 진행할 때 세 점이 모두 맵 안에 들어 있는지 확인을 해주어야 한다. 이것은 safe 함수를 개량하여 간단하게 코드를 짤 수 있다...
2020.04.21 -
[도전 20일차] 미로 만들기 풀이 - KOI 고등부
※복습 : 문제 : 백준 2665 미로 만들기 문제 링크 사용 알고리즘 : BFS 풀이: 시작점에서부터 도착점까지 가면서 색을 바꾸어야 할 검은 방의 최소 개수를 구하는 것이 목표다. 시작점으로부터 탐색을 돌리는데 들고 다닐 것은 지금까지 바꾼 검은 방의 개수다. visited 배열에 바꾼 검은 방 개수를 저장하면서 만약 개수가 작으면 갱신하고, 크거나 같으면 무시하면 된다. 이떄 DFS, BFS 모두 가능하다. safe 함수를 써서 인덱스가 맞는 지 확인하는 것이 은근 편하다. 참고하자. bool safe(int a,int b){ return a>=0&&a=0&&b=0&&a=0&&b
2020.04.20 -
[도전 19일차] KOI 벽장문의 이동 풀이
※복습 : 문제 : 백준 2666 벽장문의 이동 문제 링크 사용 알고리즘 : 백트래킹 풀이: 벽장에서 n가지 벽장문 중 오직 2가지 문을 이용할 수 있다. 이때 2가지 문을 제외한 n-2가지 문들은 어떤 칸막이로 덮여 있는데, 이 칸막이들을 적당히 움직여 다른 문들도 이용할 수 있다. (그때마다 2가지) 현재 칸막이의 위치와 앞으로 이용하고 싶은 문들의 순서가 주어질 때 칸막이를 가장 적게 움직이고서 문들을 순서대로 모두 사용하는 것이 목표다. n이 20이하로 작으므로 가능한 모든 경우를 탐색하는 것이 가능하다. 이제 사용할 수 있는 문 중 왼쪽에 있는 것을 A 문, 오른쪽에 있는 것을 B문으로 하자. 내가 만약 k번째 문을 사용하고 싶다면 A문과 B문 중 하나를 사용해야 하는데, 사용해야 할 문은 여러..
2020.04.20 -
[도전 18일차] 로봇 조종하기 - KOI 고등부 풀이
※복습 : 문제 : BOJ 2169 로봇 조종하기 문제 링크 사용 알고리즘 : DP 풀이: DP에 오는 방향 정보를 포함하자. 로봇은 왼쪽, 아래쪽, 오른쪽으로만 이동할 수 있으므로 오는 방향은 오른쪽 , 위쪽, 왼쪽이다. 유의할 점은 오른쪽 방향 DT를 채울 때는 오른쪽에서부터 채우고, 왼쪽 방향 DT를 채울 때는 왼쪽에서부터 채워야 한다. 초기화 조건이 살짝 까다로운데 이는 직접 코드로 짜보는 수밖에 없다. 역시 미리 체계적으로 정해놓고 가면 디버깅이 빠르다. DT 정의 DT[i][j][k] =로봇이 k방향 ( 0:위쪽,1:왼쪽,2:오른쪽)에서 (i,j)에 도착할 때까지 얻을 수 있는 가치의 최대합. DT 관계식 $$DT[i][j][0]=max({DT[i-1][j][0],DT[i-1][j][1],DT..
2020.04.18 -
[도전 17일차] 숫자 박스 - KOI 고등부 풀이
문제 : 백준 1983 숫자 박스 문제 링크 사용 알고리즘 : DP KOI 2003 고등부 2번 풀이: (잡담이 싫다면 "하하 풀이를 보았다" 부분부터 보면 된다.) 빈칸에 들어있는 수를 0이라 할 때, 모든 열 위아래의 수들을 곱해 더한 합이 최대가 되도록 숫자를 움직이는 것이 목표다. 단, 각 행에서 숫자들의 순서는 유지되어야 한다. (저 박스를 잡고 적당히 좌우로 기울인다고 생각하면 편하다.) N이 400 이하로 작으므로 완탐을 돌릴 생각을 할 수도 있지만 불가능한 말씀이다. 매칭 경우의 수의 근사값은 400 C 200 * 400 C 200으로 1억과는 하늘과 땅 차이가 난다. 문제를 곰곰히 생각해보자. 위쪽 행에는 a개의 수, 아래쪽 행에는 b개의 수가 있다고 하자. 일반성을 잃지 않고 a DT[..
2020.04.17 -
[도전 16일차] 트리의 높이와 너비 - KOI 고등부 풀이
KOI 고등부 풀이 ※복습 : 문제 : 백준 2250 트리의 높이와 너비 문제 링크 사용 알고리즘 : 트리 순회 풀이: 기본적인 규칙은 모든 노드에 대하여 자신의 왼쪽 서브트리에 있는 노드들은 열번호가 작고, 오른쪽 서브트리에 있는 노드들은 열번호가 크다. 가장 먼저 관찰할 수 있는 사실은 루트에서 왼쪽으로 쭉 쭉 내려왔을 때 끝에 있는 노드가 열번호 1번을 차지한다. 같은 맥락으로 1번의 부모가 2번을 차지하고, 오른쪽 자식이 있을 때까지 올라간다. 오른쪽 자식이 있으면 오른쪽 자식으로 내려가서 다시 가장 왼쪽 자식을 찾아서 넘버링한다. 이 시행을 반복하면 모든 노드에 대해 열번호 넘버링이 끝난다. 결론 : 반복적 중위 순회 (Iterative Inorder Traversal) 와 규칙이 일치한다. 위..
2020.04.16 -
[도전 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 -
[도전 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