본문 바로가기

algorithm64

HackerRank BFS: Shortest Reach in a Graph Problem Link : https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem 1. Thinking & Feedback 최단거리를 구하는 문제이기에 BFS 를 생각 Brute Force 로 푼 뒤 최적화를 생각 Start 지점 에서 노드 간 거리를 저장하는 방법에 대해서 고민 인접 edgeNum 을 조회하면서 배열로 저장해 값이 없는건 -1 로 출력하기로 함. while 문을 돌면서 Length 6씩 증가하는 방법을 사용하니 같은 레벨의 Distance 가 가중되면서 나오는 오류 이 문제는 이전 노드의 res[nodeNum] + 6 으로 해결. 왜냐하면 인접노드는 결국 서로 붙어있기에 이전노드 + 6 을 하면 같이 나옴. 2. So.. 2018. 3. 9.
HackerRank DFS: Connected Cell in a Grid (java) Problem Link : https://www.hackerrank.com/challenges/ctci-connected-cell-in-a-grid/problem 1. feedback Cache 를 적용할 수 없는 이유는 한 번 들른데를 또 들리기 때문이다. DFS 로 끝까지 탐색하고 최대 값을 찾는다는 개념 SImple 한 방법으로 푸는 방법 방문했다 다시 돌아오지 않고 한 번 방문할 때 연결된 Cell 을 모두 count 하는 방법. 메모리도 쓰지 않고 속도도 빠르고 심플함. 2. Source public class ConnectedCellInAGrid { private static boolean visited[][]; public static void main(String[] args) { Scan.. 2018. 3. 8.
HackkerRank: ARRAYS-LEFT ROTATION (JAVA) 1. Link to the problem https://www.hackerrank.com/challenges/ctci-array-left-rotation/problem 2. Point Use memory 3. Source public class ArraysLeftRotation { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int a[] = new int[n]; for (int a_i = 0; a_i 2018. 2. 27.
[BOJ] 9465 스티커 (java) [BOJ] 9465 스티커 (java) 1. point & feedback 행 0부터 시작, 열 0부터 시작 dp[0][N] : 0열에서 출발하여 (0, N) 위치까지의 score 의 합 dp[1][N] : 0열에서 출발하여 (1, N) 위치까지의 score 의 합 ex) (0,0) 에서 처음 시작했다면 다음 선택할 수 있는 수는 대각선 (1,1) / (1,2) 이다. (0,2), (1,2) 는 선택해봐야 최대 값이 될 수 없음 (0,0) -> (1,1) -> (0,2) 를 가면되니 최대 값이 될 수 없음. dp[0][N] = Math.max(dp[1][N-1], dp[1][N-2]) + score[0][N] ex) dp[0][2] 이라 하자. dp[1][1], dp[1][0] 중 하나를 고를 수 있음... 2018. 1. 30.

티스토리툴바