본문 바로가기

ACM8

하노이탑 문제 풀기 하노이탑 문제 풀기 import lombok.extern.slf4j.Slf4j; @Slf4j public class Hanoi { public static void main(String[] args) { int count = hanoi(3, 1, 2, 3, 0); log.info("{}", count); count = hanoi(4, 1, 2, 3, 0); log.info("{}", count); } /** * 하노이탑 원리를 이해해야 함. * 1. n-1 를 두번째 기둥으로 옮기고. * 2. 첫번째 기둥에서 마지막 원판을 세번째 기둥으로 옮긴다. * 3. 두번째 기둥에 있는 n-1 원판을 세번째 기둥으로 옮긴다. * * 위 내용을 보면 n 번쨰 기둥을 옮기는건 n-1 번째 기둥을 옮기는 것을 풀어야 풀.. 2020. 11. 5.
HackkerRank: Time Complexity:Primality 1. Link to the problem https://www.hackerrank.com/challenges/ctci-big-o/problem 2. Point brute force 로 문제를 풀면 O(n) 이 나온다. U (Unnecessary Work) Math.sqrt 사용하여 불필요한 작업을 제거했다. Math.sqrt 를 사용한다는 의미는 n 의 루트를 씌움으로써 루트 n 이후의 불필요한 작업은 제거한 것이다. 왜냐면 루트 n * 루트 n 은 n 이기 때문이다. 위 결론에 따라 루트 n 이 prime 인지만 판별하면 되고, 루트 n 의 정수를 추출해서 i = 2 ~ 추출된 정수로 나눈다면 답이 나온다. 3. Source public static void main(String [] args) { S.. 2018. 6. 23.
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.
[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.

티스토리툴바