전체 글97 [삽입 정렬] & [퀵 정렬] & [병합 정렬] & [기수 정렬] 삽입 정렬이란? 이미 정렬된 데이터 범위에서 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다. 시간복잡도도 O(㎡)로 느린 편이지만 구현하기 쉽다! 선택 데이터는 현재 정렬된 데이터 범위내에서 정확한 위치에 삽입하는 것이 중요하다. 퀵 정렬이란? 기준값(피벗)을 선정해 해당 값보다는 작은 데이터와 큰 데이터로 분류하는 것을 반족해 정렬하는 방식이다. 기준값에 따라 시간 복잡도에 많은 영향을 미치고 평균 시간 복잡도(O(nlogn))이며 최악의 경우에는 시간 복잡도가 O(㎡)! -> 시간복잡도가 불규칙하며 운이 따르는 알고리즘임 ㅜ.ㅜ 따라서 피벗을 설정하는 것이 가장 중요하며 투 포인터(start, end)를 설정하여 피벗과 비교하며 정렬한다. 더보기 오름차순으로 정렬 42 32 24 6.. 2024. 2. 27. [선택 정렬] 백준 1427 선택 정렬이란? 대상 데이터에서 최대나 최솟값을 갖는 데이터를 선택하는 정렬이다. 선택 정렬은 구현 방법이 복잡하고, 시간 복잡도가 O(㎡)으로 효율적이지 않아 많이 사용하지는 않는다. 구현 방법은 최솟값 또는 최댓값을 찾고 남은 정렬에서 가장 앞에 있는 데이터와 swap하는 것을 반복하는 것이다. 예를 들어 최솟값을 기준으로 정렬할 때, 더보기 1 3 2 5 4 -> 1과 5 비교 -> 1이 더 작음 -> 그대로 둠 : 남은 정렬 3 2 5 4 1 3 2 5 4 -> 3과 2비교 -> 2가 더 작음 -> swap : 남은 정렬 3 5 4 1 2 3 5 4 -> 3과 5비교 -> 3이 더 작음 -> 그대로 둠 : 남은 정렬 5 4 1 2 3 5 4 -> 5와 4 비교 -> 4가 더 작음 -> swap 1.. 2024. 2. 27. [버블 정렬] 백준 2750 버블정렬이란? 두 인접한 데이터의 크기를 비교해 정렬하는 방법이다. 간단하게 구현할 수 있지만 시간 복잡도는 O(㎡)으로 다른 정렬 알로그리즘보다 속도가 느린 편이다. 주로 loop를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다. 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 된다. 백준 2750번 문제를 sort를 사용할 수 있지만 n값이 작으므로 직접 정렬을 시도해서 문제를 풀어보겠다. public class 수정렬하기 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(n.. 2024. 2. 27. [슬라이딩 윈도우 실전문제] DNA 비밀번호 - 백준12891 슬라이딩 윈도우는 O(n)의 시간 복잡도를 가져 쉽게 문제를 풀 수 있다. s배열(기본 배열)과 비밀 번호 체크 배열을 설정한다. 윈도우에 포함된 문자로 현재 상태 배열을 만들고 현재 상태 배열과 비밀 번호 체크 배열을 비교한다. 비교 후 답이 되지 않는다면 한 칸 이동해 다시 비교한다. 이때, 빠진 첫 번째 인덱스 값과 들어온 새 인덱스 값만 비교하여 정보를 업데이트 해준다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 슬라이딩_비밀번호 { static int myArr[]; static int ch.. 2024. 2. 26. [투 포인터 실전 문제] 주몽의 명령 -백준 1940 배열의 기본 지식 뿐만 아니라, 수학적인 접근 방법도 필요함. 그 감각을 기르기 위해서 기초 문제부터 깊게 보는 중! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class 주몽의명령 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(.. 2024. 2. 26. [구간 합 실전 문제] 백준 11659 * 첫번째 줄: 개수 N(십만 이하), 합을 구해야 하는 횟수 M(십만 이하) * 두번째 줄: N개의 수 * 세번째 줄: 합을 구해야 하는 구간 * 시간 제한: 0.5초 * * 문제 풀이 방식 * S[n] = S[n-1] + A[n] 이용! public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.ne.. 2024. 2. 26. 이전 1 2 3 4 5 6 7 ··· 17 다음
notcherry
