algorithm63 [HackkerRank] Bit Manipulation: Lonely Integer 1. Link to the problem https://www.hackerrank.com/challenges/ctci-lonely-integer/problem 2. Feedback A = {a1, a2, a3, a4, … ,an} 은 홀수이며, 2개 이상 짝을 이루며, 오직 하나의 수만 유니크 XOR 이란 2개의 명제 중에서 1개만 참인 것을 추출하는 bit manipulation 이다. 모든 수를 XOR 한다면, 같은 pairs 는 비트가 0으로 될테고, 유니크한 값의 비트만 1의 비트가 켜진다. 3. Source public class BitManipulationLonelyInteger { public static void main(String [] args) { Scanner sc = new Sca.. 2018. 6. 25. [백준 알고리즘] 1927번 최소 힙 1. Point Heap 자료구조 시간복잡도 삽입 : 맨 마지막 Index 에 넣고, 부모 노드랑 비교. 부모 노드 비교 식은 (index -1) / 2 로 1/2 씩 비교하게 되니 logN 이 됨. 삭제 : 맨 마지막 Index 를 Root 로 옮겨서, 자식 노드 2개씩 비교해가면서 내려가니 logN 이 됨. 2. Source public static void main(String[] args) { PriorityQueue queue = new PriorityQueue(); Scanner sc = new Scanner(System.in); int N = sc.nextInt(); for (int idx = 0 ; idx 2018. 6. 25. 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 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. 이전 1 ··· 11 12 13 14 15 16 다음