Arrays.sort() 배열을 정렬하는데 사용 ('int [] ', 'String []' 등) 기본 데이터 타입 배열, 객체 배열 모두에 사용 가능 주어진 배열 직접 변경 Collections.sort() 컬렉션을 정렬하는 데 사용('List', 'Set' 등) 주어진 컬렉션을 직접 변경 둘 다 Comparable 인터페이스나 Comparator 인터페이스 중 하나를 구현하고 있어야 한다. 이 둘의 차이는 무엇일까? 알아본다. Comparable 인터페이스 객체가 자연스러운 순서를 갖도록 하는 것이 목표 객체 자체가 비교 로직을 구현 `compareTo` 메소드 제공해야함 메소드는 현재 객체가 다른 객체보다 작으먄 음수, 같은 0, 크면 양수를 반환해야 함 List people = new ArrayLi..

1. 문제 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net - 주어진 한 정점 부터 각 모든 정점 최소 경로 구하기 2. 해결 포인트 이 문제는 주어진 노드의 제한이 크기 때문에 정점마다 탐색을 진행할 수 없다. 최소 경로 문제에 쓰이는 알고리즘이 필요하다. 한 노드에서 각 모든 노드까지 가는 최단 경로를 구할 수 있는 다익스트라 알고리즘을 쓴다. 다익스트라(Dijkstra) 알고리즘 한 노드에서 각 모든 노드까지 가는 최단 경로를 구하는 알고리즘. 음의 간선을 포함할 수..

1. 문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 길이가 N인 계단 수가 몇 개? 계단 수란 인접한 모든 자리의 차이가 1인 수를 말한다. 1

1. 💎 문제 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 2. 🤔 어떻게 풀까 현재 위치에서 이동할 수 있는 경우의 수는 2가지 뿐이다. 오른쪽 또는 아래로 현재 칸에 적혀있는 수만큼 이동하는 것이다. 그러므로 위치마다 2가지 경우를 고려하여 경우의 수를 누적한다. 코드가 짧아 바로 전체 코드로 간다. 3. 🖥️ 전체 코드 행렬의 순서대로 요소를 탐색한다. 현재 칸에 적혀있는 수만큼 오른쪽, 아래로 이동하여 이동한 위치의 경우의 수를 증가시킨다. int length = (int)map[i][j..

1. 💎 문제 2. 🤔 어떻게 풀까 N개의 크레인 -> 동시에 이용 가능 각 크레인에는 실을 수 없는 무게 제한이 있음(포함) 이 두가지 조건을 중심으로 생각했다. 최소의 시간이 걸리기 위해서는 크레인들에게 균형있게 화물을 분배해줘야 한다. 이때 무게가 작은 박스는 어떠한 크레인이든 사용할 수 있지만, 무게가 커질 수록 사용할 수 있는 크레인은 적다. 그러므로 무게가 무거운 박스를 어떻게 분배하면 좋을지 생각했다. 해답은 무거운 박스부터 적절한 크레인을 선택하여 싣게하는 것이다. 적절한 크레인을 어떻게 고르냐 생각했을 때, 그 순간 무게 제한이 박스의 무게를 포함하면서, 이동시켜야할 박스의 수가 제일 적은 것을 선택하기로 했다. 결국 중요한 것을 균형있는 분배이다. 그러므로 제일 작업량이 작은 크레인을 ..

1. 💎 문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 한 계단, 두 계단 씩만 이동 가능 연속한 3개의 계단 불가 마지막 계단 반드시 밟음 얻을 수 있는 총 점수의 최댓값 구하기 2. 🤔 풀이 생각 이 문제의 핵심은 2계단을 가면 무조건 이동해야 한다는 것이다. 3 계단을 가지 전에 끊어줘야 하므로, 현재 계단에서 선택할 수 있는 경우의 수는 2가지뿐이다. 1. 직전의 계단(n-1)을 밟고 현재 계단을(n)을 밟는다. 2.두 번째 전 계단(n-2)을 밟고 현재 계단(n)을 밟는다. 여기서 1번은 세 계단을 이어서..

합병 정렬 개념 리스트를 두 개의 균등한 크기로 분할하고 분할된 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하기를 반복하면서 전체를 정렬한다. 분할 정복 기법 알고리즘 중 하나이다. 분할 정복 기법 (divide and conquer) 문제를 작은 2개의 문제로 분리하고 각 문제를 해결 후, 결과를 모아서 원래의 문제를 해결하는 전략 구체적인 알고리즘 합병 정렬은 다음 3가지 단계를 반복하며 정렬을 한다. 분할(Divide) : 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 충분히 작아질 때까지 분할을 반복한다. 결합(Combine): 정렬된 부분 배열들을 하나의 배열로 통합한다. 부분 리스트의 크기가 1개가..

알고리즘 퀵 정렬은 기준값(pivot)을 선정해 해당 값도가 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 평균적인 시간 복잡도는 O(nlogn)으로 다른 O(nlogn)의 알고리즘 중 가장 빠르다고 평가 된다. 구체적인 내용 기준점을 정하고 기준점을 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 이동 시키며 정렬을 진행 한다. 이때 기준점이 되는 레코드는 한 번 정렬이 완료되면 더 이상 자리가 바뀌지 않는다. partition 함수를 통해 피봇을 기준으로 왼쪽, 오른쪽을 나누게 된다. 최종적으로 피봇의 위치는 low가 higt보다 커지는 순간으로 결정된다. 이렇게 피봇을 기준으로 한 번 정렬된 리스트는 다시 왼쪽, 오르쪽 리스트로 쪼개져 partition 함수를 호출하며 리스..

알고리즘 손 안의 카드 정렬을 하는 것과 유사하다. 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입! 왼쪽 리스트에 정렬이 완료된 요소를 1개, 2개 점점 개수를 늘려가면서 정렬이 완료된다. 구체적인 알고리즘 1. 인덱스 1부터 시작한다. 2. 현재 삽입될 요소인 i번째 요소를 key 변수에 복사 3. i-1번째 부터 역순으로 조사 4. j가 0보다 작아지거나 key값보다 정렬된 배열에 있는 값이 크면 5. j번째는 j+1번째로 이동한다. 6. j를 하나 감소한다. 7. j번째 정수가 key보다 작으므로 j+1번째가 key값이 들어갈 위치이다. 코드 // 정렬 - 삽입 정렬 int i,j; for(i= 1; i=0&&num..

문제 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 접근법 N은 최대 10자리 숫자로 매우 큰 메모리 공간을 차지함. 하지만 이 문제는 자릿수의 숫자들을 뽑아 정렬하는 것이므로 String 객체로 입력을 받아 쪼개 Int형 배열로 만드는 것이 효율적이라 생각이 들었다. 그 후 최대 10개의 숫자를 정렬하는 것은 아무 정렬법이나 쓰면 된다. 풀이 코드 public class Main { public static void main(String[] args) throws IOException { // 문자열로 입력 받기 Scanner..