Difficulty : 4/10I could'nt solve this problem during the contest.but It is not difficult problem. This problem is brute force. first, you can try all combination of n-1 kayaks. but choosing 2 kayaks that soley drive is much easier. okay, then you could think about combination of n-1 tandem kayaks. here the greedy comes in. to minimize instability, you should choose two that have similar weight...
Difficulty : 4/10I couln't solve this problem during the contest.but It is not a difficult probelm. this problem can be solved in various way. I solved it with "union find algorithm". because union find is good algorithms to express "disjoint set". but the problem has a constraint. It is a "all station has just two degree, Just in and out".so it can be solved with just loop using parent, visit a..
문제 보기https://www.acmicpc.net/problem/1717 기본적으로 Disjoint를 알면 쉬운문제, 근데 애초에 엘리먼트 크기가 1,000,000 이므로 disjoint 말고는 풀수 있는 경우가 딱히 없을듯하다. 대표적인 Dis-joint set 문제이다. 또는 Union Find 문제라고도 불린다. disjoint 는 집합에서 공통된 원소가 없을 때 두 집합이 disjoint 하다고 표현한다.일단 제 포스트보다 더 설명 잘되있는 곳을 소개해드립니다.https://ko.wikipedia.org/wiki/%EB%94%94%EC%8A%A4%EC%A1%B0%EC%9D%B8%ED%8A%B8-%EC%85%8B_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0http://koo..
난이도어려울뻔했는데 난이도는 3/10문제보기http://codeforces.com/problemset/problem/879/B n 명의 사람들이 탁구를 치는데, 일렬로 서서 게임을 하게된다. 맨 처음엔 게임은 첫 사람과 둘째 사람이 하게되는데 이긴사람은 그대로있고 진 사람은 줄의 맨 뒤로 가게된다.어떤 사람이 k번째 이기면 게임은 종료되며, 이기고 진다는 판정은 입력받은 각 플레이어의 힘ai으로 결정된다.출력은 k번 승리한 플레이어의 힘을 출력하면 된다.2
이전 포스트순열과 조합 : 조합의 구현 헤헤헤. 사실 계획대로라면 dp 문제를 들어가야했지만 하나를 제대로 하는 것이 중요하다고 생각해요. 그래야 다른 응용문제도 잘 풀 수 있을테니까 말이죠.우리는 조합을 구현하는데 두 가지 방법을 썼습니다.1 첫 번째는 비트스트링과 순열을 활용한 조합방법 ( 010101011100)2 두 번째는 조합 인덱스를 생성해내는 알고리즘 (2,4,6,8,9,10) 이제 나머지 두 방법을 살펴볼건데 3 DFS를 이용한 조합 경우의 수 찾기 (모든 경우의 수도 가능함)4 비트마스크를 이용한 조합 경우 찾기 (모든 경우의 수도 가능함)방법은 알고리즘 문제를 푸는데 자주 사용하는 것입니다. 그치만 너무 귀찮군요. 푸하하... 대신에 문제를 두개 준비해보았습니다.백문이 불여일견이니까....
이전포스트순열과조합: 순열의구현 순열과 조합, 조합의 구현 이전 포스트에서는 순열을 구현해 보았는데요, 순열의 특징은 사전순으로 정렬하는데 있습니다. 그렇다면 조합의 경우는 어떨까요? 우선 조합은 다음과 같은 특징을 같습니다. 비트스트링을 생각해보죠, 해당 원소가 포함되는 곳엔 1, 아닌 곳은 0이 됩니다. 아래그림을 확인해보죠. r-조합은 기본적으로 n개 중 r개를 선택한 원소들의 고유한 집합입니다. 따라서 위와 같은 비트 스트링으로 포함, 비포함으로 표현할 수 있습니다. 자, 우선 모든 조합을 고려해보죠.그러니까 비트스링의 모든 경우의수요. 그렇다면 경우의수는 2^n 가지 입니다. 자, 우선 간단한 예제를 풀어볼까요?예제 41010111 의 다음 비트스링은 뭔가?정답1010111의 다음 비트스트링은 ..
이전포스트순열과조합 순열과 조합의 구현 반복을 허용하는 순열은 저희가 했던 브루트 포스 와 같습니다. 브루트포스 보러가기즉, 4자로 이루어진 비밀번호가 있는데 소문자 알파벳으로 이루어져있음 그 경우의 수가 26^4이죠. 반복을 허용하는 순열의 경우는 이와 같습니다. 자, 근데 이제 어떤 중요한 정보를 얻었다고 합시다.비밀번호의 알파벳들이 겹치지 않는다는 정보요. 그렇다면 26^4 -> 26*25*24*23 으로 경우의수가 줄어듭니다. 그렇담 순열대로 알고리즘을 생성해내는게 더 효율적이겠죠. 근데....순열 알고리즘은 어떤거죠? 생각보다 어렵지 않습니다. 순열을 생성해내는 것은 사전식으로 정렬 하는것과 똑같습니다. 어떤식으로 정렬을 해야할까요a, b, c, d 의 다음순열은 a, b, d, c 입니다. 자..
- Total
- Today
- Yesterday
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- Trie
- javascript
- paul wilton
- 자바스크립트 예제
- 아레나시뮬레이션
- 아레나 시뮬레이션
- 아레나
- 이산 수학
- 로젠
- 명제논리
- 최단경로 알고리즘
- Discrete Mathematics
- 대규모 시스템 설계 기초
- Propositional and Predicate Logic
- arena simulation
- 항해99
- Simulation
- 데이터 중심 애플리케이션 설계
- 시뮬레이션
- 그라파나
- grafana cloud
- 자바스크립트
- Arena
- beginning javascript
- 백준
- rosen
- flutter
- 이산수학
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |