본문 바로가기
반응형

알고리즘104

[Java][알고리즘][정렬] Selection Sort / 선택 정렬 정렬에 대해서 쭉 포스팅을 시작하겠다! 선택 정렬 선택정렬은 배열에서 아직 정렬되지 않은 부분의 원소 중에서 최솟값을 찾아 정렬된 부분의 바로 오른쪽 원소와 교환하는 알고리즘이다. 따라서 for문을 돌면서 min을 i번째로 설정하고 정렬이 안된 부분에서 최솟값을 찾아 교환해주면 된다. 모든 요소에 대해 i를 정하고 정렬 안된 부분이 하나씩 줄어들면서 계속 비교하므로 시간 복잡도는 O(N^2)이 된다. 가장 기본적인 정렬이지만 시간 복잡도가 좋지는 않으니 거의 사용하지 않는다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 public class Selection { public stat.. 2019. 6. 4.
[Java][백준][11650번] 좌표 정렬하기 문제 설명 (링크) 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 생각 이런 좌표가 주어지고 그 좌표의 정보가 2개 이상 주어진 경우는 클래스로 만들어서 하면 깔끔하고 좋다. 좌표 클래스를 만들고 변수로 x,y를 준다. 후에 Comparable를 상속하여 새로운 정렬 조건을 만들어준다. 코드 1 2 3.. 2019. 6. 2.
[Java][백준][1946] 신입사원 문제 설명 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오. 첫째 줄.. 2019. 5. 31.
[Java][백준][11047번] 동전 0 문제 설명 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 생각 원래 동전 문제는 동적계획법으로 푸는 것이 맞다. 그리디 알고리즘으로 풀면 오류가 날 수 있기 때문이다. (예를 들어 20원을 세려고 할 때 동전이 16원,10원,1.. 2019. 5. 30.
반응형

티스토리툴바