분류 전체보기(222)
-
세종 병원
https://code.sasa.hs.kr/problem.php?id=2452 풀이의 개요는 다음과 같다. 1. 손님들을 응급환자,예약환자,일반환자로 구분을 하여 각기 다른 큐에 집어넣는다. scanf("%d : %d") 를 이용해 시간을 효과적으로 입력받는다. 시간이 HH:MM꼴로 되어 있을 텐데 time = HH*60 + MM으로 나타내어 선후관계를 파악하기 쉽게 한다. 세종이의 '도착 시점'을 이때 기록해놓아야 한다. 2. 이때 큐는 '줄을 서기 시작하는 시점'을 우선순위로 하여 가장 빠른 사람을 dequeue하는 우선순위큐여야 한다. 우선순위큐의 원소는 구조체이며, 구조체간 비교 연산이 정의되어야 한다. 3. 환자들을 한명씩 진료한다. 이때 각 사람의 진료가 끝나는 시점을 기록하여 '현재 시간'을..
2020.06.22 -
첫 Codeforces
Codeforces Div.3에 처음으로 참여했다. https://codeforces.com/contest/1367 Dashboard - Codeforces Round #650 (Div. 3) - Codeforces codeforces.com A,B,C는 문제를 빠르게 읽는 것에 경각심을 느끼게 해주었다. D,E는 문자열 다루기에 익숙해지라는 것을 가르쳐주었다. F1,F2는, 내가 아이디어에 강하지만 애매한 구현을 더 연습해야 좋은 결과를 낼 수 있다는 조언을 주었다. 새벽에 재밌었다.
2020.06.17 -
시험 끝나고 PS
https://codeup.kr/problem.php?id=4488 트리회전 첫 번째 줄에는 입력되는 두 트리의 노드 개수를 나타내는 정수 N(5≤N≤300)이 주어지며, 각 노드는 1번 부터 N번까지 번호가 부여된다. 두 번째 줄부터 다음 N개의 줄에는 첫 번째 트리의 구조를 � codeup.kr 최근에 RB트리를 배워서 재밌어 보인다. https://codeup.kr/problem.php?id=4643 달팽이 첫째 줄에는 달팽이의 수 N(1≤N≤1,000)과 울타리 한 변의 길이(cm)를 나타내는 자연수 L(10≤L≤10,000)이 빈칸을 사이에 두고 주어진다. 울타리의 왼쪽 아래 좌표는 (0, 0)이고 오른쪽 위의 좌표는 (L, codeup.kr 광란의 기하 https://codeup.kr/prob..
2020.05.31 -
[Code SASA] 정독실에서 tic-tac-toe
https://code.sasa.hs.kr/problem.php?id=1067 SASA OJ 지원이와 진주는 기숙사에서 새벽에 정독실에서 tic-tac-toe를 두고 있습니다. 지원이는 흑돌, 진주는 백돌을 두고 있는데, 지원이는 진주 몰래 컴퓨터를 이용하여 각 자리마다 그 자리에 두었을 �� code.sasa.hs.kr 하루를 성공적으로 시작하게 해준 문제!!! 1. Tip => 코딩 문제 풀 때는 Pomotroid를 애용하자. 25분 코딩 - 5분 휴식 루틴! 2. 확률 계산이 중요한 문제. 처음에 turn에 따라 확률 계산을 다르게 해야하는 줄 알고 멘붕이 왔었다. 그런데 사실 turn은 그저 맵의 상태를 바꾸어주는 것일 뿐 실제로 돌을 두는 판단을 해야되는 시점은 오직 맨 처음 뿐이므로 쉽게 쉽게..
2020.05.23 -
지코 쇼미더머니 6 싸이퍼 가사
https://www.youtube.com/watch?v=VhLIPtZpApM [지코] Life is what you make of it 난 뭐든 한 페이지 일찍 넘겨 고등래퍼 때 이미 작업한 뒤 with swings and verbal 나의 잠재력 눈치 까고 서둘러 죽이려던 놈들 간곡한 부탁 다 거절 놓고 다음 광고 콘티를 훑고 있어 흥미없어여 집공개는 yeah 내가 날 가졌기 때문 yeah 네 정서를 배려하는 차원에서 수입에 대한 건 노코멘트 Go Back To 2014 아무도 몰랐지 편견은 반전 줄 때 효과 있지 I was 24 at ShowMe 4 and I be 26 at season 6 미디어와 내 안목을 합치면 it will be a big benefit 껄끄러운 인간관계는 정리해 난 여지 ..
2020.05.20 -
[Code SASA] 숫자 카드 게임
숫자 카드 게임 SASA OJ 첫 번째 줄에 카드의 개수(1
2020.05.15 -
한국정보올림피아드(KOI) 공부 시작하기
서론 안녕하세요! 비키라입니다. 저는 2020/03/29부터 KOI 전국본선 고등부 1,2번 문제들을 본격적으로 풀었습니다. (도전 내용) 도전을 시작할 때 채점이 가능한 1,2번 문제들을 전부 풀자는 목표를 세웠고, 먼저 백준 온라인저지에 있는 모든 KOI 고등 1,2번 문제를 문제집에 정리하였습니다. 2019년 최신 문제부터 1997년 문제까지 차례대로 나열되어 있으며 편한 순서대로 풀면 됩니다. 오래된 문제들은 대부분 인터넷에서 풀이를 찾을 수 없었는데 이 경우 오랜 시간 풀이를 찾아 헤멨고, 그러다가 KOI 공식 풀이를 찾아, 이를 참고하여 공부했습니다. 한국정보올림피아드 전국본선 문제들을 공부하시는 분들을 위해 고등부 1,2번 문제의 풀이를 정리합니다. 구성은 아래와 같습니다. 1. 날짜 2. ..
2020.05.01 -
[도전 30일차] 다각형의 확장 (도전중)
보호되어 있는 글입니다.
2020.04.30 -
[도전 29일차] 헬기 착륙장 - KOI 고등부 풀이
※복습 : 문제 : 백준 2626 헬기 착륙장 문제 링크 사용 알고리즘 : 기하 - 최소 외접원 풀이 : 이 문제는 '주어진 모든 점을 포함하는 최소 외접원 찾기'로 요약 가능하다. (ho94949님의 글, 최소 외접원 찾기에 정말 자세한 내용이 있다.) 외접원의 중심을 찾는 과정은 거리 함수 $$z={\sqrt (x^2+y^2)}$$가 볼록함수라는 것으로부터 출발한다. 위 그래프의 꼭짓점을 우리가 원하는 외접원의 중심 (Ax,Ay) 라고 하자. 임의의 점을 하나 잡고, (Ax,Ay)에 가깝게 가는 과정을 반복할 수 있다면 어떨까? 최종적으로는 Ax,Ay에 도착할 수 있을 것이다. 그렇다면 (Ax,Ay)에 가까운지는 어떻게 판단할까? (Ax,Ay)는 가장 거리가 먼 점과의 거리가 최소인 점이므로, 현재 ..
2020.04.29 -
[도전 27일차] 검은점과 하얀점 연결 풀이
※복습 : 문제 : 백준 2647 검은점과 하얀점 연결 문제 링크 사용 알고리즘 : Dynamic Programming 풀이: A[i] : i번째 점의 색깔 ( 0이면 하양, 1이면 검정 ) 1. X[i][j] => i번점부터 j번점까지 검은 점의 개수 X[i][j]*2 == (j-i+1) 이면 i,j 가 연결이 가능하다. X[i][j] = X[i][j-1] + A[j]로 구하기 그 다음 X[i][j]의 정의를 바꾸기 2. X[i][j] = i번점부터 j번까지 살펴보았을 때 i번점과 j번점의 개수가 같은가? X[i][j] = ( X[i][j]*2 == (j-i+1) ) 로 갱신. DP[i][j] : i번점부터 j번점까지 보았을 때 최소 연결 거리 H[i][j] : i번점부터 j번점까지 보았을 때 최소 연..
2020.04.27 -
[도전 26일차] 초고속철도 - KOI 고등부 풀이
※복습 : 문제 : 백준 2543 초고속철도 문제 링크 사용 알고리즘 : Dynamic Programming 참고 : KOI 공식 풀이 풀이: 기본적으로 DT 자체는 떠올리기 쉽다. DT[i] : 1~i번째 철도까지 보았을 때의 경우의 수 문제는 이 번째라는 것을 어떻게 정할 것인가이다. 이는 철도를 정렬하는 것으로 해결할 수 있다. 철도의 앞 구간을 a, 뒤 구간을 b라 하자. a를 기준으로 정렬한다면 살짝 불편해지는데 a가 작고 , b가 큰 구간이 존재해서 처음부터 끝까지 DT를 채우는데 영향을 줄 수 있기 때문이다. b를 기준으로 정렬하면 이 점이 해결된다. 지금 보고 있는 철도 앞에 있는 철도가 나를 포함하지 못하기 때문에 편하다. 이제 정렬이 끝났으니 DT 간 관계식을 생각해야 한다. i번째 철..
2020.04.26 -
[도전 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 -
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