전체 글

[알고리즘] Dynamic Programming(동적 계획법)

1. DP란? DP(Dynamic Programming)은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로, 이미 했던 연산이 반복되는 결점을 보완하기 위해서 고안되었다. 피보나치 수열에서 사용되는 일반적인 재귀 방식도 DP와 매우 유사하지만, 일반적인 재귀 방식은 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수도 있다는 것이다. Dynamic Programming 문제를 풀기 위한 방법에는 Top-Down과 Bottop-Up 방식이 있는데, 아래에서 알아보겠다. 2. Dynamic Programming 구현 2-1 Top-Down 방식 Top-Down 방식이란 재귀 함수로 다이나믹 프로그래밍을 구현하는 방식이며, 말 그대로..

[알고리즘] 벨만포드 알고리즘 (Bellman-Ford)

1. 벨만포드(Bellman-Ford) 알고리즘이란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 + 음수 사이클 존재 여부를 알 수 있음 다익스트라와는 달리 가중치에 음수가 있어도 사용 가능 시간복잡도: O(NE) (N:노드의 수, E:엣지의 수) 다음과 같은 그래프가 있다고 가정 다익스트라로 노드 1에서 모든 노드로의 거리를 구하면 1 -> 2 = 1 1 -> 2 ->3 = 2 1-> 2 ->3 ->4 = 4 가 되고 노드 2는 이미 방문했기 때문에 4 ->2 경로는 고려하지 않음 결과적으로 1 -> 2의 최단경로는 1이 됨 하지만 실제 1 -> 2의 최단경로는 -∞ 임 이를 해결하기 위해 벨만포드 알고리즘 탄생 2. 알고리즘 동작 원리 시작 정점을 선택한다. 모든 간선들을 탐색하면서..

[알고리즘] 그리디 - 최소 스패닝 트리(Minimum Spanning Tree)

그리디(Greedy) 알고리즘 들어가기에 앞서, 그리디 알고리즘에 대해 간략히 알아보자. 그리디(탐욕) 알고리즘 이란? => 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘이다. = 탐욕 알고리즘 빠르지만, 항상 최적인 답이라는 보장은 없다. Union-Find 알고리즘 Disjoint-set(서로소 집합)을 표현하기 위해 사용하는 알고리즘 ex) {1,2} {3,4} → 서로소, {1,2} {2,3} → 서로소 아님 (1). Union 2개 원소로 이루어진 집합을 하나의 집합으로 합치기 ex) {1} + {2} → {1,2} (2). Find 특정 원소가 속한 집합이 뭔지 알려주는 연산 ex) Find({ {1,2,3}, {4,5}, {10} }, 2) → {1,2..

Java) 2차원 배열 오름차순 정렬(Arrays.sort 람다식)

Java Array Sort 자바에서 1차원 배열을 오름차순 하기위해서는 Arrays.sort() 메서드에 인자로 배열을 넣어서 사용하면 되지만, 2차원 배열을 오름차순 하려면 Arrays.sort에서 람다식을 이용하여 구현할 수 있다. 1차원 배열(int) 정렬 - 오름차순, 내림차순 여기서 잠깐 1차원 배열(정수형) 오름차순, 내림차순 정렬하는 방법에 대해 코드로 간단히 알아보자. # 오름차순 정렬 int[] arr = {1, 26, 17, 25, 99, 44, 303}; Arrays.sort(arr); >>>>>결과: [1, 17, 25, 26, 44, 99, 303] 1차원 int형 배열의 오름차순 정렬은 비교적 간단하지만, 내림차순 정렬은 상당히 까다롭다. int형 배열이 아니라면, 아래와 같이..

Java) HashMap의 computeIfAbsent에 대해(feat. getOrDefault)

getOrDefault 우리가 흔히 알고 있는 map의 메서드중 getOrDefault 메서드는 키값이 없으면 두번째 인자를 반환하는 것으로 알고있다. 평소에 코딩 문제를 풀때, Map 같은 map에 key, value를 넣어줄 때 해당 메서드를 이용해, key가 존재한다면 해당 key의 value를 가져와서 +해주고, key가 존재하지 않는다면 default값에 + 해서 값을 넣어줬다. 예시 map.put("key", map.getOrDefault("key", "default값") + "더해줄 값"); 하지만 value가 문자열 또는 정수형이 아닌 리스트일 때는 어떻게 값을 추가해줘야 할까? Map strListMap = new HashMap(); // 기본값 넣기 List list = strListM..