topcoder SRM494 Div2 Level1 interesting party원 문제 주소 (로그인하고 하고 난뒤에 보임... 그냥 interesting party 로 검색하는게 더빠름)https://arena.topcoder.com/index.html#/u/practiceCode/14480/15196/11312/2/307028 공통된 단어를 찾는것이다.brute force 방식으로 전체탐색하면된다.n^2의 시간복잡도로 수행할 수 있다.n이 50까지였기에 망정이지만, 100만인경우 O(n)의 접근법으로 구현해야한다.그럴땐 맵 또는 딕셔너리 자료구조를 이용하면된다. C/C++ 소스보기https://github.com/ingyeoking13/algorithm/blob/master/topcoder/inte..
백준 1748 수 이어 쓰기 1 문제보기https://www.acmicpc.net/problem/1748 수를 n 까지 이어쓰는데, n까지 이어썼을 때 총 길이가 몇인지 세는 것이다.그래서 나는 len 함수를 만들어서 일일히 길이를 다 더해주기로 생각했다.함수는 log10 n 의 시간복잡도를 가지고, 총 n번 반복하니, n* logn 의 시간복잡도를 가지는 풀이이다. 좀더 멋진 풀이 방법이 있긴하다. 시간복잡도는 n이다.for 문을 딱 1번 1~n까지 순회하는데, i가 1~9까지는 1씩 길이가 더해지고, 10~99 까지는 2씩 길이를 더해준다.이렇게 하려면 int base = 10, cnt=1, ans=0;for (int i=1; i
Trie Introduction트라이는 자료를 찾는데 특화된 자료 구조이다. 트라이(Trie)의 어원은 retrieval (찾는다)의 중간글자 trie에서 유래되었다.트라이 자료구조는 종종 radix tree, prefix tree라고도 불린다. 앞 문자를 기준으로 차차 트리의 자식 vertex로 한글자씩 진행해 나가기 때문이다. 잘 이해하지 못 해도 다음 그림을 보면 이해할 수 있다.아래의 그림은 to, tea, ted, ten, a, in, inn 7 글자에 대해 트라이 자료구조로 만들어 본것이다. 위키피디아에서 퍼왔다. 이렇게 트라이 자료구조를 만드는 것은 내가 저런 단어들을 가지고 있어요~ 라는 뜻과 같다. 우리가 구현할 트라이 자료구조는 위 그림과는 좀 다르다.차차 더 읽어가면 트라이 자료구조에..
시작하기에 앞서특정한 입력값 집합으로 이루어진 문제에 대한 정답은 같은 문제에 대한 작은 입력 값 집합에 대한 정답으로 축소할 수 있습니다. (이것은 부분 문제subproblem 이라는 꽤 중요한 표현입니다.)예를 들어, 두 양의 정수 a, b의 최대공약수(GCD)를 구하는 문제를 생각해보자. 여기서 b>a. 이 문제는 더 작은 입력값인 b mod a 와 a의 최대공약수를 구하는 문제로 축소될 수 있다. 왜냐하면 gcd(b mod a, a) = gcd(a, b)이기 때문이다.이런 문제 축소가 수행될 수 있다면, 원 문제의 정답은 이런 축소된 문제의 흐름(좀 더 엄밀하게는 축소된 문제의 나열sequence of reductions) 속에서 찾아 낼 수 있다. 계속 축소하다보면 정답을 정확하게 알 수 있는 ..
내가 제일 약한 자료구조문제 http://codeforces.com/problemset/problem/911/E 자료구조문제는 자료구조를 응용해서 푸는 문제이긴한데, 그 동작이 영 익숙치 않다. 이번 문제는 다음과 같다. 한 개의 큐와 한 개의 스택를 이용해 하나의 배열로 정렬하여 두어야한다.문제는 그림으로 그려보면 대충 다음과같다.1과 2의 동작을 할 수 있는데 array에 반드시 sorting 되어야한다.그래서 문제 이름이 stack sorting 이다. 그래서 sorting 이 될수 없으면 -1을 반환해야한다. 문제가 여기까지이면 nice이다. (그래도 까다롭고 어려울 듯)그런데 문제는 이 요구사항에서 한 걸음 더 나가는데, 배열 size가 n이라고 할 때 단 k만 주어진다. 그래서 문제 input..
2차원평면에서 원의 방정식 응용 문제 컬링 게임을 하는데 컬링이 y=0인 지점부터 차곡차곡 쌓인다. 컬링은 x가 주어졌을때 (x, 10^100) 인 지점부터 y=0인 지점으로 가며 경로상에 동일한 컬링이 있을때 그곳에 부딪히고 멈춘다.입력이 주어진것부터 컬링을 하는것이며,인풋이 아래와 같을때 그림은 대충 저렇다.6 2 5 5 6 8 3 12 그런데 쌓이는 상태를 어떻게 저장해줘야 새로운 컬링을 그곳에 부딪힌다는 생각을 할 수 있기 때문에,나는 이 곳에서 막혔었다. 하지만 생각해보면 결국은 이미 사용한 컬링들은 (x,y) 를 저장하고 다음 새 컬링이 올때 그것을 참조하면된다. 그렇담 y는 어떻게 결정되는가? 두 원이 접하기 위해선 다음과같은 방정식을 만족해야한다.두 원의 반지름의 합 = 두 원의 원점 사이..
http://codeforces.com/problemset/problem/908/B 음... S사 입사 테스트 급 문제였다 ㅋㅋ굉장히 쉬운 문제였는데 숫자와 방향 맵핑에서 24가지의 경우의 수가 생성될 수 있는데 난 그것을 파악하지 못하고 4가지의 경우의 수밖에 생각하지 못했다. (항상 동서남북 순서대로 맵핑될 거라고 생가을 했기때문에 ...)testcase에 14개의 경우의 수가 나왔을 때 뭐였는지 몰랐다.하지만 생각보다 쉬운문제였다. ㅡ.ㅡ;;;하아 영어의 어려움이란 소스보기https://github.com/ingyeoking13/algorithm/blob/master/cf/implementation/908B.c
난이도 6/10DP문제, 특히 난이도가 높다고 생각한다. 특히 탑 구현? 부분 즉, dp 2차원을 어떤 정보로 memoization 할것인가가 크게 걸렸다. 나는 온전하게 문제를 풀지 못하였지만, 기억을 잃지 않으려고 포스트를 써본다. 각기 높이가 다른 블록이 여러개 주어지는데, 이것들로 두탑을 만드는데 두 탑의 높이가 같게 만든다.그런데 그것이 최대가 되는 지점을 생각해야한다. 최적화이다.인공지능이라는 어려운 주제를 구현하는 방법을 모르고,쉬운 방법을 원한다면 모든 경우의 수를 다 고려하는게 좋다, 그리고 가장 큰 특성치(두 탑의 높이가 같으며 최대 높이)인 지점을 찾는것.결국은 brute force와 그 지수복잡도를 해결하기 위한 subproblem의 만남이다. 즉 dp문제. 어떤 지점에서 subpr..
- Total
- Today
- Yesterday
- 백준
- 아레나 시뮬레이션
- javascript
- flutter
- 조합 코딩
- Trie
- grafana cloud
- Simulation
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- arena simulation
- rosen
- 자바스크립트 예제
- 이산수학
- 시뮬레이션
- Propositional and Predicate Logic
- Discrete Mathematics
- 이산 수학
- 아레나시뮬레이션
- 아레나
- 대규모 시스템 설계 기초
- 로젠
- beginning javascript
- paul wilton
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- 데이터 중심 애플리케이션 설계
- 그라파나
- 최단경로 알고리즘
- 명제논리
- Arena
- 자바스크립트
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |