Algorithm

💡문제[Gold IV] 2로 몇 번 나누어질까 - 1407문제 링크성능 요약메모리: 11552 KB, 시간: 76 ms🌟풀이범위가 무려 1≤A≤B≤1015 로 엄청나다.그래서 A ~ B 까지 순회하면서 더할 수는 없다.1 ~ n까지 소수 x의 배수의 개수를 구하는 방식을 이용하였다.💡 1 ~ n까지 수들은 소수 x로 몇번 나누어 떨어질까 ?1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20-1-2-1-3-1-2-1-4-1-21부터 20까지 순회하며 각 수를 소인수분해 했을때 2가 몇 번씩 들어가는지 적어보았다.이를 2가 들어간 횟수만큼 동그라미로 표현하게 되면 아래 사진과 같이 표시되며 오른쪽과 같은 의미를 가질 수 있다.위를 참고하여| 1 | 2 | 3 | ..

💡문제[level 2] 소수 찾기 - 42839문제 링크성능 요약메모리: 84.5 MB, 시간: 23.86 ms  🤔접근법문제 요약1개 이상 7개 이하의 자연수들을 개수 상관없이 한번씩만 뽑아서 만들 수 있는 숫자가 소수인지 판별하는 문제범위 체크 및 시간복잡도 예상1 ≤ numbers의 길이 ≤ 7numbers를 이루고 있는 숫자 들은 0 ~ 9 자연수 이다.$O(N^2)$ 보다는 작아야한다.풀이법⭕ 접근 방법. 완탐숫자 문자열로부터 가능한 모든 순열 생성:각 자리 숫자를 사용하여 순열을 만들고, 각 순열조합이 소수인지 확인자리수의 중복을 방지하기 위해 방문 여부를 체크하는 배열을 사용소수 판별:각 생성된 숫자가 소수인지 확인. 소수 판별은 2부터 해당 숫자의 제곱근까지의 수로 나누어지는지 확인하는..

# [level 3] 입국심사 - 43238  [문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/43238) ### 성능 요약 메모리: 99.7 MB, 시간: 107.77 ms import java.util.*;class Solution { public long solution(int n, int[] times) { long answer = 0; Arrays.sort(times); // 이분탐색 기준은 모든 인원이 입국심사를 받는데 걸리는 시간 // 1분 동안 모든 인원이 입국심사를 전부 받았나? -> X // 2분 동안 모든 인원이 입국심사를 전부 받았나..

💡문제[level 2] 가장 큰 수 - 42746문제 링크성능 요약메모리: 124 MB, 시간: 215.48 ms 🤔접근법문제 요약0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내는 문제범위 체크 및 시간복잡도 예상numbers의 길이는 1 이상 100,000 이하numbers의 원소는 0 이상 1,000 이하풀이법⭕ 접근 방법. 우선순위 큐🔑 PriorityQueue를 사용하자!static PriorityQueue *pq* = new PriorityQueue((o1, o2) -> {return o2-o1;});위와 같이 PQ를 사용하여 우선순위 조건을 변경하면 큰 값이 우선이 되도록 qp를 생성할 수 있다.pq 는 힙으로 구성되어 있기 때문에 시간복잡도는 O..

💡문제[Silver II] 최대 힙 - 11279문제 링크성능 요약메모리: 38356 KB, 시간: 1604 ms 🤔접근법문제 요약주어진 자연수 x를 배열에 넣고, 0이 주어지면 가장 배열에서 가장 큰 값을 출력하는 문제범위 체크 및 시간복잡도 예상1 ≤ N ≤ 100,000 (N은 x가 주어지는 횟수)$O(N^2)$ 보다는 작아야한다.풀이법⭕ 접근 방법. 우선순위 큐🔑 PriorityQueue를 사용하자!static PriorityQueue *pq* = new PriorityQueue((o1, o2) -> {return o2-o1;});위와 같이 PQ를 사용하여 우선순위 조건을 변경하면 큰 값이 우선이 되도록 qp를 생성할 수 있다.pq 는 힙으로 구성되어 있기 때문에 시간복잡도는 O(logN)을..

💡문제[Silver II] 최소 힙 - 1927문제 링크성능 요약메모리: 29732 KB, 시간: 1428 ms🤔접근법문제 요약주어진 자연수 x를 배열에 넣고, 0이 주어지면 가장 배열에서 가장 작은 값을 출력하는 문제범위 체크 및 시간복잡도 예상1 ≤ N ≤ 100,000 (N은 x가 주어지는 횟수)$O(N^2)$ 보다는 작아야한다.풀이법⭕ 접근 방법. 우선순위큐🔑 PriorityQueue를 사용하자!위와 같이 PQ를 사용하여 작은 우선으로 빠져 나올 수 있도록 자료구조를 생성할 수 있다.pq 는 힙으로 구성되어 있기 때문에 시간복잡도는 O(logN)을 가진다.➡️ 해당 풀이법의 시간 복잡도 : $O(NlogN)$😎SUCCESS고냥 단박에 성공    👩‍💻 코드import java.util...

💡문제[level 2] 두 큐 합 같게 만들기 - 118667문제 링크성능 요약메모리: 131 MB, 시간: 27.82 ms  🤔접근법문제 요약배열의 형태로 주어진 두 큐의 합을 동일하게 만들었을 때 최소가 되는 이동 횟수를 출력범위 체크 및 시간복잡도 예상1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,0001 ≤ queue1의 원소, queue2의 원소 ≤ 10$O(queue)$풀이법❌ 접근 방법. 완탐두 배열의 길이의 합이 8이라고 했을 때 두 배열로 나눌 수 있는 길이의 경우의 수는 아래와 같다1 : 7 → 8경우2 : 6 → 8경우3 : 5 → 8경우4 : 4 → 4경우 (1,2,3,4), (4,5,6,7) 이나 (4,5,6,7) , (1,2,3,4)은 같은 경우이기 때문n으로 ..

