MathTrauma

문제 링크 : https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 최대 최소 세그먼트 트리를 Bottom-Up 방식으로 구현해 보자. 이 경우에 이미 결과를 알고 있는 토너먼트 대진표를 보면 쉽게 이해가 된다. LOL, NBA 혹은 바둑 뭐든 상관없다. Rating 이 높은 쪽이 항상 이긴다고 가정하자. 우승한 팀부터 차례로 값를 줄여가며 각 팀에 rating을 부여하면 최대 세그먼트 트리가 된다. 혹은 랭킹을..

문제 링크 : https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 입력값의 컸기 때문에 걱정이 앞서서 한참 고민했던 문제이다. 그런데 결론은 효과적인 알고리즘이 필요없다는 것이었다. 절차 입력의 작은 수를 m , 큰 수를 M 이라고 하자. no 배열은 해당 수가 제곱수를 약수로 가지면 1 이고 아니면 0 이다. (우리는 0 의 개수를 세야 한다.) no[0] 은 m 이 제곱수를 가지는지 여부를 저장하고 no[M-m] 은 M 이 어떤..

Stirling Formula 여기서 보이고자 하는 주된 결과는 $$n!\approx \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$$ 이다. ($\approx$ 는 우변으로 좌변을 나누고 극한을 취하면 1 이 된다는 의미이다.) 이를 조금 더 정교하게 정리하면 $$n!=\sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n{e}^{{\theta }_n}|{\theta }_n|<\frac{1}{12n}$$ 가 된다. 경험상 이런 류의 결과들은 정확히 기억하는 것 쉽지 않다. 이미 포기하고 싶은 사람을 위해서 상대적으로 쉬운 것부터 준비했다. 1. $n!$이 $n^n$ 의 대강의 비교부터 이 비교는 굉장히 중요하다. 만약 알고리즘을 공..

1. 속성 존재 확인 객체는 여러 가지 정보를 모아둔 container 역할을 기본으로 한다. 따라서 내부에 어떤 정보가 있는지 확인할 수 있어야 한다. let obj = { id : 'trauma', test(){ console.log('Hi!'); } }; 1. 객체에 속성이 정의되지 않았다면 undefined 일 것이다. 이를 이용해서 특정 속성이 객체에 존재하는지 확인할 수 있다. 2. 우아하게 ' in ' 연산자를 이용해서 같은 일을 할 수 있다. obj.id !== undefined //true 'id' in obj; // true obj.address !== undefined //false 'address' in obj; //false 2. Object.hasOwnProperty( ) 'ha..

JavaScript에는 7 가지 자료형(data type) 이 있고 Object 를 제외한 6 가지는 primitive type 임을 언급했었다. 현재 얼렁뚱땅 6 가지 primitive 는 살펴보았고 Object 의 일종이지만 독립적으로 Array 도 다루었다. 이제 Object 에 대해서 기초적인 내용들을 정리해 보자. 1. 생성 앞서 다른 모든 타입처럼 constructor 를 이용한 생성과 literal 생성이 있다. 다음의 두 코드는 모두 빈 Object 를 생성한다. let obj = new Object(); let obj = { }; 사실 문법 공부할 때를 제외하면 constructor 로 생성해 본 적이 없고, 권장되지도 않는 듯하다. 이 글의 제목에서 알 수 있듯이 여기서는 Object ..

문제 링크 : https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 1. dp 의 정의 좌표 ( i , j ) 에 진입하는 방식에 따라 다음 움직임이 제한된다. 즉, 진입 방향을 기록할 필요가 있다. dir 은 진입 방향을 나타내는데 사용한다. (1, 1) 이 좌측 상단을 위미한다고 할 때, dir=1 은 위에서 아래로, dir=0 은 오른쪽에서, dir=2는 왼쪽에서 진입을 나타낸다. dp[i][j][dir]은 ( 1, 1 ) 에서 이동하..

문제 링크 : https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 1. dp 의 정의 dp[t][p][r] : t 시간에, p 번 나무 아래에서 움직일 수 있는 횟수가 r 번 남아 있을 때의 최댓값. 단, p 는 0, 1 값을 가지고 이는 1 , 2 번 나무를 뜻한다. 주인공 자두는 1 번 나무 아래에서 시작한다는 조건이 있는데 0 초에 0(1 번나무)에서 시작하는 것으로 설계하면 된다. 2. Transition 나무 위치 p 와 t 번째 입력(시간 t 에..

문제 링크 : https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net '수열 $a_1,a_2,\cdots ,a_k$ 을 $M$ 로 나눈 나머지가 같다.' 는 '임의의 i, j에 대하여 $a_i-a_j$ 가 M 으로 나누어진다' 와 동치이고 굳이 C\C++ 조건식으로 쓰면 (k-1) 개의 조건식 $$(a_1-a_2)\mathrm{\%}M==0$$ $$\cdots$$ $$(a_1-a_k)\mathrm{\%}M==0$$ 을 동시에 만족하는 것과 필요충분조건이다. ($M$ 에 관..