참으로 허탈한 문제. 아무리 생각해도 충분한 시간복잡도에 통과할 수 있는데, 시간초과가 났다. 그래서 개선된 속도로 풀어도 시간초과가 났는데.. 알고보니 입출력 시간 문제였다. 세 번으로 나누어서 풀었다. 처음이 가장 복잡도가 안좋은 방법. 그러더라도 문제를 풀기엔 충분한 스펙이였다. 문제는 입력 시간이였다. import sys input = sys.stdin.readline _n = int(input()) l = [ int(input()) for _ in range(_n) ] print( round(sum(l)/len(l)) ) sorted = [ f for f in l ] sorted.sort() print( sorted[_n//2] ) f = { } d = 0 for i in l: s = f.get..
Leetcode - Two sum problems has several approaches. first one is O(n^2) time complexity with two for loops. I'll not cover that approach in this post. 1 O(n log\_n) approach 1 sorting arrays. remind that origin index should be remained. 2 using two pointers, if sum value is same with target value then return it. 3 if sum value is larger than target value, then decrease tail pointer. If in op..
link https://codeforces.com/contest/496/problem/D Problem - D - Codeforces codeforces.com 흥미로운 문제다 테니스게임은 set라는 개념이 있다. 하나의 set은 어떤 플레이어가 점수 t를 달성하면 끝나고, 어떤 플레이어가 s개의 set을 이기면 테니스 게임이 끝난다. 프로그래밍 문제는 이 부분에 대한 질문이다. 만약 어느 게임의 스코어 정보만 남아있을 때 s와 t를 찾아낼 수 있는지에 대한 문제다. 다음 예를 보자. 5 1 2 1 2 1 5개의 숫자정보 아래 숫자 5개는 score를 낸사람의 번호다. 이 때 s와 t를 추론하는 것이다. naive 한 접근법은 모든 s 가능성을 탐색하자. s : from 1 to n. 만약 5개의 점수가..
참고문헌 나무위키 https://namu.wiki/w/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98%20%EB%82%98%EB%A8%B8%EC%A7%80%20%EC%A0%95%EB%A6%AC 중국인의 나머지 정리 - 나무위키 나눗셈 정리에 의하여 m=q⋅lcm(a1,a2,⋯ ,an)+rm=q\cdot\text{lcm}\left(a_1,a_2,\cdots,a_n\right)+rm=q⋅lcm(a1,a2,⋯,an)+r 을 만족하는 정수 q,rq,rq,r이 유일하게 존재한다 (0≤r≤lcm(a1,a2,⋯ ,an)0\leq r\leq\text{lcm}\left(a_1,a_2,\cdots,a_n\right)0≤r≤lcm(a1,a2,⋯,an)). 그런데 aia_iai가 mmm namu..
You are given a sequencea1,a2,…,ana1,a2,…,anconsisting ofnnnon-zero integers (i.e.ai≠0ai≠0). You have to calculate two following values: the number of pairs of indices(l,r)(l,r)(l≤r)(l≤r)such thatal⋅al+1…ar−1⋅aral⋅al+1…ar−1⋅aris negative; the number of pairs of indices(l,r)(l,r)(l≤r)(l≤r)such thatal⋅al+1…ar−1⋅aral⋅al+1…ar−1⋅aris positive; Print two integers — the number of subsegments with negat..
백준 2133 타일채우기 해설 흥미로운 문제이다. 정답을 미리 알거나 스포일링 당하는건 괴롭지만, ... 생각해나갈 때는 알쏭달쏭한 즐거운 문제였을 것이다.(구현문제보단 재밌는듯) 가로 길이 2 인 것을 만드는 경우의 수는 3가지이다. ( ||_ ),( _|| ), ( _ _ _ )이다. 임의의 길이 i를 만드는 데에는 i-2 길이를 만드는 경우의 수에 3가지 경우의 수를 조합하는 것이므로, f(i) = f(i-2)*2 이다. 그리고, 길이 4 이상부터 다음과 같은 형태를 만들 수 있다. 이러한 형태는 4, 6, 8, ... i 길이 만큼 만들 수 있고, 뒤집은 형태도 있기 때문에 각 길이마다 2가지의 경우의 수가 있다. 이를 종합하면 i를 만드는 경우의 수는 다음과 같다. f(i) = f(i-2)*2 ..
백준 14494 다이나믹이 뭐에요? 해설 n*n의 2차원 공간에서 오른쪽, 아래쪽, 우아래 대각 세 방법만 이용하여 이동한다고 하자. 이때 임의의 점 (x, y)에 도달 할 수 있는 경우의 수 f(x, y)는 f(x-1,y) + f(x, y-1) + f(x-1, y-1)이다. d배열을 1칸 크게 잡는다면 특별히 배열 range-exception 처리를 할 필요 없이 온전하게 연산에만 집중할 수 있다. #include #define MOD ((int)1e9+7) using namespace std; int d[(int)1e3+1][(int)1e3+1]; int main() { int n, m; cin >> n >> m; d[0][0] = 1; for (int i=1; i
백준 2037 문자메세지 해설 ABC, DEF, GHI, JKL, MNO, PQRS, TUV, WXYZ 가 각각 같은 번호를 눌러 입력해야하므로 이전에 동일한 번호를 눌렀다면 추가로 대기시간 W시간을 요구한다. 공백에 대해선 대기시간 W 이 필요하지 않다. BC, EF, HI .. 등에 대해선 여러번 눌러야하므로 P*required[알파벳]을 이용해 구할 수 있게 하였음. 입력 받는 것이 조금 까다로울 수 있다. ````C++ #include #include #include using namespace std; int a[26] = { 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9 }; int required[26..
백준 1463 1로 만들기 해설 Queue를 이용하여, 임의의 n 에서 1 까지의 이동하는 것을 구현하여서 최단경로 길이를 구할 수 있다. (BFS) 하지만 문제를 뒤집어서 생각해보면, n에서 1까지의 최단경로 길이는 다음 세개 중 하나이다. n/2 에서 1까지 가는 최단경로 길이 + 1 n/3 에서 1까지 가는 최단경로 길이 +1 n-1 에서 1까지 가는 최단경로 길이 + 1 아래는 memoization을 이용하여 문제를 해결한 소스코드이다. ````C++ #include #include #include using namespace std; int d[(int)1e6+1]; int go(int cur) { if ( cur = 0) return d[cur]; d[cur] = 1e9; if ( cur%2 ..
이 문제는 비교적 구현의 성격이 강한 문제이다. 해당 문제에 대해 포스팅을 남긴 이유는 삼성 B형과 성격이 비슷하기에 골랐다. 입력으로 들어온 단어들을 내 사전 (Trie) 로 저장해놓고, 4*4 배열을 규칙에 따라 순회하면서 생성된 단어를 Trie에서 탐색하는 것이 해당 문제의 풀이이다. 이 풀이 서술은 조금은 일반적인 서술로써, 구현에 대해 조금 구체적으로 이야기 해보려 한다. 1 트라이 with memory allocation 대부분이 알고있는 Trie 의 형태로써 Trie 노드가 자식 노드의 주소를 가지고 있는 것이다. 그리고 동적으로 관리하기 때문에 new, delete를 동반한다. 아래는 해당 문제에 대한 Trie 풀이 소스이다. 해당 문제 자체가 올림피아드 성격의 대회 문제이기에 구현성이 강..
- Total
- Today
- Yesterday
- Simulation
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 시뮬레이션
- 그라파나
- 아레나 시뮬레이션
- 이산수학
- 대규모 시스템 설계 기초
- 명제논리
- 이산 수학
- paul wilton
- 조합 코딩
- rosen
- Discrete Mathematics
- flutter
- 아레나
- beginning javascript
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- grafana cloud
- Trie
- 자바스크립트 예제
- javascript
- 최단경로 알고리즘
- Arena
- arena simulation
- 로젠
- 자바스크립트
- Propositional and Predicate Logic
- 백준
- 데이터 중심 애플리케이션 설계
- 아레나시뮬레이션
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
28 | 29 | 30 |