본문 바로가기

전체 글411

[알고리즘] 병합 정렬 (Merge Sort) 목차 병합 정렬이란? 병합 정렬은 분할 정복 (Divide and Conquer) 방식을 이용해서 하나의 리스트를 두 개의 리스트로 분할한 다음 각각의 분할된 리스트를 정렬한 후에 합해서 정렬된 하나의 리스트로 만드는 정렬 알고리즘이다. 추가로 병합 정렬은 퀵 정렬과 달리 정렬을 할 때 데이터 크기만큼의 추가 공간이 필요하므로 제자리 정렬 (in-place sort)이 될 수는 없다. 병합 정렬은 분할 정복의 다음과 같은 과정을 거친다. 분할(Divide) : 리스트를 두 개의 리스트로 분할한다 정복(Conquer) : 분할된 리스트를 정렬한다. 결합(Combine): 정렬된 두 개의 리스트를 하나의 정렬된 리스트로 결합한다. 이제 병합 정렬의 예시를 한번 살펴보겠다. 병합 정렬 병합 과정 분할된 리스트.. 2022. 7. 28.
[백준] 10845번 : 큐 – JAVA [자바] https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 문제 풀이 백준 10845번 큐는 실버 4 난이도의 자료 구조 및 큐 문제이다. 이 문제는 간단히 문제에 나와있는 명령어 6개를 구현하면 된다. 만약 큐에 대해 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/18 [자료구조] 큐(Queue) 목차 큐(Queue)의 개념 큐는 FIFO 선입선출(First In Fi.. 2022. 7. 26.
[백준] 2752번 : 세수정렬 – JAVA [자바] https://www.acmicpc.net/problem/2752 2752번: 세수정렬 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. www.acmicpc.net 문제 문제 풀이 백준 2752번 세수정렬은 브론즈 4 난이도의 정렬 문제이다. 이 문제는 되게 간단하다. 입력으로 3개의 숫자가 주어지고 이 숫자를 정렬해서 출력해주면 된다. 이 문제는 자바에서 기본으로 제공되는 Arrays.sort() 함수를 이용해서 풀어도 되고 아니면 퀵 정렬, 선택 정렬이나 삽입 정렬 등을 직접 구현해서 풀어도 된다. 만약에 이 정렬 알고리즘들을 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.c.. 2022. 7. 26.
[알고리즘] 퀵 정렬 (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.
반응형

티스토리툴바