유블로그

프로그래머스 level 2 구명보트 시간초과로 시간이 거의 두 시간 가까이 걸렸던 것 같다... 정확성은 통과되기 어렵지 않았는데 효율성을 통과하기 어려웠다. 효율적인 코드를 짜는 것을 많이 연습해야할 듯 하다. 먼저 무게 오름차순으로 배열을 정렬하고, 제일 가벼운 사람과 제일 무거운 사람을 더해서 limit 내인지 보고 limit 내라면 보트 1개를 사용한다. limit 를 초과한다면 제일 무거운 사람을 보트 1개에 태우고 제일 가벼운 사람과 제일 무거운 사람 다음으로 무거운 사람을 더하여 비교한다. import java.util.Arrays; class Solution { public static int solution(int[] people, int limit) { int N = people.len..

프로그래머스 level 2 큰 수 만들기 제거할 인덱스를 k개 고르는 조합(재귀) 코드를 사용했는데 시간초과 때문에 처음부터 다시 짰다. StringBuilder를 사용했고, 현재 내 위치와 나의 바로 다음 위치의 숫자 크기를 비교하여 내가 더 작으면 나를 StringBuilder 에서 지우고 다시 그 위치부터 나의 다음 위치와 비교하는 방식이다. 그렇게 k개의 숫자를 제거하게 되면 끝냈다. 이렇게 간단한 코드를 생각을 못해서 약 3시간? 혹은 좀 더 ? 걸렸던 듯.. class Solution { public String solution(String number, int k) { StringBuilder sb = new StringBuilder(number); int N = number.length()..

탐욕법 level2 조이스틱 처음에 그리디 접근을 이용해 while문만 사용했다. 왼쪽으로 갈 때와 오른쪽으로 갈 때 이동횟수가 똑같으면 오른쪽으로 가게 했는데 그렇게 하니 안되는 케이스가 있어서 재귀로 바꾸었다. 왼쪽으로 갈 때 이동횟수가 더 적으면 왼쪽으로 가고, 오른쪽으로 갈 때 이동횟수가 더 적으면 오른쪽으로 가고 같으면 왼쪽, 오른쪽 둘 다 가보고 총 이동횟수가 더 적은 방법을 출력하도록 했다. public class Solution { static int N; static int[] word; public static int solution(String name) { N = name.length(); word = new int[N]; int[] me = new int[N]; for (int i..

- 대우 p->q 가 참이면 ~q -> ~p 도 참이다. - 멍청이 논리 틀린 명제를 참이라고 가정을 하면 어떤 명제도 참이 된다. (= F->()는 참이다! ) ex) "2가 홀수이면 5는 짝수다." 라고 했을 때 2가 홀수이면 5가 짝수 -> True 2가 홀수이면 5가 홀수 -> True : 2가 짝수인데 홀수라고 했으니 5를 홀수라고 우길 수 있다. 2가 짝수이면 5가 짝수 -> False 2가 짝수이면 5가 홀수 -> True Q) 만약 0이 홀수라면, 미국에서 2080년 월드컵이 열린다. -> true : 0이 홀수라고 거짓말했으니 뒤는 무조건 참 - 귀납법 기본형태 : P(1)이 참이고, P(n) -> P(n+1) 이 참이면 P(n)은 모든 자연수 n에 대해서 참이다. 강한형태 : P(1)이..

동적계획법 : 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘 최적화 문제는 최대값이나 최소값 혹은 경우의 수 등과 같은 최적값을 구하는 문제이다. 동적계획법은 먼저 작은 부분 문제들의 해들을 구하고 이들을 이용하여 보다 큰 크기의 부분문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법이다. 동적계획법은 중복 부분문제 구조, 최적 부분문제 구조 이 두 요건을 모두 만족해야만 사용할 수 있다. - 최적 부분문제 구조 : 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다. - 중복 부분문제 구조 : 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제를 해결한다. -> 점화식 사용 이전에..

- 최단 경로 : 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 - 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라(dijkstra) 알고리즘 : 음의 가중치 허용X, 그리디 알고리즘의 일종. 벨만-포드(Bellman-Ford) 알고리즘 : 음의 가중치 허용. - 모든 정점들에 대한 최단 경로 플로이드-워샬(Floyd-Warshall) 알고리즘 시작정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다. 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다. s: 시작 정점, A: 인접행렬, D: 시작정점에서 자신 정점까지의 최단 거리 V: 정점 집합, U: 선택된 정점 집합 Dij..

- 간선 수가 많을 때 kruskal 알고리즘은 불리하다. - 간선 개수에 비해 정점의 개수가 적은 경우 정점 중심인 Prim이 유리할 수 있다. (불리한 경우도 있음) - 간적쿠 간만프 ! (간선적으면크루스칼, 간선많으면프림) - Prim : 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식 - 과정 1. 임의 정점을 하나 선택해서 시작 2. 선택한 정점과 인접한 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 3. 모든 정점이 선택될 때까지 1, 2 를 반복 + MST만들기 위해 선택된 정점과 선택되지 않은 정점들 정보를 유지 public class PrimTest { public static void main(String[] args) throws Exception..