이진 탐색 트리 - 이진 탐색 트리를 중위 순회하면 정렬된 값들을 얻을 수 있다. - 삽입, 삭제가 일어나도 이는 유지된다.- 한 쪽으로 값이 쏠리는 불균형 이진 트리가 되면 연산의 시간복잡도가 O(N)에 가까워 진다.- 그래서 BST를 naive 하게 구현해서 해결하려고 했을 때 시간 초과를 볼 수 있었다. 풀이 방법 1. 삽입할 X의 위치를 찾는다. - 트리의 최솟값보다 작다면? 왼쪽 끝에 삽입하면 된다. - 트리의 최댓값보다 크다면? 오른쪽 끝에 삽입하면 된다. - 트리의 어떤 값 A, B 사이에 있다면? (A A의 오른쪽 서브트리 또는 B의 왼쪽 서브트리에 들어갈 수 있다.A, B 둘 중, 깊이가 큰 쪽을 기준으로 삽입하면 된다.직접 BST 를 그려보면 알 수 있다. 깊이가 ..
수학 + ... - 지문대로 해보면 식을 세울 수 있다. (x, y : 현재 위치 xi, yi : 조사점들 n : 조사점의 갯수) - 이 식을 빠르게 구하려면 정렬 + 이분 탐색, 부분 합 필요 - 푸는 방법이 꼭 이것만 있는 것은 아니다 ㅎㅎ; 풀이 순서 1. 입력 받은 조사점들을 크기 순으로 정렬한다.2. 부분 합을 구해 놓는다.3. 현재 위치 보다 큰 x, y 좌표를 찾는다. 그 좌표가 위 식에서 부호가 바뀌는 곳 이다.4. 식 대로 계산한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include #i..
다이나믹 프로그래밍 1. 사자를 배치하는 경우의 수는 왼쪽, 오른쪽, 배치 안하기 3가지 경우의 수2. 바로 윗칸에 배치된 경우는 배치할 수 없다. 3.왼쪽에 배치하는 경우의 수 = 직전 윗 칸의 오른쪽에 배치하는 경우의 수 + 직전에 배치 안하는 경우의 수오른쪽에 배치하는 경우의 수 = 직전 윗 칸의 왼쪽에 배치하는 경우의 수 + 직전에 배치 안하는 경우의 수 배치 안하는 경우의 수는 제약이 없으므로 직전 윗 칸의 왼쪽, 오른쪽, 배치 안하는 경우의 수를 합하면 된다. 식을 세워보면 D[100001][3] : D[행번호][왼쪽, 오른쪽, 배치x] D[i][0] = D[i - 1][1] + D[i - 1][2] : i행의 왼쪽에 배치하는 경우의 수 = i - 1행의 오른쪽 배치 + i - 1행의 배치xD..
브루트 포스 - CCTV의 좌표를 미리 저장해둔다. 그리고 완전 탐색 ㄱㄱ링- 코드를 수정하다가 연산자 하나 안 고쳐서 계속 틀렸다...실전에서도 이러면 꽤 곤란하다,,...,;; - 상하좌우 각각 확인하는 함수를 미리 만들어 놓으면 편하다. 계속 써야 하기 때문,, 소스 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611..
시뮬레이션 - 1번, 4번은 순서대로 보면 되지만 2번, 3번은 양 옆을 따로 봐야한다. 1번 톱니바퀴 이동 명령 1->2->3->44번 톱니바퀴 이동 명령 4->3->2->1 2번 톱니바퀴 이동 명령 2->1 // 2->3->43번 톱니바퀴 이동 명령 3->4 // 3->2->1 - 1번과 3번은 같은 방향으로 움직인다.- 2번과 4번은 같은 방향으로 움직인다. 소스 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #define FOR(i,a,b) for(int i = a; i 0;..
- Total
- Today
- Yesterday
- 컴퓨터공학
- 패스트캠퍼스
- c언어
- Fast Campus
- 개발자 취업
- 자료구조
- 코딩 면접
- 프로그래밍 온라인 강의
- 올인원 패키지
- #패스트캠퍼스 #프로그래밍대학생서포터즈 #올인원패키지 #컴퓨터공학 #성공하는프로그래밍공부법
- 운영체제
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |