알고리즘29 1041번 주사위 문제 https://www.acmicpc.net/problem/1041 풀이 큐브로 생각해서 풀면 쉽습니다. 문제의 주사위를 블록으로 호칭하겠습니다. N 크기의 정육면체는 N=1 인 경우를 제외하고는 다음과 같이 구성됩니다. 모서리 블록 + 모서리를 제외한 테두리 블록(N=2 제외)+ 테두리 안쪽 블록(N=2 제외) 각 부분의 블록이 보여주는 면은 다음과 같습니다. 모서리 = 3면 테두리 = 2면 안쪽 = 1면 문제는 바닥면을 제외한 5 면의 최소합을 구하는 것입니다. 그러면 모서리, 테두리, 안쪽블록이 가질수 있는 면의 최소합을 구한 다음 각 구성의 개수만큼 곱해서 더해주면 됩니다. int minOne; // 안쪽인 1면 최소합 int minTwo; // 테두리인 2면 최소합 int minThree; .. 2022. 6. 21. 단계별로 풀어보기 - 입출력과 사칙연산 입출력과 사칙연산 관련 기초 문제이다. 언어를 처음 접할 때 풀어보면 좋은 문제들이다. 참고로 백준의 경우 제출할 때 , 클래스 이름을 Main으로 해주어야한다. 아니면 인식을 못한다. 여기서 알고 넘어가야할 것은 자바에서 사용하는 키워드 ( ",\ 라던지)들을 출력하기 위해서는 이스케이프 처리를 해주어야한다는 것만 알고넘어가면 될 것 같다. 출력하고자 하는 특수문자 앞에 역슬래시(\)를 붙여서 출력해주면 된다. 2557 public class Main { public static void main(String[] args) { System.out.println("Hello World!"); } } 10171 public class Main { public static void main(String[] .. 2022. 6. 2. 최단 경로 알고리즘 - 플로이드 워셜(Floyd-Warshall) 플로이드 워셜 알고리즘이란? 모든 노드 간의 최단 경로를 구하는 알고리즘 벨만 포드 알고리즘과 동일하게 음수 간선이 있어도 최단 경로를 구할 수 있습니다. 음수 사이클이 존재할 때는 사용하지 못합니다. 알고리즘 복잡도 : O(V^3) 모든 경로를 구하다보니 V * V(노드 수,Vertex) 만큼의 메모리가 필요합니다. 플로이드 워셜 알고리즘 흐름 요약 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용합니다. 우선 모든 노드들을 돌면서 최단경로 메모리에 직접적으로 연결되어있는 노드라면 가중치를, 아니라면 INF로 초기화합니다. 쉽게 말해서 모든 노드돌면서 연결된 인접한.. 2022. 6. 1. 다이나믹 프로그래밍 (DP,Dynamic Programming) 1. 다이나믹 프로그래밍이란? = 동적 계획법 큰 문제를 부분 문제로 나눈 후 문제를 해결하는 과정에서 나오는 계산된 결과를 기록하여 재활용하는 방법 한번 계산한 부분을 다시 계산하지 않기 때문에 속도가 빠르다 계산된 결과를 저장하기 위한 메모리가 필요하다 2. 다른 알고리즘과의 차이점 분할 정복 분할 정복은 부분 문제가 중복되지 않는다 DP는 부분 문제가 중복된다 분할 정복에서는 DP 사용불가 그리디 알고리즘 그리디 알고리즘은 근사치를 구하는 방식 DP는 모든 방법을 확인 후 최적해 구하는 방식 둘 다 적용이 가능하다면 그리디 알고리즘이 더 빠름 3. 다이나믹 프로그래밍 예시 피보나치 피보나치 같은 경우 아래의 그림과 같이 계산할 때 중복이 발생한다. 이를 처음 계산할 때 따로 저장해둔다면 계산을 여러.. 2022. 5. 29. 최단 경로 알고리즘 - 벨만-포드 (Bellman-Ford) 벨만-포드 알고리즘이란? 하나의 정점에서 모든 정점으로 가는 최단 거리를 구할 수 있습니다. 다익스트라와 달리 음수 간선이 포함되어 있어도 최단 경로를 구할 수 있습니다. 다만, 음수 사이클이 있을 땐 사용 X 매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느립니다. 알고리즘 복잡도 : O(VE) 벨만-포드 알고리즘 흐름 1. 정점의 숫자만큼 모든 간선을 체크한다. (정점 * 간선 , VE) distance가 무한대인 경우, 뽑힌 변의 가중치를 더해봤자 무한대이기 때문에 continue 처리한다. 1의 노드에서 5의 노드로 가는 경우, 1의 최단 경로 값이 0이기 때문에 5번 노드로 가는 가중치 5를 더해준다. 위의 작업을 정점 별로 모든 간선을 체크해나가다보면 distance가 갱신된다. 2. 음.. 2022. 5. 11. 최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘이란? 가중 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법 지도 경로 탐색, 네트워크 구축에 드는 비용을 최소화 하는데 사용 최단 경로 알고리즘 종류 다익스트라 벨만-포드 플로이드-워셜 다익스트라 알고리즘 (Dijkstra Algorithm) 출발점에서 목표점까지의 최단 경로를 구하는 알고리즘 한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음 간선에 음의 가중치가 없어야 함. 하나라도 음의 가중치가 있다면 다익스트라 알고리즘을 사용할 수 없다. 그리디 + DP 형태 알고리즘 복잡도 : O(ElogV) * E = Edge , V = Vertex 다익스트라 알고리즘 흐름 1. 출발점으로부터의 최단경로를 저장할 노드만큼의 크기를 가진 배열을 만들고, 출발 노드에는 0을.. 2022. 5. 11. 최소 신장 트리 (MST) 최소 신장 트리 (MST, Minimum Spanning Tree) 란? 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법 종류 크루스칼 (Kruskal) 간선 중 최소 값을 가진 간선부터 순차적으로 연결 사이클 발생 시 다른 간선을 선택 사이클 발생 여부는 Union-Find를 통해서 체크 주로 간선 수가 적을 때 사용 시간복잡도 : O(ElogE) import java.util.Arrays; import java.util.Comparator; public class Kruskal { // Union-Find를 위한 배열 static int[] parents; public static int kruskal(int[][] data, int v, int e) { int weightSum = 0; //.. 2022. 5. 11. 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘이란? 매 순간 현재의 기준으로 최선의 답을 선택해나가는 기법 빠르게 근사치를 계산할 수 있지만 결과적으로는 최적해가 아닐 수 있다. 그리디 알고리즘 적용 조건 탐욕적 선택 특성 (Greedy Choice Property) 지금 선택이 다음 선택에 영향을 주지 않을 경우 최적 부분 구조 (Optimal Substructure) 전체 문제의 최적해는 부분 문제의 최적해로 이루어짐 그리디 알고리즘 예제 Activity Selection Problem import java.util.ArrayList; import java.util.Collections; class Activity { String name; int start; int end; public Activity(String name, i.. 2022. 5. 10. Binary Search (이진 탐색) import java.util.Arrays; /** * Binary Search (이진 탐색) * 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법 * 찾고자 하는 값과 데이터 중앙에 있는 값을 비교 * - 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색 * - 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색 * 시간 복잡도 : O(logn) * * 자바에서 기본적으로 제공하는 BT가 있다. Arrays.binarySearch(); */ public class BinarySearch { // 반복문 사용 public static int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - .. 2022. 4. 30. 정렬 알고리즘별 복잡도 정리 2022. 4. 30. Shell Sort (셸 정렬) /** * Shell Sort(셸 정렬) * - 삽입정렬은 오름차순 정렬 기준으로 내림차순으로 이미 정렬되어 구성된 데이터에 대해서는 * - 앞의 데이터와 하나씩 비교하며 모두 교환해야한다. * - 이러한 약점을 보완하는 방식이 Shell sort * - 이전의 모든 데이터와 비교하지 않고 일정 간격을 두어 비교 * - 간격 설정에 따라 worst case가 O(n^2) 지만 일반적인 산포 데이터 기준으로는 삽입 정렬에 비해 빠르다. */ public class ShellSort { public static void shellSort(int[] arr) { // 보통 간격은 배열 길이의 절반으로 시작함. int gap = arr.length / 2; // 절반씩 줄여나가면서 진행 for (int g = .. 2022. 4. 30. Counting Sort (계수 정렬) import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; /** * Counting Sort(계수 정렬) * - 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식 * - 카운팅을 위한 카운팅 테이블이 필요 * - Un-Stable sort * - 시간 복잡도 = O(n+k) (k는 정렬 대상 데이터 중 최대 값) * - * - [1,3,2,4,5] 이런 배열처럼 수의 분포가 좁다면 배열을 이용하는게 좋고 * - [1,24005,4,3] 이런식으로 수 자체는 적은데 수의 분포가 넓다면 해시맵을 이용하는게 좋다. */ public class CountingSort { /.. 2022. 4. 30. Radix Sort (기수정렬) 가장 작은 자릿수부터 정렬해나가다보면 결국에는 정렬이 되는 신기한 기수정렬 1의 자리 -> 10의 자리 -> 10의 자리 -> ,,,, 순으로 정렬을 해나가다보면 정렬이 되어있다. - 첫번째 자리수로 정렬(1의 자리) - 두번째 자리수로 정렬(10의자리) import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; /** * Radix Sort(기수 정렬) * - 낮은 자리 수부터 정렬하는 방식(1의자리 -> 10의자리 -> 100의자리) * - 각 원소 간의 비교 연산을 하지 않아 빠르지만, 기수 테이블을 위한 메모리가 필요하다. * - 시간 복잡도 = O(dn) (d는 최대자릿수) * - Stable sort * - .. 2022. 4. 30. Heap Sort (힙 정렬) /** * Heap Sort(힙 정렬) * - Heap 자료구조 기반 정렬 방식 * * - 이진 tree 자료구조 성질 이용 (0번 인덱스부터 시작한다는 기준) * - 1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1 * - 2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 2 * - 3. 부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2 * - * - 장점 * - 부분 정렬을 할 때 효과적 * - 최악의 경우에도 시간 복잡도 = O(nlogn) * - * - 단점 * - 일반적인 O(nlogn) 정렬 알고리즘에 비해 성능이 조금 떨어진다. * - Stable sort 가 아니다. */ public class HeapSort { public static void heap.. 2022. 4. 30. Merge Sort(합병 정렬, 2-ways 합병 정렬) /** Merge Sort(합병정렬) - 배열을 절반으로 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식 (Divide & Conquer) - 장점 - 동일한 값의 경우, 들어온 순서대로 정렬되므로 Stable Sort 이다. - 최악의 경우에도 시간 복잡도 = O(nlogn) - 단점 - 추가적인 배열이 필요하므로 in-place Sort가 아니기 때문에 메모리 사용량이 많다. - 원본 배열에 추가적인 배열의 값을 복사하는 과정이 많은 시간을 소비하기 때문에 데이터가 많을 경우 시간이 많이 소요된다. */ public class MergeSort { public static void mergeSort(int[] arr, int[] tmp, int left, int r.. 2022. 4. 29. 이전 1 2 다음
