전체 글362 [백준] 1780번 종이의 개수 1. Feedback brute-force 로 풀음. 시간복잡도 O(n 제곱) 2. Source package acmicpc; import java.util.Scanner; /** * @author lee * *문제 : -1로만 채워진 종이 개수, 0으로만 채워진 종이 개수, +1으로만 채워진 종이 개수를 * 구한다. */ public class Num1780 { public static void main(String [] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int board[][] = new int[N][N]; for (int i = 0 ; i board[0].length) return new int[] {0,0,0};.. 2018. 6. 26. [HackkerRank] DP: Coin Change 1. Link to the problem https://www.hackerrank.com/challenges/ctci-coin-change/problem 2. Feedback 순서에 관계 없이 DP 를 이용하는 것이 핵심 기존 문제 푸는 방식대로 하면 cache[n] 으로 풀이가 될테지만, 이렇게 풀면 코인종류는 똑같은데 순서가 다른 것까지 포함되기에 이렇게 풀면 안됨. 중복된 것을 제거하기 위해 startIdx 를 도입하였고, 캐시를 이용하기 위해 cache[n][startIdx] 를 이용 함. 캐시를 사용함으로써 중복된 작업을 수행하지 않음. cache[n][startIdx] 의 의미는 n 에서 startIdx 로 시작할 경우, 중복된 것을 제거하고 값을 구할 수 있음. cache 가 int 값을 넘.. 2018. 6. 26. [HackkerRank] Recursion: Davis' Staircase 1. Link to the problem https://www.hackerrank.com/challenges/ctci-recursive-staircase/problem 2. Feedback [부분집합 문제] 재귀 사용 brute-force 로 푼다면, 재귀이기 때문에 n * n-1 * n-2 … 1 로 O(n의 제곱) 이 중 중복된 작업을 제거하고자 캐시 사용 3. Source public class RecursionDavisStaircase { private static int cache[]; public static void main(String [] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for (int testcase.. 2018. 6. 26. [HackkerRank] Hash Tables: Ice Cream Parlor 1. Link to the problem https://www.hackerrank.com/challenges/ctci-ice-cream-parlor/problem 2. Feedback Hash 를 이용해서 나머지 하나의 값을 찾는 것까지는 생각했는데, 중복 값 처리가 안될거 같아 이 방법을 포기 결국 중복 값이 HashMap 에 덮어쳐도 array 값을 이용해서 덮어쳐져있는 값을 불러오기에 중복 값 문제 해결 됨. 또 중요한 것은 array 의 index != map 의 value 와 일치하면 안됨. 같은 값이니 3. Source package hackerrank; import java.util.HashMap; import java.util.Map; import java.util.Scanner; publ.. 2018. 6. 25. [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. 이전 1 ··· 54 55 56 57 58 59 60 61 다음