본문 바로가기

CS/알고리즘19

병합정렬 병합 정렬 알고리즘 배열의 요솟수가 2개 이상인 경우 배열의 앞부분을 병합 정렬로 정렬합니다 배열의 뒷부분을 병합정렬로 정렬합니다 배열의 앞부분과 뒷부분을 병합합니다 배열 병합의 시간복잡도는 O(n), 병합정렬까지 생각하면 전체 시간복잡도는 O(n log n). + 안정적인 정렬방법이다. 실습 public class MergeSort { static int[] buff; // 작업용 배열 // a[left] ~ a[right] 를 재귀적으로 병합정렬 static void __mergeSort(int[] a, int left, int right){ if(left < right){ int i; int center = (left + right) / 2; int p = 0; int j = 0; int k = l.. 2024. 1. 4.
퀵정렬 퀵정렬은 요솟수가 많은 배열을 정렬하는 경우 효과적이다. O(n log n) ~ O(n²)의 시간복잡도를 가진다. 재귀적인 퀵 정렬 구현 left < pr, pl < right 는 모두 그룹의 요솟수가 1개일때는 성립하지 않는 조건임. 이 조건은 요솟수가 2개 이상인 그룹을 나눌 때 필요하다. import java.util.Scanner; public class QuickSort { static void swap(int[] a, int idx1, int idx2){ int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t; } // 나눌 구간의 맨 앞 요소(left), 맨 뒤 요소(right) static void quickSort(int[] a ,int left, int r.. 2024. 1. 4.
정렬 알고리즘 정렬 알고리즘의 핵심요소 : 교환, 선택, 삽입 1. 버블 정렬 : 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복한다. (단순 교환 정렬) 요소수가 n인 경우 변수 i값을 0부터 n-2까지 1씩 증가시키며 패스를 n-1번 수행한다? (n-1번 패스가 수행되면 마지막 요소는 끝에 놓임) for(int i=0; i 안정적이지 않다.(값이 3인 요소가 두개가 있는 경우 요소의 순서가 바뀔 수 있음) 아직 정렬하지 않은 .. 2024. 1. 2.
java 8퀸 문제 어느 두 개의 퀸 중 하나라도 같은 열, 같은 행, 같은 대각에 놓이지 않도록 8×8 체스판에 8개의 퀸을 놓는 문제. 1. 같은행, 같은 열에 겹치지 않도록 flag를 이용하였음(분기한정법이용) public class QueenB { static boolean[] flag = new boolean[8]; static int[] pos = new int[8]; static void print(){ for (int i = 0; i < 8; i++) System.out.printf("%2d",pos[i]); System.out.println(); } static void set(int i){ for (int j=0; j 2023. 12. 29.
재귀로 푸는 괄호 추가하기 문제 [3, +, 8] [8, *, 7] [7, -, 9] [9, *, 2] 이렇게 문자쪼개기는 되는데 (3+8)+7 로 어떻게 만들까? 에 대해 고민을 많이 했다. -> 이걸 재귀로 이렇게 표현할 수 있다. private static void dfs(int result, int idx){ int result1 = calc(ops.get(idx),result,nums.get(idx+1)); dfs(result1, idx+1); 2023. 11. 16.
윷놀이 문제, Map merge 메소드 윷놀이는 4개의 윷을 이용하는 게임이다. 도 : 1개가 뒤집어진 상태 개 : 2개가 뒤집어진 상태 걸 : 3개가 뒤집어진 상태 윷 : 4개가 뒤집어진 상태 모 : 하나도 뒤집어지지 않은 상태 4개의 윷 상태가 입력되면 도, 개, 걸, 윷, 모를 출력하는 프로그램을 작성하시오. 입력 ① 윷의 4가지 상태가 공백으로 구분되어 입력된다. ② 윷의 상태가 0이면 뒤집어 지지 않은 상태, 1이면 뒤집어진 상태를 의미한다. 출력 윷의 상태를 보고 도, 개, 걸, 윷, 모를 판단하여 출력한다. 여기서 추가되는 형태로 10 회를 굴려서 각각 윷이 나온 상태를 표시하기 ex ) 도 x회 개 x회... 그래서 임의로 지정한 x는 총 몇칸을 전진했는지까지 나의 풀이 /* 0 : 안뒤집힘, 1: 뒤집어진 상태 * 모 : 모두.. 2023. 11. 16.

티스토리툴바