* 핵심 개념

음수 가중치가 존재하는 경우 최단 거리를 찾기 때문에 다익스트라가 아닌 벨만포드 알고리즘을 사용해야 한다.

방향이 있는 유향그래프이기 때문에 1번 정점에서부터 시작해서

해당 정점을 갈 수 있는 최단 거리와 이전 정점까지 가중치 + 해당 정점 방문에 필요한 가중치를 더해

최소값을 저장해주면 된다.

* 문제

* 소스 코드

* 다익스트라(Dijkstra) 알고리즘

한 정점에서 다른 정점으로 가는 최단거리를 구하는 알고리즘으로 가중치가 음수면 사용이 불가능하다.

다익스트라는 최단거리는 최단거리들로 이루어져 있다는 Greedy한 아이디어로 만들어진 알고리즘이다.

주로 우선순위 큐와 BFS를 이용하여 구현되며, 작동 방식은 다음과 같다.

1. 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하나 선택해 방문한다.

2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다.

* 작동 예시

0번 정점에서 시작한다고 가정하고, 위와 같은 그래프가 있을 때 작동방식은 다음과 같다.

위 순서를 통해 정점과 정점사이의 최단 거리를 구한다.

핵심은 최단거리는 최단거리들로 이루어져 있다는 생각이고, 선택한 정점과 인접한 최소한의 가중치를 가진 간선을 선택하는 것은 프림 알고리즘과 비슷하다.

하지만, 프림 알고리즘과 달리 우선순위 큐에 해당 가중치를 계속 더해가며 최단 경로를 찾는 알고리즘이다.

백준/1753 :: 최단경로 문제

백준/1753 :: 최단경로 풀이

* 핵심 개념

최대값은 최소값이랑 곱하고 최소값은 최대값이랑 곱한 값을 더하면 그 값은 최소가 된다.

A,B 배열을 정렬해서 최대값과 최소값을 곱하면서 더하면 된다.

단순 Arrays.sort를 사용해 정렬해 풀 수도 있지만

MergeSort도 연습할겸 구현해서 사용했다.

* 문제

* 소스 코드

Java를 사용하다 보면 형변환할 일이 많이 있다.

int <> char <> String 으로의 형변환에 대해 알아보자.

< 유의 사항 >

char to int에서 숫자를 넘기는 경우 '0'을 해야 한다. (아스키코드값을 넘기기 때문)

char to string에서 char배열인 경우 String.valueOf를 사용하면 char배열 글자가 서로 붙어서 문자열로 넘어간다.

String to char에서 문자 길이가 1이라면 charAt으로 넘기면 된다.

String to char에서 문자 길이가 2이상이라면 toCharArray를 이용해 char배열로 넘긴다.

* 핵심 개념

Stack을 사용해 풀 수 있는 문제다.

다양한 방법이 있지만 필자는 입력받은 문자를 Stack에 넣어가며 값을 비교했다.

Stack에 ()와 [] 짝이 안맞다면 강제로 종료하면 되고,

아니면 ()인 경우 2를, []인 경우 3을 스텍에 넣어준다.

만약, Stack에 [,2,3 이 들어있다면 2+3을 하고 현재 문자가 ] 이라면 *3을 하면 된다.

마지막에 Stack을 돌면서 숫자를 전부 더해주면 된다.

예외 처리는 맨 처음부터 ')'나 ']'가 들어왔을때 처리해야 한다.

* 문제

* 소스 코드

* 합병 정렬(Merge Sort)    =>O(nlogn)

합병 정렬은 O(nlogn) 의 시간복잡도를 보장한다.

하지만 단점은 임시 배열 공간이 추가로 필요하다는 점이다.

분할 정복으로 구현하는데, 배열을 최대한 나누고 각 배열을 다시 정렬하면서 합병하는 방식이다.

< 작동 방식 >

1. 나눌 수 있는 만큼 끝까지 나눈다. (1개가 될때까지)

2. 나누어진 배열을 임시 배열에 저장하고 이를 비교하면서 확인한다.

모든 작동방식을 알아보는 것 보다 합치는 과정에 대표적인 예를 통해 작동방식을 알아보자.

우선 배열을 하나의 배열까지 쪼갠 후 합치면서 정렬한다.

이후 tmp 배열에 4개의 data를 복사한다.

left = start, right = mid+1로 설정하고 서로 비교해 작은 값을 data에 덮어씌운다.

left를 한칸 이동하고 작은 값을 data에 덮어씌운다.

right를 한칸 이동하고 작은 값을 data에 덮어씌운다.

right가 배열의 끝에 도달했기 때문에 남은 left를 data에 덮어씌운다.

이런 방식으로 통해 정렬하는 방식이다.

추가로, 이 방식은 left가 남았을 때만 남은 data를 덮어 씌워주면 되는데, 그 이유는 처음 시작때 임시 배열에 data를 복사했기 때문이다.

아래 예시를 살펴보자.

tmp에 data를 복사한 후 left와 right를 비교해 작은 값을 data에 넣는다.

left를 한칸 이동하고 작은 값을 data에 덮어 씌운다.

여기서 Right에 있는 값을 굳이 덮어 씌우지 않아도 원본 데이터랑 같기 때문에 Right의 경우 덮어씌울 필요가 없다.

< 소스 코드 >

* 퀵 정렬(Quick Sort)    =>평균 O(nlogn), 최악 O(n^2)

