알고리즘 문제408 [Codeground][74] 버스타기 문제 : https://www.codeground.org/practice/practiceProblemViewNew 5 3 1 4 3 7 9을 예로 들어보자. 일단 오름차순으로 정렬한다.1 3 4 7 9첫번째 수 1과 같은 버스를 탈 수 없는 바둑 기사와 같이 탈 수 있는 바둑기사를 나눠보면 다음과 같다.1 3 4 7 9차이가 작은 수들이 같은 버스를 탈 수 없다. 따라서 1과 같은 버스를 탈 수 없는 바둑 기사들은 각자 누구와도 같은 버스를 탈 수 없다. (정렬했기 때문에 빨간색 범위 내의 능력차이는 항상 3(4-1)보다 작다.)즉, 1 3 4는 각자 다른 버스를 타야하고 따라서 적어도 3개의 버스가 필요하다. 나머지 7과 9는 1번이 탄 버스에 같이 타면 되므로 같이 탈 수 없는 바둑 기사의 수만 고려.. 2018. 11. 16. [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. [leetcode][933] Number of Recent Calls 문제 : https://leetcode.com/problems/number-of-recent-calls 조건에 t는 점점 커진다고 적혀있다.따라서 한 번 범위에 포함되지 않는 핑은 앞으로도 계속 포함되지 않을 것이다.최소 범위는 t - 3000인데 t가 계속 커질 것이므로 t-3000도 계속 커질 것임.따라서 한 번 ping < t - 3000 가 된 ping은 앞으로도 최소 범위 t -3000 이전 값이 된다. 큐를 이용한다.ping 함수에서 받는 t를 큐에 저장한다.큐의 앞에서부터 t - 3000 보다 작은 것은 제외 시킨다. 다 제외 시켰을 때 큐의 크기를 반환시킨다. 시간복잡도는 O(N) 일 듯. N은 입력에서 받는 ping 함수 개수. 소스코드 : https://gist.github.com/fp.. 2018. 11. 9. 이전 1 ··· 63 64 65 66 67 68 다음