본문 바로가기

전체 글376

[알고리즘] 퀵 정렬 (Quick Sort) 목차 퀵 정렬이란? 퀵 정렬은 분할 정복 (Divide and Conquer)과 재귀 방식을 이용한 정렬 알고리즘이다. 분할 정복이란 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 방식이다. 퀵 정렬에서는 pivot이라는 기준을 하나 정하고, 왼쪽은 기준보다 작은 값, 그리고 더 큰 값은 기준 오른쪽으로 옮기면서 배열을 둘로 분할한 후 정렬한다. 보통 pivot은 맨 앞이나 맨 뒤, 혹은 중간에 위치한 값을 선택한다. 퀵 정렬 과정 배열 맨 앞에 있는 수를 pivot으로 설정한다. 그리고 배열의 길이가 n일 때, 배열의 시작점은 0이 되고 도착점은 n - 1이 된다. pivot 값을 기준으로 시작점에서부터 검사해서 큰 값을, 도착점에서부터 작은 값을 찾는다.. 2022. 7. 25.
[백준] 1427번 : 소트인사이드 – JAVA [자바] https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 문제 풀이 백준 1427번 소트인사이드는 실버 5 난이도의 문자열 및 정렬 문제이다. 이 문제에서는 숫자 N이 주어진다. 그리고 이 N의 자릿수들을 내림차순으로 정렬한 뒤에 출력해주기만 하면 된다. 즉, 예를 들어서 2143이 들어오면 4321로 출력해주면 된다. 자바에서는 내림차순으로 정렬을 할 때 마찬가지로 Arrays.sort() 함수를 사용하기는 한다. 다만, 매개 변수로 정렬할 배열과 Collections.reverseOrder()를 포함시켜 주어야 한다. 이 Coll.. 2022. 7. 25.
[백준] 10989번 : 수 정렬하기 3 – JAVA [자바] https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 문제 풀이 백준 10989번 수 정렬하기 3은 브론즈 1 난이도의 정렬 문제이다. 이 문제는 되게 간단하다. N개의 수가 주어지고 이 N개의 수를 오름차순으로 정렬을 해서 그대로 출력만 해주기만 하면 된다. 이 문제는 자바에서 기본으로 제공되는 Arrays.sort()를 이용해서 풀 수 있다. Arrays.sort()는 매개 값으로 주어지는 배열을 오름차순으로 정렬하는 역할을 한다. 즉, 주어지는 N개의 수들을.. 2022. 7. 24.
[백준] 7568번 : 덩치 – JAVA [자바] https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제 문제 풀이 백준 7568번 덩치는 실버 5 난이도의 구현 및 브루트 포스 문제이다. 이 문제에서는 N명의 키와 몸무게가 주어진다. 그리고 한 사람의 키와 몸무게가 다른 사람보다 더 크면 그 사람은 덩치가 더 크다고 한다. 이때, N명의 키와 몸무게가 주어질 때 덩치 등수를 출력하면 된다. 이 문제는 정렬을 안 쓰고서도 풀 수 있다. 브루트 포스, 즉 가능한 모든 경우를 봐야 한다.. 2022. 7. 22.
[알고리즘] 삽입 정렬 (Insertion Sort) 목차 삽입 정렬이란? 삽입 정렬이란 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신이 들어갈 위치를 찾아 삽입함으로써 정렬을 하는 알고리즘이다. 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. 삽입 정렬의 원리는 두 번째 자료부터 시작해서 그 앞의 정렬되어 있는 자료들과 비교하여 삽입할 위치를 찾은 뒤에 자료를 뒤에 옮기고 지정한 자료를 삽입하여 정렬하는 알고리즘이다. 즉, 2번째 자료는 1번째 자료, 3번째 자료는 2번째와 1번째 자료, 4번째 자료는 3번째, 2번째, 1번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 이제 예시를 한번 보겠다. 소스 코드 static void insertionSort() { int j, temp; int .. 2022. 7. 21.
[백준] 2581번 : 소수 – JAVA [자바] https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 문제 문제 풀이 백준 2581번 소수는 실버 5 난이도의 수학 문제이다. 이 문제에서는 입력으로 자연수 M과 N이 주어진다. 그리고 M이상 N이하인 소수들의 합과 소수의 최솟값을 출력하면 된다. 만약에 이 범위 안에 소수가 없을 때는 -1을 출력하면 된다. 이 문제는 소수 판별 알고리즘인 에라토스테네스의 체를 이용해서 풀 수 있다. 에라토스테네스의 체 이론을 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다.. 2022. 7. 16.
[백준] 2960번 : 에라토스테네스의 체 – JAVA [자바] https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 문제 문제 풀이 백준 2960번 에라토스테네스의 체는 실버 4 난이도의 수학, 구현 및 에라토스테네스의 체 문제이다. 이 문제에서는 정수 N과 K가 주어진다. 2부터 N까지 에라토스테네스의 체 알고리즘을 적용시킨다고 할 때 K번째로 지우는 수를 출력하면 된다. 참고로 원래 에라토스테네스의 체 알고리즘에서는 숫자의 배수만 지운다. 즉, 예를 들어서 2의 배수를 지울 때 2는 원래는 안 지우는데 이 문제에서는 2도 같이 지워야 한다. 만약에 에라토스테네스의 체에 대해서 잘 모른다면 밑에 .. 2022. 7. 16.
[알고리즘] 버블 정렬 (Bubble Sort) 목차 버블 정렬이란? 버블 정렬이란 옆에 있는 값과 비교해서 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법이다. 만약에 내림차순으로 정렬을 한다고 하면 옆에 있는 값과 비교해서 더 큰 값을 앞으로 보내면 된다. 우선 예시를 하나 살펴보겠다. 다음과 같은 배열을 오름차순으로 정렬한다고 가정하겠다. 우선 첫 번째와 두 번째 숫자, 즉 4와 2를 비교한다. 2가 4보다 더 작으니 더 작은 숫자인 2를 앞으로 보낸다. 그다음에는 두 번째와 세 번째 숫자, 즉 4와 1을 비교한다. 비교하고 더 작은 1을 앞으로 보낸다. 4와 5를 비교했을 때 4가 더 작으니 건너뛴다. 이 과정을 끝까지 반복하면 다음과 같다. 이 예시에서 알 수 있듯이 더 큰 숫자가 계속 뒤로 밀려나고 마지막에는 가장 큰 숫자가 맨 뒤로 밀려.. 2022. 7. 16.
반응형

티스토리툴바