👩‍💻 코드import java.util.*;class Solution { static class Task { private String name; private int start; private int playtime; public Task(String name, int start, int playtime) { this.name = name; this.start = start; this.playtime = playtime; } public Task(String name, int playtime) { this..

💡문제[level 2] 테이블 해시 함수 - 147354문제 링크성능 요약메모리: 144 MB, 시간: 9.92 ms  🤔접근법문제 요약주어진 2차원 배열을 정해진 컬럼을 오름차순으로 행을 다시 정렬 (값이 같다면 첫번째 값을 기준으로 내림차순)i ~ j 행을 각 i 행으로 나눈 나머지들의 합을 구한후 그 합들을 XOR 연산 하여 나온 값을 출력범위 체크 및 시간복잡도 예상1 ≤ data의 길이 ≤ 2,5001 ≤ data의 원소의 길이 ≤ 5001 ≤ data[i][j] ≤ 1,000,000data[i][j]는 i + 1 번째 튜플의 j + 1 번째 컬럼의 값을 의미합니다. (주어진 입력값들은 모두 1부터 인덱스가 시작함으로 유의하자)1 ≤ col ≤ data의 원소의 길이1 ≤ row_begin ..

💡문제[level 3] 베스트앨범 - 42579문제 링크성능 요약메모리: 76.4 MB, 시간: 4.64 ms 🤔접근법문제 요약복잡한 우선순위에 맞춰 정렬한 다음 조건에 맞게 노래 번호를 출력하는 문제우선순위 설명 (장르에 따른 우선순위 조건이 있고, 노래에 따른 우선순위 조건이 있다.)각 장르별로 재생 수를 합산하여 재생 수가 높은 순서대로 출력단, 각 장르별로 노래는 2개씩 출력한다. (만약 주어진 보기에 장르에 해당하는 노래가 한개라면 하나만 출력한다.)두 노래의 우선순위는 재생 수가 높은 것을 우선으로 출력, 단 재생수가 같다면 고유 번호가 낮은 순서로 출력 범위 체크 및 시간복잡도 예상1 ≤ 노래 곡 수 ≤ 10,000장르 종류는 100개 미만$O(노래곡수^2)$ 까지도 가능 풀이법⭕ 접근 ..

💡문제[level 2] 문자열 압축 - 60057문제 링크성능 요약메모리: 82.9 MB, 시간: 31.44 m 🤔접근법문제 요약주어진 문자열을 규칙에 따라 압축했을 때 가장 짧은 문자열의 길이를 출력문자열을 1개 ~ n개 단위로 잘라서 제일 앞에서부터 부분문자열을 보는데 특정문자열이 반복되면 반복횟수+문자열 로 압축 가능하다ex) abcabc → 3abc , abcabcdede → 3abcdede (길이가 3으로 잘랐을때, de는 반복 되긴 하지만 길이가 3이 아니라 압축할 수 없다.)단 , 문자열은 제일 앞에서부터 정해진 길이로 자른다.범위 체크 및 시간복잡도 예상1 ≤ 주어지는 문자열의 길이 ≤ 1,000$O(N^2)$ 까지도 쌉가능시간복잡도가 null~null~한 아주 착한 문제풀이법⭕ 접근 ..

💡문제[level 1] 숫자 문자열과 영단어 - 81301문제 링크성능 요약메모리: 71.7 MB, 시간: 24.66 ms     🤔접근법문제 요약숫자와 영어로 된 숫자가 띄어쓰기 되지 않은 상태로 문자열로 주어진다.부분부분 영어로 되어 있는 숫자로 바꿔서 정수형으로 출력하라.범위 체크 및 시간복잡도 예상1 ≤ 주어지는 문자열의 길이 ≤ 50모든 문자열이 숫자라고 하더라도 50이므로 시간복잡도가 null~null~한 아주 착한 문제풀이법⭕ 접근 방법. 완탐주어진 문자열에서 1 ~ 9 까지 검색 , zero ~ nine 까지 검색만약 존재한다면 존재하는 문자열의 첫번째 인덱스을 반환받아 result 배열에 영문숫자와 치환되는 숫자를 기입중복되는 숫자가 존재할 수 있으므로 이미 검색된 문자열을 @로 치환..

💡문제[level 2] 숫자 카드 나누기 - 135807문제 링크성능 요약메모리: 124 MB, 시간: 34.15 ms 🤔접근법문제 요약배열 A의 정수들을 모두 나눌 수 있는 숫자 a는 배열 B의 정수를 하나도 나눌 수 없다.배열 B의 정수들을 모두 나눌 수 있는 숫자 b는 배열 A의 정수를 하나도 나눌 수 없다.숫자 a와 b중 큰거를 출력범위 체크 및 시간복잡도 예상1 ≤ 배열의 길이 ≤ 500,0001 ≤ 배열의 원소 ≤ 1,000,000O($N$) 이하.풀이법⭕ 접근 방법. 유클리드 호제법배열 A의 최대 공약수를 구한다.배열 B의 최대 공약수를 구한다.배열 A의 최대 공약수가 배열 B의 원소 중 하나라도 나눌 수 있는지 확인한다.배열 B의 최대 공약수가 배열 C의 원소 중 하나라도 나눌 수 있는..

💡문제[level 2] 뒤에 있는 큰 수 찾기 - 154539문제 링크성능 요약메모리: 206 MB, 시간: 259.36 ms  🤔접근법주어진 정수 배열을 순회하면서 본인보다 오른쪽에 있는 수들 중에서 본인보다 크지만 가장 가까이 있는 수 찾기범위 체크 및 시간복잡도 예상1 ≤ N ≤ 1,000,000O($NlogN$) 보다 더 작아야 한다. 풀이법❌ 접근 방법. 완탐주어진 정수 배열을 인덱스 0 ~ N 까지 반복가르키는 정수로부터 오른쪽에 존재하는 모든 정수를 탐색만약 본인보다 큰 정수가 나오면 answer에 저장하고 정지➡️ 해당 풀이법의 시간 복잡도 : $O(N^2)$ → 시간 초과 ⭕ 접근 방법. stack을 사용하자 !스택에는 정수배열의 인덱스와 값을 넣는다.스택은 top 보다 값이 작을때만..

🤔Merge Sort(병합정렬) 이란 ? 병합 정렬은 분할 정복 (Divide and Conquer) 방식을 이용해서 하나의 리스트를 두 개의 리스트로 분할한 다음 각각의 분할된 리스트를 정렬한 후에 합해서 정렬된 하나의 리스트로 만드는 정렬 알고리즘 💡 과정 주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (Divide : 분할) → mergeSort() 메소드 해당 부분리스트의 길이가 1이 아니라면 1번 과정을 되풀이한다. → if (start == end) return; 인접한 부분리스트끼리 정렬하여 합친다. (Conqure : 정복) → merge() 메소드 ⚡ 특징 시간 복잡도 : 최선, 평균, 최악 모두 $O(NlogN)$ 데이터를 “비교”하면서 찾기 때문에 비교정렬 추가 메모리 필요 ..

💡문제 [Gold V] 개똥벌레 - 3020 문제 링크 성능 요약 메모리: 29804 KB, 시간: 252 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000 $O(\sqrt {NH}$ 또는 $O(N)$ 이하 이어야 한다. 풀이법 ❌ 접근 방법. 완탐 H개의 높이에 대해서 N개의 장애물에 대해 탐색하며 몇개의 장애물을 통과해야할지 판별→ $O(NH)$ ➡️ 해당 풀이법의 시간 복잡도 : $O(NH)$ 당연히 시간복잡도 초과 ❌ 접근 방법. 완탐 높이 H를 인덱스로 가지는 배열을 생성 장애물을 차례대로 탐색하며 높이에 장애물이 존재하는 높이에 업데이트 → $O(NH)$ 길이가 2인 석순이라면 높이 1에 +1, 높이 2에 +1 길..

💡문제 [Gold III] 두 배열의 합 - 2143 문제 링크 성능 요약 메모리: 112696 KB, 시간: 556 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 -1,000,000,000 ≤ T ≤ 1,000,000,000 (십억) 1 ≤ n ≤ 1,000, 1 ≤ m ≤ 1,000 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수 $O(\sqrt T)$ 또는 $O(n^2)$이하 이어야 한다. 풀이법 ❌ 접근 방법. 완탐 배열 A의 가능한 부분 배열 만들기 → $O(N^2)$ 배열 B의 부분합이 T-(배열 A의 부분합)인 모든 부 배열 찾기 → $O(N^2)$ ➡️ 해당 풀이법의 시간 복잡도 : $O(N^4)$ 당연히 시간복잡도 초과 ⭕ 접근 방법. Map을 이용해 누..

[Silver II] 수들의 합 4 - 2015 문제 링크 성능 요약 메모리: 35852 KB, 시간: 312 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 1 ≤ N ≤ 200,000 |K| ≤ 2,000,000,000 (20억) $O(N\sqrt N)$ 이하 이어야 한다. 풀이법 ❌ 접근 방법. 완탐 시작점이 0 ~ N-1 , 끝점이 0 ~ N-1로 두고 가능한 모든 부분 배열을 지정한다. → $O(N^2)$ 부분 배열을 순회하며 부분합을 구한다. → $O(N)$ 부분합이 k와 같은지 비교한다. ➡️ 해당 풀이법의 시간 복잡도 : $O(N^3)$ 시간복잡도가 너무 커서 시간이 부족하다. ❌ 접근 방법. 누적합 누적합 배열($S_n)$을 만든다. → $O(N)$ $S_b-S_{..

## 💡문제 ### [Silver II] 조합 0의 개수 - 2004 [문제 링크](https://www.acmicpc.net/problem/2004) #### 성능 요약 메모리: 11564 KB, 시간: 76 ms --- #### [깨진 부분은 여기에서 확인](https://velog.io/@dksek3050/%EB%B0%B1%EC%A4%80-Java-2004%EB%B2%88-%EC%A1%B0%ED%95%A9-0%EC%9D%98-%EA%B0%9C%EC%88%98%EC%A0%95%EC%88%98%EB%A1%A0) ## 🤔접근법 ### 범위 체크 및 시간복잡도 예상 - 0 ≤ m ≤ n ≤ 2,000,000,000 (20억) n ≠ 0 - $O(\sqrt N)$ 또는 $O(logN)$ 이어야 한다. ###..

💡문제 [Gold V] 실질적 약수 - 2247 문제 링크 성능 요약 메모리: 11588 KB, 시간: 732 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 1 ≤ n ≤ 200,000,000 .. 2억 시간 제한이 2초라 $O(N)$ 도 가능할 거 같다. 풀이법 ❌ 첫번째 접근 방법 . 에라토스테네스의 체 소수 판별 (에라토스테네스의 체) $O(log(logN))$ 소수가 아닌 N에 대해 순회 $O(N)$ → (여기가 이미 188,921,062) 실질적 약수 구하기 SCD(N) $O(\sqrt N)$ ➡️ 해당 풀이법의 시간 복잡도 : $O(N\sqrt N)$이다 ⭕ 두번째 접근 방법 . N까지 x의 배수의 개수 1 ~ N까지 순회 $O(N)$ N 이하의 수에서 어떤 수 i를 ..

💡문제 [Gold V] 등차수열과 쿼리 - 23888 문제 링크 성능 요약 메모리: 324788 KB, 시간: 1360 ms 깨진 부분은 여기에서 확인 🤔접근법 범위 체크 및 시간복잡도 예상 1 ≤ $a$ ≤ $10^6$, 0 ≤ $d$ ≤ $10^6$ 1 ≤ $q$ ≤ $10^6$ 1 ≤ $l$ ≤ $r$ ≤ $10^6$ 완탐은 힘들듯 하다. $O(\sqrt N)$ 또는 $O(Nlog{N})$ 이어야 한다. 풀이법 1 $l$ $r$ : $l$ 번째 항부터 $r$ 번째 항까지의 합 → 등차수열 합공식 등차 수열의 합공식을 이용하면 상수 시간으로 구할 수 있을 것이라고 생각했다. 등차수열 합공식 : 항의 개수 * (첫째항 + 끝항) / 2 항의 개수가 n개인 등차 수열의 첫째항을 a, 끝항을 $l$ , 공..

💡문제 [Silver III] 소수의 자격 - 6219 문제 링크 성능 요약 메모리: 16376 KB, 시간: 148 ms 🤔접근법 범위 체크 및 시간복잡도 예상 범위 : 1 ≤ A ≤ B ≤ 4,000,000 , B ≤ A + 2,000,000 범위 순회 * 소수 판정 $O(N^2)$은 최대 범위가 2백만이라 어렵다. $O(N\sqrt N)$도 1,000,000 * 1000 이라 어렵다 . $O(Nlog{N})$ 은 될 지 잘 모르겠다. 가능할듯 (대충 N * 8 정도 예상…) $O(\sqrt N)$ 또는 $O(Nlog{N})$ 이어야 한다. 풀이법 🅰️ 첫 번째 접근방법. 완탐 ⭕ 범위 A ~ B 까지 순회하면서 각 숫자들이 소수인지 판별 소수이면 D를 포함하는지 판별 ➡️ 해당 풀이법의 시간 복잡도..

💡문제 [Gold IV] 2로 몇 번 나누어질까 - 1407 문제 링크 성능 요약 메모리: 11552 KB, 시간: 76 ms 🌟풀이 범위가 무려 1≤A≤B≤$10^{15}$ 로 엄청나다. 그래서 A ~ B 까지 순회하면서 더할 수는 없다. 1 ~ n까지 소수 x의 배수의 개수를 구하는 방식을 이용하였다. 1 ~ n까지 수들은 소수 x로 몇번 나누어 떨어질까 ? 1부터 20까지 순회하며 각 수를 소인수분해 했을때 2가 몇 번씩 들어가는지 적어보았다. 이를 2가 들어간 횟수만큼 동그라미로 표현하게 되면 아래 사진과 같이 표시되며 오른쪽과 같은 의미를 가질 수 있다. 위를 참고하여 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 ..

Binary Search (이분탐색) 이란? "정렬"되어 있는 배열에서 특정 값의 위치를 찾는 탐색알고리즘이다. 탐색하는 배열을 둘로 나누고 찾고자하는 값이 존재하는 영역만 탐색하기 때문에 전체를 탐색하는 경우보다 당연히 빠르게 찾을 수 있다. 더보기 백준 문제 1. 수 찾기 https://www.acmicpc.net/problem/1920 과정 내가 찾고자하는 값을 '타겟'이라고 하자. 이분탐색은 주로 배열에서 타겟의 위치(인덱스)를 찾고자 할 때 많이 사용된다. 1. 탐색할 배열을 정렬한다. 2. 탐색할 영역의 중앙값( = (시작점 + 끝점)/2)이 타겟과 비교한다. 2-1. 중앙값이 타겟과 같다면 중앙값의 위치를 반환하고 탐색을 종료한다. 2-2. 타겟이 중앙값보다 작다면 다음엔 중앙값을 기준으로 ..

[Platinum V] 숨바꼭질 5 - 17071 문제 링크 성능 요약 메모리: 89244 KB, 시간: 248 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색 문제 설명 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위..

[Gold I] 열쇠 - 9328 문제 링크 성능 요약 메모리: 320872 KB, 시간: 1328 ms 분류 너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현 문제 설명 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다. 각 테스트 케이스의 첫째 줄에는 지도의 높이와 너..

[Gold III] 줄 세우기 - 2252 문제 링크 성능 요약 메모리: 46084 KB, 시간: 4360 ms 분류 그래프 이론, 위상 정렬 문제 설명 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 ..

Topology Sort (위상 정렬) 이란? 위상 정렬은 사이클이 없는 방향그래프 (DAG: Directed Acyclic Graph)에서 각 정점의 선후를 위배하지 않고 정렬하는 알고리즘이다. 정해진 선후만 위배하지 않으면 되기 때문에 정렬된 결과가 여러개가 나올 수 있다. 작업의 순서가 정해져 있을때 일직선의 순서를 찾는 알고리즘이라고 생각하면 편하다. ex ) 집도착 → 손발 씻기 → 밥먹기 → 설거지하기 → 과제하기 → 유튜브 보기 → 잠자기 이때 주어진 엣지의 방향만 지키면 된다. 만약 기초수학 → 물리 기초수학 → 화학 이라는 선후가 주어진다면 기초수학→물리 → 화학 도 괜찮고 기초 수학 →화학 →물리 도 괜찮다 같이보면 좋은 백준 문제 더보기 백준 문제 https://www.acmicpc...

[Silver V] 수 정렬하기 2 - 2751 문제 링크 성능 요약 메모리: 134424 KB, 시간: 692 ms 분류 정렬 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 💡 나의 접근 주어진 N의 개수가 1,000,000이기 때문에 O(N^2) 시간복잡도를 가지게 되면 터지게 된다. 그래서 O(NlogN)이나 O(N) 시간복잡도를 가지는 정렬을 생각해 보아야 할 것이다. A..

Counting Sort (계수 정렬) 이란? 계수 정렬은 값을 비교하지 않고 각 값들의 개수를 세어서 그 값들이 몇번째 인덱스 부터 몇번째 인덱스까지 위치하는 지를 알아내 정렬하는 알고리즘이다. 더보기 백준 문제 https://www.acmicpc.net/problem/2751 과정 과정은 간단하다. 1. 가장 큰 값 찾기 -> 큰 값까지 인덱스를 가지는 배열 만들기 2. 만든 배열에 인덱스를 값으로 하는 값의 개수 담기 3. 각 값의 개수를 누적으로 바꾸기 4. 뒤에서부터 자리 찾아주기 위 순서에 따라서 위 arr 배열을 정렬해보자 1. 가장 큰 값을 찾는다. ➡️ max = 5 2. 각 값의 개수를 담는다. arr값을 인덱스로 하여 arr의 값의 개수를 담는 count 배열을 만든다. 3. 각 값의..