이전포스트브루트 포스순열과 조합 경우의 수 문제들 중에 대부분이 - 특정 크기의 집합으로부터 고유한 원소들을 순서를 따지면서 뽑으며 구성하는 경우의 수를 말한다. 또, 뽑은 순서는 상관없이 구성하는 경우의 수 문제도 있다. 5명 학생중에 3명을 선택해서 줄을 세우는 경우의 수는? --> 순열 4명 학생중 3명의 학생을 뽑는 경우의 수는? --> 조합 이게 바로 순열과 조합이다순열예제 15명 학생들 중에 3명을 선택해서 일렬로 줄을 세우려고한다. 이 때 이 경우의 수는 몇 개인가?정답우선 어떤 학생을 선택하는지에 대한 그 순서가 중요하다. 첫 번째에 줄서는 애를 뽑기위해선 5가지 경우의수가 있고, 그 친구가 선택되었을 경우에는 이제 두번째로 줄 서는 애를 뽑기위해선 4가지의 경우의 수가 있다. 그리고 두번..
이전 포스트경우의 수 덧셈규칙http://ingyeoking13.tistory.com/162 경우의 수를 이용한 알고리즘완전탐색 (Brute Force)완전탐색은 기본적이면서, 중요한 알고리즘 패러다임인데요. 완전 탐색 알고리즘의 사용할 때, 문제를 해결하는 방식이 굉장히 직설적입니다. "완전" 이라는 단어도 그렇지만, 해당 문제의 조건을 보면 알 수 있습니다 ㅇㅅㅇ.. 완전탐색 알고리즘은 그다지 좋은 알고리즘이 아닙니다. 왜냐하면 시간 복잡도가 지수 시간exponential time이기 때문이죠. 그래서 완전탐색을 사용한다는건 연산 장치의 리소스를 별로 신경쓰면서 문제를 해결하는 쪽은 아니라는 거죠. 일반적인 완전탐색 예로는, 모든 가능한 정답들을 검사해서 진짜 정답을 찾는겁니다. 제일 그럴듯한 정답을..
이전 포스트 보기 경우의 수 곱셈규칙경우의 수 덧셈규칙 The Sum Rule Definition 덧셈규칙어떤 업무를 완료하기까지 n1 가지 수로 된 방법 그리고 n2 가지 수로 된 방법이 있을 때, 업무를 완료 하는데 총 방법수는 n1+n2 이다. 여기서 n1과 n2는 어떠한 공통된 집합(즉, 부분 또는 원소) 이 없다. 덧셈규칙은 곱셈규칙과 전제가 다르다. 곱셈규칙은 어떤 사건이 and 연산자로 묶여있을 때 적용되며, 어떤 사건이 or 연산자로 묶여있으면 덧셈규칙이 적용된다. 아래의 그림을 확인하자. 나의 하루 (오늘)은 밥먹고 똥싸기로 이루어져있으며, 나의 내일은 밥먹거나 똥싸기로 이루어져있다. 작성자가 가족들한테 인정받는 주특기이다.곱의규칙 참고사이트 (곱의 규칙은 집합과 집합의 곱인 cartes..
백준 1, 2, 3 더하기본문보기https://www.acmicpc.net/problem/9095 이번 문제는 경우의 수 구하는 문제이다. 해당문제는 n중 for문으로도 풀 수 있고, 재귀를 이용한 dfs 탐색(트리탐색) 으로도 풀 수 있다. 하지만 또 dp풀듯이도 풀 수 있다. dp 풀듯이라는 뜻은 어쨋든 굉장히 큰 길이 또는 크기를 구하는 문제이지만 서도 낮은 숫자부터 차근차근 sub-answer들을 구해내서 귀납적으로 큰 값에 대한 답 real-answer를 구하는 것이다.이게 바로 sub-problem , overlapping 이라는 개념인데 나는 아직 이 개념에 익숙치 않아서 이 블로그를 포스팅 하는 이유이기도 하다. 이번문제에서 숫자는 어떻게 완성될까? 우선 이전 dp 문제들의 접근법을 확인해..
백준 2*n타일링 2본문보기https://www.acmicpc.net/problem/11727 dp문제. 경우의 수를 구하는 문제이다. 이 문제는 2*n 타일링 의 확장판 같은 문제이다. (브루드워?) 링크참조이번엔 약간 다른것이 있는데 2*2 타일이 있기 때문에 a[n-2]의 경우의 수가 2개가 된다.길이가 3일때를 생각해보자. 2까지 완성된 경우 세로로 길때 완성되는 경우와 1까지 완성된경우 가로로 긴 두개를 쌓아서 완성된경우, 2*2로 완성된경우 가 있다.an 이 n 까지 완성된 블록의 경우의 수라고하자. a3 은 a2+ a1+ a1 으로 표현할 수 있다.3부터 차근차근 경우의수를 기록해나가면서 다음 길이의 블록의 경우의 수를 구하려고하면 된다.낮은 상태에서 부터 높은 상태로 까지의 값을 기로고해나..
백준 2*n 타일링본문보기https://www.acmicpc.net/problem/11726 dp문제. 경우의 수 문제이며, 점화식을 구하는 문제이다. 이 문제의 형식은 다음 문제와 유사하다. n 길이의 비트스트링 문자열의 경우의 수를 구하여라. 단 0이 두개 이상 연속하면 안된다.우선 n길이의 비트스트링 문자열 경우의 수는 2^n 이다. 그런데 0이 연속되면안된단다. 확실히 2^n보다 작을것 같지만 경우의 수가 몇개인지 모른다. 여기서 접근법은 이전 문제(1로만들기)처럼 차근차근 접근하는 것이다. 문자열 3일 때의 경우의 수를 생각해보자.문자열 3일때의 경우의수는 3번째 수가 1인경우와 3번째 수가 0인경우로 표현할 수 있다. 3번째 수가 0일때에는 반드시 2번째 수는 1이 되어야한다. 그리고 물음표인..
백준 1463 1로만들기https://www.acmicpc.net/problem/1463 해설dp로 불어보았다. 문제를 딱 봤을 때 우선 음.. 확실히 3으로 나누는 것이 이동수를 크게 줄이는 이득부분이니까 나누는게 좋다. 라고 생각했고, n에서 1까지 내려가는 것을 연산하였다.그런데 반례는 예제에서도 있듯이 10은, 10 ->9->3->1 이 최소이동이며 내가 생각한대로 하면10->5->4->2->1 이므로 이동횟수가 하나 더 많았다. dp의 배열을 이용하면서 1에서부터 차근차근 해당수로 올라가면서 1에서부터의 최소거리를 구한다면 우리가 원하는 방식으로 알고리즘은 동작한다. 어떤 수 n는 default로 하나 작은 수[n-1] 에서 1을 더한만큼의 거리를 가진다. 그리고 그게 2로 나누어지고 d[n-1..
경우의 수영어로는 Counting이다. 수 세기. 셈법. 조합론. 등 으로도 불린다. 조합론은 무엇인가?1 무엇보다 이산수학에서 굉장히 중요한 분야 중 하나다.2 비교적 최근 수학이다. 17세기 즈음에 도박 확률 문제와 연관되어 정립되었다.3 주로 특정 상태의 어떤 것들을 세는데 사용한다. 예) 2개 이상 연속하는 0을 포함하지않는 0과 1로만 이루어진 n길이의 문자열 갯수는?4 이론적인 곳 외에도 굉장히 다양한 곳에서 사용된다.예) 알고리즘의 복잡도 구하기, IP 수요와 그 할당의 문제, DNA 염기서열 등등의... 앗 복잡해 어찌됐든 알아보기로 하자... 경우의 수 기초컴퓨터를 사용할 때 패스워드를 생성하는 것을 생각해보자. 패스워드를 생성하는데 최소 1개의 숫자를 포함해야하고 최대 8자의 소문자 알..
다트게임난이도 : 5/10어렵다. 구현이라는게 생각보다 어렵다. 어떨 땐 기초 BFS, DFS, dp 등의 문제가 쉽다 ... 가끔은 그렇다. (-.-....)... 아래 시계문제를 포스팅해서 갑자기 기억나서 또 비슷한 원문제를 포스팅했다. 내용보기https://www.codeground.org/practice/practiceProblemView 설명흠... 두가지가 중요하다. 1 에 선언된 atan2 함수의 사용atan2 는 c에서 지원하는 (gcc에서는 -lm 옵션을 붙여야함) 함수이다. atan2 에 대한설명보기http://egloos.zum.com/ForJustin/v/1199696 360도를 표현하려면 " atan(y,x) * 360 / PI "를 사용하여야한다.y축이 음수일 땐 각도가 음수이므..
868B Race Against Time난이도 : 5/10구현이지만 까다로운 문제이다. 원을 이용해 문제를 푸는건 익숙치 않다. 차라리 backtracking, dp, BFS 등 등 알고리즘 문제가 더 쉬울정도. 컨테스트에서는 풀지 못하였다. 아마도 블라인드 입사문제 (카카오)의 구현 급 난이도였다. 문제보기http://codeforces.com/contest/868/problem/B Race against time 이란 뜻은 굉장히 짧은 시간내에 무언가를 해내려고 한다는 뜻이다. 일분 일초를 앞다퉈... 라는 것과 비슷한 뜻 어쨌든 각설하고... 문제의 주인공이 misha는 space-time paradox라는 상황에 처해있는데, 이는 시공간이 서로 대체되는 특수한 상황이다. 이 상황속에서 misha는..
- Total
- Today
- Yesterday
- beginning javascript
- 아레나시뮬레이션
- 이산수학
- Propositional and Predicate Logic
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- 대규모 시스템 설계 기초
- 아레나
- 명제논리
- 그라파나
- flutter
- 이산 수학
- 항해99
- Trie
- Arena
- Simulation
- arena simulation
- 시뮬레이션
- 데이터 중심 애플리케이션 설계
- paul wilton
- 최단경로 알고리즘
- 아레나 시뮬레이션
- Discrete Mathematics
- 로젠
- grafana cloud
- 엄청난 인내심과 시뮬레이션을 위한 아레나 툴
- 자바스크립트
- rosen
- javascript
- 백준
- 자바스크립트 예제
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |