Archive

https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem BFS: Shortest Reach in a Graph | HackerRank Implement a Breadth First Search (BFS). www.hackerrank.com 풀이 그래프와 시작노드가 주어졌을 때 BFS로 다른 노드까지의 depth를 구하는 문제. 도달할 수 없으면 -1 리턴. BFS로 depth를 구할 때, 아래와 같은 순서대로 풀면 됨. 먼저 start_node를 정의(혹은 주어짐). 방문 정보를 저장할 visited 리스트 0으로 초기화. start_node에 대해서는 1로 처리 queue에 start_node 저장. depth는 dictionary를..

https://www.hackerrank.com/challenges/torque-and-development/problem Roads and Libraries | HackerRank Help the ruler of HackerLand determine the cheapest way to give his citizens access to libraries. www.hackerrank.com 풀이 그래프가 주어졌을 때 dfs로 전체 node를 방문하기 위한 경로를 세는 문제 첫 번째로 도서관 짓는 비용 c_lib이 길을 설치하는 비용 c_road보다 작을 경우 각 node에 도서관을 짓는다고 보면 됨. dictionary를 사용해 인접행렬을 구현했고, 방향이 없기 때문에 시작노드, 끝 노드를 각각의 valu..

https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 풀이 야근 시간 n시간, 처리해야할 업무 리스트 works를 입력으로 받음. 야근 지수 = n시간동안 works의 일을 처리(숫자 감소) 후 남아있는 원소의 제곱 합 n시간동안 매번 큰 수를 찾아서 1씩 감소시킨 후 제곱합을 구하면 됨. 리스트의 내장함수 [].index(element)는 O(n)이기 때문에 시간초과 남. "리스트의 max valu..

https://www.hackerrank.com/challenges/ctci-recursive-staircase/problem Recursion: Davis' Staircase | HackerRank Find the number of ways to get from the bottom of a staircase to the top if you can jump 1, 2, or 3 stairs at a time. www.hackerrank.com 풀이 계단을 1칸, 2칸, 3칸 올라갈 수 있을 때, n을 입력으로 받았을 때 가능한 모든 경우의 수 찾는 문제. 재귀함수로 풀지 않고, memoization으로 풀 수 있음. bottom-up으로 풀었고, 식은 next_step = next_step-1 + next..

https://www.hackerrank.com/challenges/candies/problem Candies | HackerRank Help Alice to save money by minimizing the total number of candies. www.hackerrank.com 풀이 2번 iteration을 사용. 오른쪽으로 iteration돌 때는 오름차순일 때 dp 값을 채워줌. 왼쪽으로 iteration돌 때는 내림차순일 때 dp값을 채워줌. def candies(n, arr): n = len(arr) # 최소값은 1로 문제에서 주어짐. dp = [1] * n for i in range(1, n): # 다음 원소가 더 크면 dp값을 증가해줌. if arr[i-1] < arr[i]: dp[..

https://www.hackerrank.com/challenges/abbr/problem Abbreviation | HackerRank Make two strings equal www.hackerrank.com 풀이 두 개의 문자열 a, b를 입력받음. 문자열 a를 다음 두 가지 방법을 사용해 문자열 b를 만들 수 있으면 "YES"를, 아니면 "NO"를 출력하는 문제 문자열 a의 소문자를 대문자로 0개 이상 바꿀 수 있음. 문자열 a의 소문자를 모두 제거. a = AbcDE, b = ABDE일 때, ABcDE로 b -> B로 바꾼 뒤, 소문자를 모두 제거하면 ABDE가 되므로 b를 만들 수 있음. Dynamic programming을 사용해서 품. 처음에는 대소문자 상관없이 a의 j번째 문자열 = b의..

https://www.hackerrank.com/challenges/max-array-sum/problem Max Array Sum | HackerRank Find the maximum sum of elements in an array. www.hackerrank.com 풀이 입력으로 정수로 구성된 arr를 받을 때, 이웃하지 않은 element와의 최대합을 구하는 문제 n1, n2, n3 3개만 있고 swap해가면서 정답을 구할 수 있음. 보통 dp[i] = i번째 원소까지 봤을 때 최대합 으로 생각해 문제를 접근 n2를 초기화할 때 arr[1]로 하지 말고 max(2번째 원소까지) 음수 값도 존재하기 때문에, i번째 원소가 최대인 경우도 있음. max 값을 update할 때 자기 자신이 최대인 경우도..

https://www.hackerrank.com/challenges/reverse-shuffle-merge/problem Reverse Shuffle Merge | HackerRank Given a string, find the lexicographically smallest substring that satisfies the given conditions. www.hackerrank.com 풀이 입력으로 문자열 s를 받을 때 아래 조건을 만족하는 알파벳 순으로 가장 앞선 문자열 A를 찾는 문제 s \in merge( reverse(A) , shuffle(A) ) merge 연산은 파라미터로 두 개의 string을 받는데, 각 string의 입력 순서만 맞으면 됨. merge( 'abac', 'bcbc'..