알고리즘 문제/Leetcode283 [leetcode][946] Validate Stack Sequences 문제 : https://leetcode.com/problems/validate-stack-sequences/ poped배열을 앞에서부터 탐색하면서 가능한 순서인지 체크한다. pushed : 1 2 3 4 5 poped : 4 2 5 3 1 를 예로 들어보자. pop할 값 stack에 들어간 값 아직 stack에 들어가지 않은 값 1 2 3 4 5 4 1 2 3 5 5 1 2 3 3 1 2 2 1 1 위 테이블을 보면 pop해야 할 값이 아직 stack에 들어가지 않았다면 pop할 값이 나올 때까지 stack에 값을 넣는다. pop해야 할 값이 이미 stack에 있다고 한다면 stack의 top에 해당하는 값이 해당 값이어야 한다.문제에서 조건을 보면 poped배열 크기와 pushed 배열크기는 같고 모든.. 2018. 11. 25. [leetcode][941] Valid Mountain Array 문제 : https://leetcode.com/problems/valid-mountain-array/ 배열 A의 크기가 3미만인 것들은 정답이 될 수 없다. (값이 증가하는 범위와 감소하는 범위가 존재하려면 적어도 3개의 값이 필요하므로)배열의 첫번째 값과 두번째 값을 비교했을 때 증가하지 않는다면 정답이 될 수 없다. (값이 증가하는 범위가 존재하지 않으므로)위 두 경우를 먼저 체크한다. 이후 배열의 연속된 값 2개를 비교하면서 다음을 체크한다.1. A[i-1] == A[i] : 값이 같은 경우 -> 정답이 될 수 없다.2. A[i-1] 이전에 값이 감소하는 경우가 나온경우 정답이 될 수 없다.3. A[i-1] > A[i] : 값이 감소하는 경우 -> 이후부터는.. 2018. 11. 25. [leetcode][938] Range Sum of BST 문제 : https://leetcode.com/problems/range-sum-of-bst/ BST는 왼쪽 자식 서브트리는 현재 노드보다 값이 작고, 오른쪽 자식 서브트리는 현재 노드보다 값이 크다.따라서 현재 노드의 val가 L보다 크다면 왼쪽 서브트리에도 정답이 될 수 있는 노드가 있을 수도 있다. -> 왼쪽 서브트리 탐색.현재 노드의 val가 R보다 작다면 오른쪽 서브트리에도 정답이 될 수 있는 노드가 있을 수 있다. -> 오른쪽 서브트리 탐색.루트 노드부터 위 조건에 맞는 서브트리를 탐색해 가면서 정답이 될 수 있는 수를 더해간다. 시간복잡도는 O(노드개수). 소스코드 : https://gist.github.com/fpdjsns/8818a1684ee7bb59abfb404ff6dd792e 2018. 11. 12. [leetcode][746] Min Cost Climbing Stairs 문제 : https://leetcode.com/problems/min-cost-climbing-stairs/ 기본 dp 문제.i 번째 계단으로 갈 수 있는 계단은 i-1, i-2번째 계단이다.따라서 i번째 계단으로 갈 수 있는 최소 비용은 (i-1번째까지 가는 최소 비용 + i번째 계단을 밟는 비용)과 (i-2번째까지 가는 최소 비용 + i번째 계단을 밟는 비용) 중 작은 비용이다.따라서 점화식은 아래와 같다.d[i] = min(d[i-1], d[i-2]); (d[i] = i번째 비용까지 가는데 드는 최소 비용) 시간복잡도는 O(N). 소스코드 : https://gist.github.com/fpdjsns/58c995f1439d437a2eed60bb517cb882 2018. 11. 11. [leetcode][129] Sum Root to Leaf Numbers 문제 : https://leetcode.com/problems/sum-root-to-leaf-numbers/ DFS로 풀었다.재귀함수를 만들어서(스택 사용 반복문으로 풀어도 됨) 자식노드로 가면서 합계를 더해나간다.만약 현재 노드가 리프노드(=왼쪽, 오른쪽 자식이 모두 없는경우)라면 이때까지의 합을 정답에 더한다.자식노드로 내려갈때는 현재까지의 합에서 *10을 해준다. 소스코드 : https://gist.github.com/fpdjsns/594442e85df0096e7b2f86f5fb120c15 2018. 11. 10. [Leetcode][934] Shortest Bridge 문제 : https://leetcode.com/problems/shortest-bridge/ BFS로 풀었다.먼저 배열을 탐색하면서 1 위치를 찾는다.찾은 위치를 시작점으로 BFS를 돌리면서 연결된 1을 2로 모두 바꾼다.바꾼 배열에서 아까의 시작점을 또 다시 시작점으로 하여서 BFS를 한 번 더 돌린다.이번에는 0을 1로 바꾼 횟수도 저장해야 한다. 따라서 이때의 너비우선탐색은 0 -> 1로 바꾼 횟수가 가장 작은것부터 먼저 탐색한다.다음 탐색 위치가 0이라면 탐색횟수+1을 한다.2라면 같은 땅이므로 탐색횟수는 이전과 같다.1이라면 현재까지 탐색한 횟수가 정답이 된다. 시간복잡도는 정확하게는 잘 몰겄지만 BFS를 2번 돌리니까 대략적으로 배열크기와 같다고 보면 될 듯하다. 소스코드 : https://g.. 2018. 11. 10. 이전 1 ··· 42 43 44 45 46 47 48 다음