목록알고리즘/백준 등 알고리즘 문제 (8)

개발자꿈나무

No2750 버블정렬 이용해서 수 정렬하기

[문제] [입출력 형식] 사실 이 문제는 간단하게 풀고자한다면 sort() 메소드를 이용해서 간단하게 풀 수 있다. 나역시 sort 메소드를 이용해서 몇 초만에 문제를 풀었고, 이후에도 유사한 문제들을 sort 메소드를 이용해서 간단하게 풀었지만 그렇게하면 알고리즘 실력을 쌓을 수 없기 때문에 정렬 알고리즘에 대해서 공부를 다시 하고 알고리즘을 활용해서 문제를 풀어봤다. 오늘 공부한 정렬은 버블정렬으로 버블정렬이란 인접한 두 개의 값을 비교해서 정렬을 해주는 알고리즘 방식이다. 간단하게 구현할 순 있지만 시간 복잡도는 O(n제곱)으로 다른 정렬 알고리즘보다 속도가 느린 편이다! [버블 정렬 과정] 위의 예시를 보고 간략하게 설명을 해보자면 현재 [5 2 3 4 1]이란 값이 저장되어있는 상태이고 오름차순..
알고리즘/백준 등 알고리즘 문제 2023. 4. 1. 23:49
No11660 구간합 구하기5

이번엔 1차원 배열을 이용한 구간합 구하기가 아니라 2차원 배열을 이용한 구간합 구하기에 대해서 알아볼 것이다. 2차원 배열 합 배열의 공식을 먼저 살펴보도록 하자. 먼저 기본적인 배열이 아래와 같이 주어져있다고 할 때, 이 배열의 합 배열을 직접 그려가면서 이해해볼 것이다. 회색 칸은 단순히 (0, 0)의 인덱스를 나타낸 것으로 전부 0이라고 생각하면 되고 흰색 칸의 값들이 들어가있다고 할 때 첫번째 행과 첫번째 열의 합부터 구해보면 1차원 배열의 합배열과 똑같은 것을 알 수 있다. 첫번째 열을 구하는 공식은 D[1][j-1] + A[1][j]이고 첫번째 열을 구하는 공식은 D[i-1][1] + A[i][1]이다. 행과 열이 섞여있어 헷갈릴 수 있는데 직접 그림은 그리면서 생각해보면 이해가 될 것이다...
알고리즘/백준 등 알고리즘 문제 2023. 3. 23. 22:41
No11659 구간합 구하기

구간합 문제를 풀기에 압서 배열합과 구간합의 공식과 개념을 먼저 알아볼 필요가 있다. 구간합이란 합 배열을 이용하여 시간 복잡도를 줄이기 위해 사용하는 특수한 목적의 알고리즘 구간합 알고리즘을 활용하려면 합 배열을 구해야 한다! 합 배열 S[i] = A[0] + A[1] + A[2] + ... + A[i] //A[0]부터 A[i]까지의 합 위 그림에서 S[5]의 값은 A[0] + A[1] + A[2] + A[3] + A[4] + A[5]의 값과 같다. 즉, S[i] = S[i-1] + A[i] 라는 공식까지 도달할 수 있다. => S[1] = S[0] + A[1] = 15 + 13 = 28 // S[5] = S[4] + A[5] = 48 + 12 = 60 구간합을 구하는 식도 간편한데 i부터 j까지의 합..
알고리즘/백준 등 알고리즘 문제 2023. 3. 22. 22:31
No9020 골드바흐의 추측(우여곡절이 많았던..)

[문제] [입력 출력 조건] [수도 코드] 소수들의 집합을 먼저 구해야 함 -> 에라토스테네스의 체에 대해서 먼저 알아볼 필요가 있음 일단 먼저 소수란 1과 자기 자신만을 약수로 가지고 있는 자연수라고 할 수 있음 에라토스테스의 체란? 구하고자 하는 구간의 모든 자연수를 나열한 후 소수의 배수들을 전부 지워주는 방식. - 예를 들어 100까지의 소수를 구하고자 한다면 일단 1은 제외하고 제일 작은 값인 2를 소수로 채택 -> 2의 모든 배수들 지우기 - 그 다음 작은 값인 3을 소수로 채택 -> 3의 모든 배수 지우기 - 이런 식으로 배수들을 지워나가면 결국 마지막에는 소수들만 남아있음 에라토스테스의 체를 이용해서 소수면 false로 boolean 배열 안에 저장해놓고, 소수의 값들만 list에 저장 l..
알고리즘/백준 등 알고리즘 문제 2023. 3. 21. 23:31
No1002 : n개의 최대공약수, 최소공배수

문제 기존의 최대공약수, 최소공배수 푸는 방법과 똑같은데 갯수가 2개가 아니라 3개 이상이라는 점만 다름 package jungol_Beginner; import java.util.Scanner; public class No1658 { static int recursive(int x,int y) { if(y==0) return x;// y=0이면 최대 공약수는 x가 됨. 재귀는 끝나는 포인트를 꼭 지정해줘야함. return recursive(y, x%y); // 재귀적호출. 본인을 계속해서 호출. } public static void main(String[] args) { // 최대공약수 최소공배수(n개의) Scanner in = new Scanner(System.in); int N; int lcm; i..
알고리즘/백준 등 알고리즘 문제 2023. 2. 18. 20:58
No1658 : 최대공약수와 최소공배수 구하기

첫 번째 방법 : 기본적인 방식 더보기 최대공약수(gcd)란? - 두 수 이상의 공통인 약수(공약수) 중 가장 큰 수 8, 12의 공약수 : 1, 2, 4 최대공약수 : 4 최소공배수(lcm)란? - 두 수 이상의 공통인 배수(공배수) 중 가장 작은 수 8, 12의 공배수 : 24, 48 ... 최소공배수 : 24 import java.util.Scanner; public class No1658 { static int gcd_get(int x,int y) { int i; int ans=0; for(i=1;i 최대공약수 6 import java.util.Scanner; public class No1658 { static int euclidean(int x,int y) { int r; while(y!=0) ..
알고리즘/백준 등 알고리즘 문제 2023. 2. 18. 20:21
이전 Prev 1 2 Next 다음