문제https://www.acmicpc.net/problem/1516 풀이선행 조건을 해결해야하는 문제 특성상 위상정렬을 이용해서 문제를 해결했습니다.입력을 받으면서, 정보를 저장했으며(진입차수, 건물 건설시간, 선행 건설 건물정보)진입차수가 0인 건물을 큐에 넣고 그래프 탐색을 진행했습니다. 이때, 건물이 동시에 지어질 수 있기 때문에건물 중 가장 오래걸리는 시간을 찾아서 ans 정답 배열에 저장해주었고진입차수를 1 감소시킨 값이 0이라면 큐에 넣어주었습니다. 그래프 탐색을 마친 후건물을 순회하면서 도출된 정답 배열 값 + 현재 건물을 건설하는 데 걸리는 시간을 더해주어 출력했습니다. 코드import java.io.*;import java.util.*;public class Main { stati..
개념분할 정복을 기반으로 정렬되는 알고리즘이며, 대용량 데이터를 정렬할 때 유리합니다.추가적인 공간 필요 X피벗을 기준으로 나누어진 두 개의 집단 사이에서 요소의 교환이 일어나는 불안정한 정렬입니다. 병합 정렬(Merge Sort)와의 차이점은병합 정렬은 수열의 절반을 나누어 분할 정복을 수행하지만퀵 정렬은 피벗을 기준으로 분할 정복을 수행합니다. 로직피벗을 기준으로 2개의 배열로 분할하고(분할)분할된 배열을 각각 정렬한 다음(정복)정렬된 배열을 합하는 방식으로 동작합니다. (결합)큰 값과 작은 값을 나누어 정렬하는 방식으로 동작합니다. 1. 분할입력 배열을 피벗을 기준으로 2개의 부분 배열로 분할합니다.피벗의 좌측에는 피벗보다 작은 값을 두고피벗의 우측에는 피벗보다 큰 값을 둡니다. 2. 정복부분 배열..
개념요소들 중에서 최대/최소값을 찾아 정렬하는 알고리즘입니다.최대값 선택 시 내림차순 정렬을 진행합니다.(최솟값 선택 시 오름차순 정렬) 로직오름차순 정렬을 기준으로 보자면먼저 0~N-1 요소들 중에서 가장 작은 값을 찾고 0번째 인덱스와 교환해줍니다.그다음 정렬된 0번째를 제외한1~N-1 요소 중에서 가장 작은 값을 찾고 1번째 인덱스와 교환해줍니다.이렇게 총 N-2번(마지막 인덱스 탐색 X) 반복하면 정렬이 완료됩니다.추가 메모리 공간이 필요하지 않는 특징이 있습니다. 코드자바로 작성한 선택정렬 코드는 다음과 같습니다.// 선택 정렬: N^2 순회// 오름차순 정렬for (int i = 0; i arr[j]){ minVal = arr[j]; minIdx = j..
개념정렬을 진행할 원소의 index(a)보다 작은 곳(0~a-1)에 있는 원소들을 탐색하고알맞은 위치에 삽입하여 정렬하는 알고리즘입니다.구현이 간단하다는 특징이 있습니다. 로직오름차순 정렬 기준1~N-1번째 인덱스를 순차적으로 key로 두고key-1 ~ 0의 인덱스를 감소순회하면서만약 arr[현재의 값] > key 라면, arr[현재의 값+1] = arr[현재의 값]을 넣어줍니다.그렇지 않다면, 순회를 종료합니다.순회가 끝나고 난 후, arr[마지막 위치 + 1] = key 값으로 갱신합니다. 코드자바로 작성한 삽입정렬 코드는 다음과 같습니다.// 삽입 정렬: N^2 순회int key, j;for (int i = 1; i = 0 ; j --) { if (arr[j] > key) arr[j+1..
