Computer Science/Algorithm(14)
-
Leetcode - Maximum Depth of N-ary Tree
1. Root로 부터 시작된 경로 모두 다 탐색해야되구나... 2. DFS vs BFS 뭐가 빠를려나... 3. 짧은 경로 찾는게 아니라, 최장 경로니까 둘 다 똑같겠구나 4. BFS 오랜만에 써봐야지 5. 편-안 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 /* // Definition for a Node. class Node { public: int val; vector children; Node() {} Node(int _val, vector _children) { val = _val; children = _childre..
2019.10.13 -
Leetcode - Longest Increasing Path in a Matrix
어떻게 풀었는지? 1. 특정 배열에 방문하는 횟수가 여러번 생기겠네? 2. 이미 방문에 대한 결과를 가지고 있으면, 더이상 진행할 필요없는거 아니야? -DP로 풀자 3. 경로 탐색 DFS + DP로 풀자 4. 편-안 Hard 문제 같진 않다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 class Solution { vector dp; vector arr; int max_row; int max_col; i..
2019.10.13 -
정렬(Sorting) 알고리즘 정리
#선택정렬 (Selection Sort) -공간 복잡도 O(N)-시간 복잡도 O(N^2)-전체 배열의 최솟값 혹은 최댓값을 선택하여 왼쪽부터 차례대로 채워나가는 방식. #삽입정렬 (Insertion Sort) -공간 복잡도 O(N)-시간 복잡도 O(N^2)-2번째 index부터 진행함. 이전의 정렬되어진 배열에서 비교하여 자기 자리를 찾아감. +) 만약 정렬되어있다면?! O(N)시간을 가짐! #버블정렬 (Bubble Sort) -공간 복잡도 O(N)-시간 복잡도 O(N^2)-자신의 주변값들을 비교하여 Sorting #병합정렬 (Merge Sort) -공간 복잡도 O(2N)-시간 복잡도 O(NlogN) #퀵 정렬 (Quick Sort) -공간 복잡도 O(N)-시간 복잡도 O(NlogN) +) 만약 정렬되어..
2017.10.10 -
Knapsack Problem(배낭문제), BOJ 14728 벼락치기
https://www.acmicpc.net/problem/14728 이 문제 보자마자, Greedy문제로 풀려고 했다.왜냐하면, 많이 본 Greedy스러운 문제였기 때문에.... 그래서 Priority_Queue 써서, 공부시간이 많이 걸리는 과목별로 내림차순 정렬한 다음,T시간만큼 다 썼다면, Priority Queue에 있는 가장 Score가 가장 작은 놈이랑교체해주는 방식으로 했다. 틀렸길래 이해가 안되었는데, 생각해보면 우선순위 큐 안에 걸리는 시간 100 50 40 30 20 10Score 10 2 2 2 2 1 이 있고, 추후에 들어올 자료가각각걸리는시간, Score9 1005 200 이라면,이러한 상황에서 맨마지막 걸리는 시간 10을 빼는 것 보다20이나 30을 빼서 최적을 갖는 것이 더 바..
2017.10.08 -
11067 모노톤길
# 이분탐색, lower_bound, upper_bound 이용해서 품 우선 x와 y를 오름차순으로 정렬한다.C++ sort함수는 pair로 sorting할 때, 첫번째는 first를 기준으로, 그리고 first가 같을 때는, second를 기준으로 정렬한다. 맨 처음에는 0.0이 나오는 부분을 기억한다. 그 다음, 다음 카페로 이동할 때마다, 1) 수직선으로 이동할 수 있는 지를 고려한다.그 이유는, 만약 수직선에 길이 있음에도 불구하고, 수평선으로 간다면, 모노톤길이 생성이 안된다. 2) 수직선으로 이동할 수 없다면, 이제서야 수평선으로 이동한다. 문제의 조건을 잘 이해하지 못하고, 깨닫지 못해서 무식(?)하게 푼 것 같다.#include#include#include#include#includeusi..
2017.08.30 -
BOJ 1208 부분집합의 합 2
'부분집합의 합' 문제를 약간 변형시킨 문제이다.N이 40으로 증가하였다. 모든 부분집합의 수를 고려하려면 O(2^N)의 시간복잡도를 갖는다.2^40은 제한시간 1초에 통과를 하지 못한다. 이 문제를 푸면서 느낀 것은 어떻게서든 자신이 갖고 있는 알고리즘 능력을 총동원해서 최대한 풀려고 노력하자는 교훈을 얻었다. 단편적으로 어떻게 풀지몰라서 그냥 구글링해서 풀다가 반성하게 되었다. N이 크기 때문에,N을 절반으로 나눈다. A B로.그 다음,나누어진 집합의 각각이 나올 수 있는 부분집합의 합을 구한다.N/2 형태로 크기를 나누었기 때문에B 배열에 원소가 많을 것이다. B 배열로 알게 된 부분집합의 합들을 for문을 돈다.S-B의 부분집합의 합 = temp. 라고 한다면,A 배열로 알게 된 부분집합의 합들에..
2017.07.12