PS하는 깃털

각 α만큼 기울어진 빗면에서 θ의 각도로 초속 v0로 공을 던진다. 공의 출발 위치로부터 공아 밧면 위에 떨어진 지점까지의 거리가 최대가 되기 위한 θ와 이때의 최대 도달 거리를 구하여라. 이 문제를 풀기 위해 중력가속도와 초속를 빗면의 수직 성분과 수평 성분으로 분해해보자. 1. 빗면에 수직인 성분 빗면에 수직인 성분 관점에서 보면 초속도가 v0 sinθ이고 가속도가 -g cosα이다. 따라서 다시 빗면에 착지하기까지 걸리는 시간 t는 최고점까지 올라가는 시간의 2배이므로 아래와 같은 식이 성립한다. 2. 빗면에 수평인 성분 빗면에 수평인 성분 관점에서 보면 초속도가 v0 cosθ이고 가속도가 -g sinα이다. 운동을 t초동안 하므로 도달 거리를 R이라고 하면, 이러한 식이 나온다. 이제 이 값을 잘..

문제 링크 : https://www.acmicpc.net/problem/30928 30928번: Yokohama Phenomena Do you know about Yokohama Phenomena? The phenomenon takes place when three programmers, sitting around a table, hold a single pen together above a board. A grid of squares is drawn on the board, with each square marked with a single letter. Although none www.acmicpc.net 백준에서 대회 문제들을 찾아보다가 이 문제를 발견했는데 실버1이기도 하고, 재미있게 생겨서 시도..

문제 링크 : https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 문제 풀이 이 문제를 처음 도전할 때는 모든 사대에 대해서 잡을 수 있는 동물들을 카운트 해주는 Brute Force 방법을 쓸 수 있다(시간복잡도 O(MN). 그렇게 하면 M과 N이 100000이하이기 때문에 시간초과가 날 것이다. 그래서 다른 방법을 생각해보면 이부 분탐색이 떠오른다. 모든 동물에 대해서 조건을 만족하는 사..

문제 링크 : https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 문제 풀이 이 문제는 원 위에 정D1각형부터 정D2각형까지 그릴 때 중심에서 다른 점들에 의해 '가려지지 않는' 점들의 개수를 묻는 문제이다. 제한시간이 1초이고 D2가 2000이하이므로 넉넉하게 O(n^2)으로 해도 별 문제가 없을 것 같아보인다. 반지름이 D1인 원에서 부터 반지름이 D2인 원까지 각각의 원에 대해서 각각의 좌석들에 대해 모두 탐색을 해보자. 각 원에서 좌석들에 ..

이항게수와 관련된 PS를 하다가 범위가 큰 n과 범위가 큰 r에 대해서 nCr의 일의 자리 수를 구해야하는 일이 생겼다. 일반적인 콤비네이션 계산(O(n))을 하고 일의 자리수를 구하면 시간초과가 나서 다른 방법이 필요했다. 이 포스팅에서는 이와 관련된 내용을 적어보려고 한다. 1. 조합을 계산하는 일반적인 방법 가장 쉬운 방법으로는 정의식대로 n!, (n-r)!, r!을 모두 계산해주고 연산해주는 것이다. 하지만 n과 r이 조금만 커져도 계산 시간이 오래걸리고 PS에서는 정수형 범위나 심지어는 long long 범위까지 넘어갈 수 있기 때문에 좋지 않은 방법이다. int factorial(int n) { int output = 1; for(int i = 1; i >n>>p; k1 = p_digit(n,..

문제 링크 : https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 문제 풀이 이 문제는 초기 위치에서 시작해, 이전 변위와 현재 변위의 차가 1 이하가 되도록 이동하여, 마지막 위치까지 이동했을 때 이동 횟수의 최솟값을 묻는 문제이다. i번째 이동에서의 이동거리를 D(i)로 정의해보자. 이제 각각의 이동에 대해 D(i)를 최대로 할 수 있게 Greedy방법을 써보자. 현재 위치 current에 대해 D(..

백준 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net  오늘은 DP를 이용해 최장 증가 부분 수열의 길이를 구하는 코드를 구현해볼 것이다.최장 증가 부분 수열 : 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.ex)  A = ..

오늘은 크게 어렵진 않지만 그래도 생각해볼 가치가 있는 문제를 가져와보았다. 이 문제는 quant라는 곳에서 인터뷰 문제로 나온 적이 있다고 한다. One hundred people are in line to board a plane which has exactly 100 seats. Each passenger has a ticket assigning them to a specific seat, and the passengers board one at a time. The first person to board is drunk, picks a random seat, and sits in it. The remaining passengers board; if they find their assigned se..

PS를 좋아하는 사람이라면 한 번쯤은 Knapsack Problem에 대해 들어본 적이 있을 것이다. DP를 활용하는 대표적인 문제이기도 하고, 알고리즘을 공부하기에도 좋은 문제이다. Knapsack Problem : 주어진 물건들에 대해 그 가치와 무게가 주어져있을 때, 무게의 합이 담을 수 있는 최대 무게를 넘기지 않고 가치의 합이 최대가 되도록 배낭에 담기 위해서는 어떤 물건을 담아야하는가? 자세한 설명 : https://en.wikipedia.org/wiki/Knapsack_problem Knapsack problem - Wikipedia From Wikipedia, the free encyclopedia Problem in combinatorial optimization Example of a ..

높이가 h인 지점에 있는 질량 m의 물체를 벽에서부터 막대를 이용해 경사각이 θ인 경사까지 굴릴 때 걸리는 최소 시간은? 그리고 그때의 막대의 길이는? 문제만 놓고 보면 굉장히 쉬운 문제 같아보이지만 처음 접근할 땐 생각을 많이 해봐야한다. 이 문제를 풀어보기 전에 조금 더 쉬운 문제를 한 번 보자. 어떤 원에서 지표와 수직한 지름으로 공을 떨어뜨릴 때 걸리는 시간과 다른 호로 공을 떨어뜨릴 때 걸리는 시간이 같을까? 이건 자명하게 같다. 왜냐하면 둘 다 등가속도 운동을 하는데, 가속도의 비는 1 : sinθ이고, 거리비는 sinθ : 1이기 때문에 쉽게 알 수 있다. 그럼 이것을 이용해 이 문제를 풀어보자. 선분 PA를 지름으로 하는 원을 그리고, 그 원과 경사의 교점을 H라고 해보자. ∠PHA는 지름..