Notion - 위상 정렬 (Topology Sort) 이번에는 위상 정렬에 대해 정리하고, 문제를 기준으로 이해해보자! https://www.acmicpc.net/problem/2252 - 줄 세우기 / Gold 3 위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.4 24 23 1위상 정렬, Topology Sort?위상 정렬은 뱡향이 정해져 있는 그래프에서 순서대로 정렬하기 위해 사용되는 알고리즘이다.특히 이 알고리즘은 방향이 있으며 순환하지 않는 그래프, DAG(Directed Acyclic Graph)에만 적용이 가능하다는 조건이 붙는다. 위상 정렬을 구현하기 전에 이해해야 할 두 가지 개념을 이해해두면 도움이 될 것이다. 진입차수 (in-degree, 입력차수)어떤 노드 N으로 향하..
Notion - 동적계획법 (Dynamic Programming; DP) 이번에는 DP에 대해 정리하고, 문제를 기준으로 이해해보자! https://www.acmicpc.net/problem/1912 - 연속 합 / Silver 2 위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.1010 -4 3 1 5 6 -35 12 21 -1동적계획법, DP?동적계획법, 알고리즘을 풀 때 흔히 언급되는 DP는 큰 문제를 작은 문제들로 나누어 푸는 방법이다.각 하위 문제들을 해결하고 저장하여 같은 하위 문제가 나왔을 때 이를 이용한다.쉽게 말해서 문제를 작게 나누고 해결한 값을 저장해서 활용한다는 것이다. 위 예제를 통해 먼저 살펴보자.위 예제는 최대 부분 수열의 합을 구하는 문제로 연속된 숫자의 합이 가장..
Notion - 다익스트라 이번에는 다익스트라에 대해 정리하고, 문제를 기준으로 이해해보자. https://www.acmicpc.net/problem/1916 - 최소비용 구하기 / Gold 5 위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.581 2 21 3 31 4 11 5 102 4 23 4 13 5 14 5 31 5다익스트라 알고리즘?다익스트라는 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다.다익스트라는 2중 for문을 이용한 방법, 우선순위 큐를 이용한 탐색으로 구현 방법이 나뉜다.그럼 이번에도 그림으로 표현해보도록 하겠다. 이전 글인 플로이드 워셜과 유사하게 접근이 가능하다.INF를 사용하지만 이번에는 시작 지점만을 위한 가중치 배열인 dist를 따로 선언하여 사..
Notion - 플로이드 워셜 이번에는 플로이드 워셜에 대해서 정리하고, 문제를 기준으로 이해해보자. https://www.acmicpc.net/problem/11404 - 플로이드 / Gold 4 위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.5141 2 21 3 31 4 11 5 102 4 23 4 13 5 14 5 33 5 103 1 81 4 25 1 73 4 25 2 4플로이드 워셜 알고리즘?플로이드 워셜은 모든 노드 간의 최단경로를 구할 때 사용되는 알고리즘이다.플로이드 워셜 3중 for문을 이용해서 구현할 수 있다. 우선 예제를 기준으로 표현해보자면 아래와 같다. 예제에서 나온 중복되는 경로에서의 큰 값은 제외하고 인접행렬을 만들었을 때 오른쪽과 같이 만들어 낼 수 있다.여기서 I..
Notion - DFS와 BFS DFS와 BFS에 대해서와 인접 행렬과 인접 그래프에 대해서 정리하고, 한 문제를 통해서 이해해보자.설명에 앞서 코드에 대한 기준을 정하고 시작하면 좋을 것 같아 아래 문제를 기준으로 설명하도록 하겠다. https://www.acmicpc.net/problem/1260 - DFS와 BFS / Silver 2 위 문제의 예제 1번인 아래 입력을 기준으로 설명하도록 하겠다.4 5 11 21 31 42 43 4DFS (Depth-First Search)DFS는 깊이 우선 탐색이라고 부르며, 깊은 부분부터 우선적으로 탐색하는 알고리즘이다.DFS는 Stack 자료구조 혹은 재귀 함수를 이용하여 구현할 수 있다. DFS로 위 예제를 탐색하게 되면 1 2 4 3 이라는 결과를 얻을 수..
문제 소개Level 3 / Graphhttps://school.programmers.co.kr/learn/courses/30/lessons/49191풀이 public int solution(int n, int[][] results) { int answer = 0; int[][] rank = new int[n+1][n+1]; // 플로이드 워셜 알고리즘 변형 for(int[] r:results){ rank[r[0]][r[1]] = 1; //이김 rank[r[1]][r[0]] = -1; //짐 } // 여기까지는 일반 인접행렬과 비슷함 for(int k=1; k이번 문제는 플로이드 워셜 알..
문제 소개Medium / Binary Searchhttps://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/풀이public int shipWithinDays(int[] weights, int days) { int answer = 0; int left = 0, right = 0; for (int tmp : weights) { left = Math.max(left, tmp); right += tmp; } while (left mid) { day++; result = 0; } r..
문제 소개Medium / Dynamic Programminghttps://leetcode.com/problems/count-sorted-vowel-strings/description/풀이public int countVowelStrings(int n) { int[] dp = new int[]{1, 1, 1, 1, 1}; while (--n > 0) { for (int i = 3; i >= 0; i--) { // 각 인덱스 a, e, i, o 에 대한 개수를 할당함 dp[i] += dp[i + 1]; // a는 나머지 4개를 포함한 경우의 수, e는 나머지 3개를 포함한 경우의 수, i 는 나머지 2개, o는 나머지 1개, u는 제외 / u는 항상 1개 => 모두 ..
문제 소개Medium / Dynamic Programminghttps://leetcode.com/problems/all-possible-full-binary-trees/description/풀이public List allPossibleFBT(int n) { if (n%2 == 0) { return new ArrayList(); } List result = new ArrayList(); if (n == 1) { result.add(new TreeNode(0)); } else { for (int leftNodes = 1; leftNodes 이번 문제는 DFS로 풀어내야겠다는 생각은 들었지만, 그 이상으로 접근하기가 어려웠다.그렇기에 내용을 풀어..
문제 소개Level 2https://school.programmers.co.kr/learn/courses/30/lessons/42885테스트케이스 (추가)[20, 60, 70, 80, 30], 100 / 3풀이public int solution(int[] people, int limit) { Integer[] peopleArray = Arrays.stream(people).boxed().toArray(Integer[]::new); Arrays.sort(peopleArray, Collections.reverseOrder()); int length = peopleArray.length; int last = length-1; int[] ch = new int[length]; i..
문제 소개Level 2https://school.programmers.co.kr/learn/courses/30/lessons/42860테스트케이스 (추가)“BBAAAAB” / 6풀이public int solution(String name) { int count = 0; int length = name.length(); int move = length-1; // 순서대로 가는 이동 수 char[] chars = name.toCharArray(); for (int i = 0; i Z로 이동 } int next = i+1; while (next 처음에는 알파벳을 조정하는 조이스틱인 상, 하에 대한 요소만 신경 쓰다가 틀리게 된 문제이다.좌, 우를..
Notion - 퀵 정렬Git - 퀵 정렬 이해하기 이번에는 퀵 정렬에 대해서 정리해보려고한다.퀵 정렬이란?퀵 정렬은 불안정 정렬이며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 방법이다.불안정 정렬?정렬 과정에서 같은 값을 가진 요소의 상대적 순서가 보장되지 않는 정렬을 뜻한다.예를들어, [a1, b, c, a2] 가 있다고 가정하겠다.a1, a2는 같은 a이며, 위 예제에서는 이해하기 쉽도록 a1, a2로 설명하겠다.정렬이 완료된 후 [a2, a1, b, c] 가 될 수도 있고, [a1, a2, b, c]가 될 수도 있다.이처럼 정렬 이후 상대적으로 뒤에 있던 a2가 항상 뒤에 오는 것이 아닌 앞으로 올 수도 있기에, 상대적인 순서를 보장하지 못하는 불안정 정렬이라고 불린다.분할 정복 알고리..
