본문 바로가기

전체 글657

[201018] 티스토리 수익 창출 업데이트 티스토리 수익 창출 업데이트. ads.txt 문제 드디어 해결! 12일날 나온 소식인데 이제 확인했네. ads.txt 문제 관련 질문이 많긴 했나보다. 빨간색에 볼드 처리라니. 10월 중에 개선된다는데, 기대된다. 아주 좋군..! 2020. 10. 18.
[programmers][월간 코드 챌린지 시즌1] 트리 트리오 중간값 문제 : programmers.co.kr/learn/courses/30/lessons/68937 트리의 지름을 구하는 문제의 심화과정. 임의의 노드(let, v1)에서 dfs를 한 번 돌려서 가장 먼 노드(let, v2)를 구한다. (첫번째 BFS) v2 노드에서 가장 먼 노드들을 구한다. (두번째 BFS) 이 때 구한 가장 먼 노드들과 v2 노드의 거리가 트리의 지름이 된다. 만약 가장 먼 노드들이 복수 개(let, d1, d2)라면 f(v2, d1, d2)를 선택하면 이들의 중앙값은 트리의 지름이 되므로 정답은 트리의 지름이 된다. v2 노드에서 가장 먼 노드(let, v3)가 한 개라면 한 번 더 BFS를 돌려야한다. 왜냐하면 v2를 지름의 끝으로 트리의 지름을 만드는 노드들을 구했을 때는 v3 노.. 2020. 10. 18.
[programmers][월간 코드 챌린지 시즌1] 쿼드압축 후 개수 세기 문제 : programmers.co.kr/learn/courses/30/lessons/68936 크기가 2인 answer 배열을 하나 만들고 각각 0, 1일 때 크기를 저장한다. arr[sx~ex][sy~ey] 를 탐색하면서 모든 수가 같은지 확인하고 같다면 answer 배열을 갱신하고 같지 않다면 배열을 4분할로 나눠서 다시 판단한다. 이 때 n은 확인하고 있는 배열의 크기로 ex - sx값이라 한다. 1. arr[sx ~ ex - n/2][sy ~ ey - n/2] 2. arr[sx + n/2 ~ ex][sy ~ ey - n/2] 3. arr[sx ~ ex - n/2][sy + n/2 ~ ey] 4. arr[sx + n/2 ~ ex][sy + n/2 ~ ey] 이를 매열 크기가 1일때까지 반복하고 배.. 2020. 10. 17.
[programmers][월간 코드 챌린지 시즌1] 3진법 뒤집기 문제 : programmers.co.kr/learn/courses/30/lessons/68935 string third; while(n > 0) { third += n % 3; n /= 3; } int mul = 1; int answer = 0; // 뒤에서부터 탐색 for(int i=third.size()-1; i>=0; i--){ answer += mul * third[i]; mul = 3 * mul; } n이 0이 될때까지 n에 3나머지 연산한 결과를 문자열 앞에서부터 추가하고 n에 3을 나눈다. n이 0이 되었을 때의 문자열이 n을 3진법화한 결과이고 이를 앞뒤 반전하라고 했으므로 뒤에서부터 3의 i(i는 자리수-1)승을 곱한 수의 총합이 정답이 된다. 시간복잡도는 O(log3N) 소스코드 : g.. 2020. 10. 17.
[leetcode][189] Rotate Array 문제 : leetcode.com/problems/rotate-array/ Follow up에 적힌 공간복잡도 O(1)을 목표로 해보자. 예시로 나온 nums=[1,2,3,4,5,6,7], k=3을 예로 들어보면 일단 nums 배열은 모두 reverse 시킨다. nums=[7,6,5,4,3,2,1] 그리고 앞에서 k개의 원소를 reverse 시키고 nums=[5,6,7,4,3,2,1] k개 이후의 원소들을 다시 reverse 시키면 원하는 배열을 만들 수 있다. nums=[5,6,7,1,2,3,4] 이 때 k는 음수가 아니라는 말만 있고 nums 배열 크기보다 클 수도 있으므로 모듈러 연산해줘야 한다. k = k % |nums| 시간복잡도는 O(N). 공간복잡도는 O(1) 소스코드 : github.com/.. 2020. 10. 16.
[leetcode][701] Insert into a Binary Search Tree 문제 : leetcode.com/problems/insert-into-a-binary-search-tree/ 이진검색트리의 root 노드가 주어질 때 이진검색트리 조건을 만족하며 val 값을 넣어라. val 값은 이진검색트리에 없다고 가정한다. 이진검색트리 규칙대로 루트 노드부터 자식 노드들을 탐색하면서 val보다 탐색중인 노드 값이 작은 경우 오른쪽 자식, 큰 경우 왼쪽 자식으로 탐색해간다. 탐색중에 NULL인 자리를 만나면 val 값을 가지는 노드를 생성하여 트리에 연결한다. 시간복잡도는 O(logN). 소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/701.%20Insert%20into%20a%20Binary%20Search%20Tr.. 2020. 10. 6.

티스토리툴바