하이 나윤

문제 최초 풀이 -> 이진수로 바꿔서 문자열 형태로 가져온 후 반복문으로 문자 요소 중 1의 개수를 세었다.중간 풀이 -> 이진수로 바꾸는 과정에서 1이 있으면 세었다.최종 풀이 -> 비트 연산자를 사용하였다. 최종 풀이(3ms)n & 1 -> 이진수의 1의 자리에 1이 있는지 체크n >> 1 -> 나누기 2, 이진수에서는 오른쪽으로 한칸씩 미는 것class Solution { public int[] countBits(int n) { int[] result = new int[n + 1]; for(int i = 0; i > 1; } return result; }}  중간 풀이(8ms)class Solution { public int[] co..

문제 맨 아래 칸부터 하나 혹은 두 칸씩 올라가면서 최소 칸 수를 메모하며 올라간다. class Solution { public int minCostClimbingStairs(int[] cost) { int start = 0; int top = cost.length + 2; int[] m_cost = new int[top]; for(int i = 0; i m_cost[start + 1] + minimum[start]) { minimum[start + 1] = m_cost[start + 1] + minimum[start]; } if (start + 2 m_cost[start + 2]..

링크 DP(Dynamic Programming)하나의 큰 문제를 작은 문제로 나누어 해결하는 기법 동적프로그래밍을 사용하는 대표적인 문제가 피보나치 수열이다.f(n) = f(n - 1) + f(n - 2) (n > 2), f(0) = 0, f(1) = 1 위의 수열을 해결하기 위해 재귀적으로 문제를 해결할 수도 있지만 중복 실행이 발생하게 되고 n이 커지면 커질수록 비효율적이다.따라서 f(0), f(1)을 배열에 저장해서 한번 구한 값을 또 구하지 않도록 아래와 같이 f(n)을 구할 때까지 반복적으로 연산을 진행한다.  DP를 사용해서 문제를 풀기 위해서는 문제를 작은 문제로 나누고 이 결과를 이용해서 동일한 작은 문제를 해결하도록 해서 소문제를 재사용해야한다.즉, 비슷한 여러 개의 소문제로 나눌 수 있..

링크 이진탐색이란 정렬된 배열에서 가운데 숫자를 고른 후, 찾으려던 숫자보다 작으면 가운데를 기준으로 앞의 절반 배열을 버리고 크면 가운데를 기준으로 뒤의 절반 배열을 버린 후 다시 가운데 숫자를 뽑아서 찾고자 하는 숫자를 찾아가는 탐색이다. 가운데 숫자를 고를 때는 배열 내 가장 작은 인덱스 + (가장 큰 인덱스 - 가장 작은 인덱스) / 2 로 찾는다./** * Forward declaration of guess API. * @param num your guess * @return -1 if num is higher than the picked number * 1 if num is lower than the picked number * othe..

링크class Solution { public static Map map; public static List result; public static String[] temp; public static int len; public List letterCombinations(String digits) { len = digits.length(); temp = new String[len]; result = new ArrayList(); map = new HashMap(); map.put("2", new String[]{"a", "b", "c"}); map.put("3", new String[]{"d", "e",..

링크/** sort가 없는 상황에서는 heap, priority queue를 쓰면.. 이러한 상황을 극복할 수 있다.. */import java.util.PriorityQueue;import java.util.Collections;class Solution { public int findKthLargest(int[] nums, int k) { PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); for(int n: nums) { pq.add(n); } for(int i = 0; i

링크import java.util.*;class Solution { public int nearestExit(char[][] maze, int[] entrance) { int result = -1; Queue queue = new LinkedList(); int m = maze.length; int n = maze[0].length; int[][] visited = new int[m][n]; for(int i = 0; i r.route + 1) { visited[r.x + 1][r.y] = r.route + 1; queue.add(new Route(r.route + 1,..

링크 import java.util.*;class Solution { public static boolean[] unlocked; public static List> room; public boolean canVisitAllRooms(List> rooms) { int size = rooms.size(); room = rooms; unlocked = new boolean[size]; unlock(0); boolean result = true; for(boolean check: unlocked) { if (!check) { result = false; ..

링크/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { static int max; public int ma..

링크class Solution { public int largestAltitude(int[] gain) { int start =0; int highest = 0; for(int i = 0; i highest) { highest = start; } } return highest; }}