Archive

https://www.hackerrank.com/challenges/ctci-connected-cell-in-a-grid/problem DFS: Connected Cell in a Grid | HackerRank Find the largest connected region in a 2D Matrix. www.hackerrank.com 풀이 0과 1로 구성된 grid가 주어지면, 1을 기준으로 한 영역의 최댓값을 구하는 문제. 8가지 방향에 1이 있으면 같은 영역이라 가정.(왼쪽 대각선 위부터 시계방향) visited를 확인하기 위한 matrix 만들고, 방향 정보 리스트 만들고, stack을 사용해 dfs 구현하면 됨. def maxRegion(grid): n = len(grid) m = len(grid..

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/find-the-nearest-clone/problem Find the nearest clone | HackerRank Find the shortest path length between any two nodes with the given condition. www.hackerrank.com 풀이 그래프 정보와 각 노드의 색깔 저보가 주어짐. 특정 색깔을 입력받았을 때 같은 색깔의 다른 노드에 도달할 수 있는 최단 거리를 구하는 문제 먼저 adj_matrix를 만들어주는데, 파이썬의 dictionary를 사용. key : node, value : [인접 노드] 방향이 없기 때문에 graph_from, graph_to에 있는 노드를 번갈아..

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://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/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'..

https://www.hackerrank.com/challenges/special-palindrome-again/problem Special String Again | HackerRank Find Special sub-strings in a string. www.hackerrank.com 풀이 입력으로 문자열 길이, string이 주어졌을 때, 다음 조건에 만족하는 substring 개수를 구하는 문제 substring에 포함된 모든 문자가 같은 경우. ex) aaa substring의 가운데 하나를 제외한 양 옆의 모든 문자가 같은 경우. ex) aadaa ex) s = mnonopoo special substrings = {m, n, o, n, o, p, o, o, non, ono, opo, oo} ..