자바에서 Arrays.sort를 사용하변 내부는 Quick Sort로 구현되어있다.

평균 O(nlogn) 이지만 최악에 O(n^2) 이므로 데이터가 많은 경우 조심해야 한다.

최악의 경우란 아이러니하게도 정렬된 경우를 의미한다.

< 작동 방식 >

퀵 정렬은 pivot값을 중심으로 왼쪽에는 pivot 보다 작은 값들, 오른쪽에는 pivot보다 크거나 같은 값을 정렬한다.

기준을 잡고, left, right 포인터를 이동하면서 num[left] > pivot 과 num[right] < pivot 인 경우 서로 교환한다.

소스 코드와 그림으로 이해하자.

num[left] > pivot, num[right] < pivot 조건을 만족할 때까지 left, right를 움직인다.

pivot을 가운데 값으로 설정하고 Left, Right 를 각 끝의 idx를 지정한다.

< 소스 코드 >

버블 정렬(Bubble Sort)

• 인접한 두 숫자를 비교해서 변경하는 방법
• 오른쪽부터 최대값/최소값을 정렬해 나가는 방식

1 2 3 4 5 6 7

public void BubbleSort(int[] num) { for (int i = 0; i < num.length; i++) { for (int j = 1; j < num.length - i; j++) { if (num[j] < num[j - 1]) swap(j - 1, j, num); } } }

---

선택 정렬(Selection Sort)

• 자신보다 뒤에있는 숫자들 중 가장 작은 숫자를 발견해서 맨 앞에서부터 채우는 정렬
• 왼쪽부터 최대값/최소값을 정렬해 나가는 방식

1 2 3 4 5 6 7 8 9

public void SelectionSort(int[] num) { for (int i = 0; i < num.length; i++) { int min = i; for (int j = i + 1; j < num.length; j++) { if (num[min] > num[j]) min = j; } if (num[min] < num[i]) swap(min, i, num); } }

---

삽입 정렬(Insertion Sort)

• i번째 배열 값부터 앞으로 탐색하며 자신보다 작다면 swap하는 정렬
• n번째 수행시 n번째 까지 정렬되는 방법

1 2 3 4 5 6 7 8 9 10 11

public void InsertioinSort(int[] num) { for (int i = 1; i < num.length; i++) { int tmp = num[i]; for (int j = i - 1; j >= 0; j--) { if (tmp < num[j]) { num[j + 1] = num[j]; num[j] = tmp; } } } }

---

퀵 정렬(Quick Sort)

• pivot을 정하고 pivot 좌/우를 정렬하면서 전체 배열을 정렬
• 자바에서 Arrays.sort를 사용하변 내부는 Quick Sort로 구현되어있다.
• 평균 O(nlogn) 이지만 최악에 O(n^2) 이므로 데이터가 많은 경우 조심해야 한다.
• 최악의 경우란 아이러니하게도 정렬된 경우를 의미한다.

< 작동 방식 >

• pivot을 가운데 값으로 설정하고 Left, Right 를 각 끝의 idx를 지정한다.

• num[left] > pivot, num[right] < pivot 조건을 만족할 때까지 left, right를 움직인다.

• 둘의 위치를 바꾼다. 이렇게 되면 pivot 왼쪽에는 pivot보다 작은 값, 오른쪽에는 큰값이 정렬된다.

< 소스 코드 >

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public int partition(int left, int right, int[] num) { int pivot = num[(left + right) / 2]; while (left <= right) { while (num[left] < pivot) left++; while (num[right] > pivot) right--; if (left <= right) { swap(left, right, num); left++; right--; } } return left; } public void QuickSort(int left, int right, int[] num) { if (left < right) { int pivot = partition(left, right, num); if (left < pivot - 1) QuickSort(left, pivot - 1, num); if (right > pivot) QuickSort(pivot, right, num); } }

---

합병 정렬(Merge Sort)

• 합병 정렬은 O(nlogn) 의 시간복잡도를 보장한다.
• 단점은 임시 배열 공간이 추가로 필요하다는 점이다.
• 분할 정복으로 구현하는데 배열을 최대한 나누고, 합병하면서 값을 비교해 정렬하는 방식이다.

< 작동 방식 >

1. left = start, right = mid+1로 설정하고 서로 비교해 작은 값을 data에 덮어씌운다.
2. left를 한칸 이동하고 작은 값을 data에 덮어씌운다.
3. right를 한칸 이동하고 작은 값을 data에 덮어씌운다.
4. right가 배열의 끝에 도달했기 때문에 남은 left를 data에 덮어씌운다.

< 소스 코드 >

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

public void mergeSort(int start, int end) { if (start < end) { int mid = (start + end) / 2; mergeSort(start, mid); mergeSort(mid + 1, end); merge(start, mid, end); } } public void merge(int start, int mid, int end) { for (int i = start; i <= end; i++) { tmp[i] = num[i]; //tmp 배열에 값을 옮긴다. } int left = start; int right = mid + 1; int idx = start; while (left <= mid && right <= end) { //num 배열에 비교하면서 저장 if (tmp[left] >= tmp[right]) { num[idx++] = tmp[right++]; } else { num[idx++] = tmp[left++]; } } //어느 한쪽에 남은 tmp 배열을 num 배열에 저장 while (left <= mid) num[idx++] = tmp[left++]; while (right <= end) num[idx++] = tmp[right++]; }