분류 전체보기
자바로 구현한 버블 정렬(거품 정렬) 알고리즘
자바로 구현한 버블 정렬(거품 정렬) 알고리즘
2023.02.22버블 정렬은 두개의 인접한 원소를 비교하는 형식의 정렬방식입니다. 버블 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 안정 정렬입니다. 1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다. 2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다. 3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다. 버블정렬 과정을 요약하면 다음과 같습니다. 1. 처음 원소부터 차례대로 인접한 원소를 비교하고 교환한다. 2. 마지막 원소를 1번을 반복하면서 저장한다. 3. 모든 원소가 저장되거나 교환이 없다면 정렬이 종료된다. 그림으로 보겠습니다. 그림으로 보면 크게 어려움 없이 알고리즘 이해가 될것입니다. 그럼 자바로 구현해보겠습니다. 전체코드 ..
문제 번호 2787번 : 대표값2 - JAVA [자바]
문제 번호 2787번 : 대표값2 - JAVA [자바]
2023.02.22https://www.acmicpc.net/problem/2587 2587번: 대표값2 어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30의 평균은 (10 + 40 + 30 + 60 + www.acmicpc.net 문제 설명 간단하게 수를 정렬하여 중간값을 찾고 평군을 내는 문제입니다. 문제 풀이 해당 문제는 삽입정렬을 사용해서 풀도록 하겠습니다. 삽입 정렬에 대한 내용은 삽입 정렬 참고해주세요. 정렬에 대한 이해가 있다면 어렵지 않은 문제일 것입니다. import java.util.Scanner; public class Main { public static void m..
자바로 구현한 삽입 정렬 알고리즘
자바로 구현한 삽입 정렬 알고리즘
2023.02.20삽입 정렬은 Target 인덱스를 정해서 올바른 인덱스에 삽입해 주는 정렬 방식입니다. 삽입 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 안정 정렬입니다. 1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다. 2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다. 3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다. 선택정렬의 정렬 과정을 요약하면 다음과 같습니다. 1. 첫 인덱스와 이미 정렬된 인덱스를 제외한 가장 작은 인덱스를 타깃으로 결정합니다. 2. 타겟과 타깃보다 작은 인덱스의 값들을 비교하여 정렬합니다. 3. 모든 인덱스가 정렬될 때까지 1,2번 과정을 반복합니다. 그림으로 보겠습니다. 그림으로 보시게 되면 큰 어려..
자바로 구현한 선택 정렬 알고리즘
자바로 구현한 선택 정렬 알고리즘
2023.02.20선택 정렬알고리즘은 O(N2)의 시간 복잡도를 가지는 정렬 알고리즘 중에 하나입니다. 선택 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 불안정 정렬입니다. 1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다. 2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다. 3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다. 선택정렬은 이름에서와 같이 최솟값을 찾아 선택하여 선수대로 교환하는 정렬방식입니다. 정렬 과정을 요약하면 다음과 같습니다. 1. 해당 리스트의 최솟값을 찾는다. 2. 리스트의 맨 처음 인덱스와 교환한다. 3. 교환한 인덱스를 제외한 리스트에서 최솟값을 찾고 정렬된 인덱스를 제외한 맨 앞 인덱스와 교환한다. 알고리즘..
문제 번호 2750번 : 수 정렬하기 - JAVA [자바]
문제 번호 2750번 : 수 정렬하기 - JAVA [자바]
2023.02.15https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 설명 간단하게 수를 정렬하는 문제입니다 문제 풀이 해당 문제는 선택정렬을 사용해서 풀도록 하겠습니다. 선택정렬에 대한 내용은 해당 글에서 설명되어 있습니다. 정답코드 import java.util.Random; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Sc..
Java로 구현한 Heap 자료구조(트리 구조)
Java로 구현한 Heap 자료구조(트리 구조)
2023.02.08이번 글에서는 Heap 자료구조에 대해 설명하겠습니다. 백준 알고리즘을 푸는 글이 많은데 알고리즘과 자료구조는 굉장히 깊은 관계가 있기 때문에 자료구조에 대한 공부 한 것을 종종 기록해 공유하도록 하겠습니다. 목차 더보기 1. Heap 자료구조란? 2. Heap 자료구조 자바 구현 1) Heap 자료구조의 생성자와 변수 2) Heap 자료구조의 인덱스 구하는 함수와 배열 길의 재정의 함수 3) Heap 자료구조의 노드 추가 함수 4) Heap 자료구조의 삭제 함수 3. Heap 자료구조 TEST 1. Heap 자료구조란? Heap 자료구조는 Heap 정렬에서 사용되는 자료구조입니다. 이번 글에서는 단순이 int형만 만들어지는 것이 아니라 객체도 만들 수 있도록 구현하도록 하겠습니다. 상당히 복잡한 부분도..
문제 번호 24060번 : 병합 정렬 1 - JAVA [자바]
문제 번호 24060번 : 병합 정렬 1 - JAVA [자바]
2023.01.21https://www.acmicpc.net/problem/24060 24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 문제 설명 재귀를 사용한 병합 정렬에서 정렬되는 순서에 따른 값을 출력하는 문제입니다. 문제 풀이 문제에서는 병합정렬 로직이 풀이로 나와있지만 해당 언어를 알지 못하거나 병합정렬 알고리즘에 대한 이해가 없으면 풀기가 쉽지 않습니다. 병합 정렬에 대한 내용은 다음 게시물에 올려놓았습니다. 병합정렬이 관하여 자바로 구현한 합병 정렬(병합 정렬) 알고리즘..
자바로 구현한 합병 정렬(병합 정렬) 알고리즘 - 분할 정복
자바로 구현한 합병 정렬(병합 정렬) 알고리즘 - 분할 정복
2023.01.18목차 더보기 1. 합병 정렬에 관하여 2. 분할 정복 알고리즘에 관하여 3. 병합 정렬 알고리즘 로직과 질문 4. 병합 정렬 알고리즘 자바 구현 - [TOP-DOWN] - [BOTTOM-UP] 5. 병합 정렬 알고리즘 장단점 1. 합병 정렬에 관하여 합병 정렬 알고리즘은 정렬 알고리즘의 하나로 분할 정복을 사용한 알고리즘입니다. 합병 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬이 아닙니다. 3. 안정정렬입니다. 1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다. 2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다. 3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다. 2. 분할 정복 알고리즘에 관하여 그럼 분할 정복이 무엇인지 알아보겠..
문제 번호 2566번 : 최댓값 - JAVA [자바]
문제 번호 2566번 : 최댓값 - JAVA [자바]
2022.12.15https://www.acmicpc.net/problem/2566 2566번: 최댓값 첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다. 최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다. www.acmicpc.net 문제 설명 행열에 대해 최대값과 그 위치를 찾아 출력하는 문제입니다. 문제 풀이 2차원 배열을 선언하고 이중 for문을 통해 최대값을 구했습니다. 코드를 보시면 바로 이해가 되실 겁니다. import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int max..
문제 번호 25501번 : 재귀의 귀재 - JAVA [자바]
문제 번호 25501번 : 재귀의 귀재 - JAVA [자바]
2022.12.15https://www.acmicpc.net/problem/25501 25501번: 재귀의 귀재 각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다. www.acmicpc.net 문제 설명 문자열에 앞뒤가 같은지 재귀를 사용하여 확인하는 문제입니다. 문제 풀이 사실 문제속에 정답이 다 있습니다. 문제를 보고 조금 당황했어요. 반복문과 출력만 해주면 됩니다. import java.util.Scanner; public class Main { static int count = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n ..
문제 번호 10870번 : 피보나치 수 5 - JAVA [자바]
문제 번호 10870번 : 피보나치 수 5 - JAVA [자바]
2022.12.14https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 설명 피보나치 수열은 유명한 수열문제중에 하나입니다. 재귀를 이용해 풀어보도록 하겠습니다. 문제 풀이 재귀 문제를 만나면 어떻게 재귀를 만들어야 하는지 막막 할 수 있습니다. 그럴때는 먼저 반복문으로 해당 문제를 풀어보는 것이 중요합니다. 그러면 어떻게 재귀를 사용해야하는지 감이 오기 시작합니다. 반복문으로 다음과 같이 할 수 있습니다. public s..
문제 번호 10872번 : 팩토리얼 - JAVA [자바]
문제 번호 10872번 : 팩토리얼 - JAVA [자바]
2022.12.14https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 설명 하나의 수가 주어지면 그 수부터 1까지 모든 수를 곱한 수를 구하는 문제입니다. 재귀를 이용하여 풀어보겠습니다. 문제 풀이 사실 이 문제에서 재귀와 반복문이 다를 것이 없습니다. 어떻게 재귀를 반복문처럼 쓰는지 밑에 코드로 보여드리겠습니다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //팩토리얼 변수 int n =..