Java

Algorithm

[Algorithm] 여러 가지 정렬1 - 간단하지만 느린 정렬들

2023.01.06

배열을 정렬(오름차순)할 수 있는 여러 가지 방법에 대해서 알아보자. 1. Selection Sort 주어진 배열에서 가장 작은 데이터를 선택하여 앞으로 보내는 정렬 첫 번째 과정에서 가장 작은 데이터를 찾아 배열의 첫 번째 자리에 넣고, 두 번째 과정에서 그 다음 작은 데이터를 찾아 두 번째 자리에 넣고, ... n-1자리까지 반복한다. n개의 데이터에서 가장 작은 데이터를 찾고, n-1개의 데이터에서 가장 작은 데이터를 찾고, 그 다음은 n-2개, n-3개, ... 이렇게 이어지기 때문에 O(N^2)의 시간복잡도를 가진다. public void selectionSort(int[] arr) { for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j ..

Problem Set/Greedy

[Greedy] BOJ 1744 수 묶기 (Java)

2022.09.12

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 분석 수열 N이 주어졌을 때, 수열의 두 수를 묶어서 (순서는 상관없음) 묶은 수들의 합이 최대가 되도록 하는 문제. 묶은 두 수는 곱해지며, 수는 한 번만 묶을 수 있고, 묶지 않을 수도 있다. 예전에 풀었던 문제인데 뭔가 greedy 하지 못하다는 생각이 들어 백준에서 더 깔끔하게 푸신 분들이 없나 참고하였다. 내 코드 import java.io.BufferedReader; import..

[Algorithm] 여러 가지 정렬1 - 간단하지만 느린 정렬들

[Greedy] BOJ 1744 수 묶기 (Java)

티스토리툴바