Study Note

절차지향 (Procedural Programming) 일련의 처리 절차를 정해진 문법에 따라 순서대로 기술하는 프로그래밍 방법 데이터와 기능(함수)으로 나누어서 기능의 목록을 절차적으로 수행 장점 초기 프로그래밍 언어로, 컴퓨터와 처리구조가 비슷해 실행 속도가 빠르다. 적은 개발 비용 및 시간 단점 유지보수의 어려움 - 디버깅이 어려움 모든 구성 요소가 유기적으로 연결되어 있다는 것은, 하나가 고장 났을 때 시스템 전체가 고장난다는 의미이다. 문제를 해결하기 위해 일부분이 아닌 시스템 전체를 수리해야한다. 엄격하게 순서가 정해져 있어 비효율적 실행 순서가 정해져 있어 코드의 순서가 바뀌면 결과가 달라질 가능성이 높다. 즉, 언어의 융통성이 부족하여 생산 효율이 떨어진다. 과도한 전역변수 사용 모든 함수에..

계수정렬(Counting Sort) 크기를 기준으로 갯수를 세는 알고리즘 갯수를 세는 배열(counting)을 정렬하고자 하는 배열(arr)의 사이즈를 최대값으로 담기도록 설정한다. 배열을 탐색하면서 해당 값을(arr[i]) counting배열에서 인덱스로 하는 갯수를 센다. import java.util.Scanner; public class p07_countingSort { public static void countingSort(int[] arr, int max){ int[] counting = new int[max+1]; // 배열의 사이즈를 최대값이 담기도록 잡는다. for(int i = 0; i < arr.length; i++){ counting[arr[i]]++; } for(int i = 1..

병합 정렬 (Merge Sort) 시간 복잡도 항상 O(NlogN) 정렬하는데 필요한 시간은 two pointer알고리즘을 사용하므로 수행시간은 N이다. 합치는 개수는 2배씩 증가하므로 2^3 = 8 로 3단계가 필요하다. 따라서 단계의 크기는 데이터의 갯수가 N개일 때 logN을 유지하게 된다. 따라서 항상 시간복잡도가 O(NlogN)을 유지한다. import java.util.Scanner; public class p05_mergeSort { public static void mergeSort(int[] arr) { sort(arr, 0, arr.length); } private static void sort(int[] arr, int low, int high) { if (high - low < 2)..

오름차순 import java.util.Scanner; public class quickSort { public static void swap(int[] arr, int p1, int p2){ int tmp = arr[p1]; arr[p1] = arr[p2]; arr[p2] = tmp; } // 분할 public static int partition(int[] arr, int start, int end){ int key = start; int lt = start + 1; int rt = end; while(lt rt) { // 현재 엇갈린 상태이면 키 값과 교체 swap(arr, rt, key); } else { // 엇갈리지 않았다면 lt와 rt의 값 교체 swap(arr, lt, rt); } } re..

이분 탐색 탐색 범위를 두 부분으로 분할 하면서 검색하는 방식 알고리즘 오름차순 정렬 배열 포인터 인덱스 start, end, mid 값 설정 mid와 내가 구하고자 하는 값과 비교 같으면 mid가 답 구할 값이 mid 보다 작으면 start = mid + 1 작으면 end = mid - 1 start > end가 될 때까지 반복 public class binarySearch { public int solution(int n, int m, int[] arr){ Arrays.sort(arr); int start = 0; int end = n -1; int mid = 0; while(start

2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘 public class p03_insertSort { // 오름차순 public static int[] solution(int n, int[] arr){ for(int i = 1; i = 0; j--){// i번째 이전을 순회하면서 삽입 대상을 어디에 삽입할지 선택 if(arr[j] > tmp) arr[j+1] = arr[j]; else break; // arr[j] < tmp 이면 j이전 인덱스의 값들이 tmp보다 작은 ..

거품 정렬 (Bubble Sort) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 끝에서 부터 정렬이 이루어진다. public class p02_bubbleSort { // 오름 차순 public static int[] solution(int n, int[] arr){ for(int i = 0; i arr[j+1]){ int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } return arr; } // 내림 차순 public static int[] solution2(int n, int[] arr){ for(..

스택(Stack) 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조 후입 선출 LIFO (Last In First Out) top으로 정한 곳을 통해서만 접근할 수 있다. 자료는 top이 가리키는 가장 맨 위에 쌓이며, 자료를 삭제할 때도 top을 통해서만 삭제가 가능하다. 삽입 연산: push, 삭제 연산: pop 활용사례 웹 브라우저 방문기록(뒤로 가기) 실행 취소 (undo) 역순 문자열 만들기 후위 표기번 계산 큐(Queue) 먼저 들어오는 것이 먼저 나가는 구조 선입 선출 (First In First Out) 삽입 연산: Enqueue, 삭제 연산: Dequeue 삽입 연산이 이루어지는 곳을 리어(rear), 삭제 연산이 이루어지는 곳을 front라고 부른다. 활용사례 은행 업무 서비스 센터..

투포인터(Two Pointer) 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘 예제 (연속 부분 수열) 어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값(m)을 가지는 경우의 public class p04 { public static int solution(int n , int m, int[] arr){ int answer = 0; int lt = 0; int sum = 0; for(int rt = 0; rt = m) { lt++; sum -= arr[lt]; if(sum == m) answer++; } } return answe..

선택 정렬(Selection Sort) 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 이다. public class p01_selectionSort { // 오름차순 public static int[] solution(int n, int[] arr){ for(int i = 0; i < n-1; i++){ // 1 int idx = i; for(int j = i+1; j < n; j++){ // 2 if(arr[j] < arr[idx]) idx = j; // 3 } // 4 int tmp = arr[i]; arr[i] = arr[idx]; arr[idx] = tmp; } return arr; } // 내림차순 public static int[] solution2(..