1. 자료구조 기본

1.1 컴퓨터 기본 커리큘럽

1.1.1 기본언어

1.1.2 자료구조

1.1.3 알고리즘

1.2 자료구조란?

데이터를 담는 구조

1.3 기본 자료 구조

1.3.1 변수

• int x=4;

1.3.2 배열

• int[] arr={0,1,2};
• 장점: arr[i]번째 수를 바로 일 수 있음.
• 딘잠: 데이터 넣고 빼기가 힘듬(배열 앞뒤로 다 이동시키고 삽입)

  1.3.3 링크드 리스트

• 앞의 값이 다음 값을 알고있음
• 장점: 데이터 넣고 빼기 용이
• x[i]번째 값 알기 어려움(처음부터 탐색)

2. 기초 자료구조

자료구조가 설계된 목적을 이해해야함

• 스택
• 큐
• 트리
• 그래프

2.1 스택(Stack)

• 선형 자료구조

• LIFO(Last in first out)
• push(), .pop(),
• 스택 오버플로우란 push()할때 할당된 공간이 다 차서 넘치는것
• 스택언더플로우란 공간에 데이터가 하나도 없을때 pop()하는것

2.1.1 스택 구현

• push()
• pop()
• top()
• size()

2.2 큐(Quque)

• FIFO(First in first out)
• push(), .pop(),
• 스택 오버플로우란 push()할때 할당된 공간이 다 차서 넘치는것

• 스택언더플로우란 공간에 데이터가 하나도 없을때 pop()하는것

• 큐의 문제점 : 공간활용이 안좋음 >> 해결 원형큐

2.2.1 원형큐

배열 공간을 원형으로 만들어서 함

2.2.2 큐 활용문제 예시

괄호가 올바른지 판단하기

2.3 트리(Three)

• root
• 노드(정점)
• 간선
• 트리의 재귀적성질

2.3.1 트리순회

• 전위순회 : root-Left-Right
• 중위순회 : Left-Root-Right
• 후위순회 : Left-Right-Root

2.4 우선순의 큐

• 큐에 넣고 우선순위가 높은것 순으로 뽑기
• 배열을 이용한 우선순의 큐는 뽑고 다시채워야 해서 O(n^2)걸림->느림

2.4 힙(Heap)

부모값이 항상 자식보다 작은 이진트리

아래 트리에 4를 추가한다고 하면.

–4추가

4랑 7비교 4랑 7변경

4랑 3비교 유지 > 정렬끝!!

2.4.1 힙의 삽입의 시간복잡도

완전 이진트리의 높이

노드의 개수가 n개일때의 높이 = logn

2^n-1

• 힙 값 삽입의 시간복잡도=> O(logn)
• 힙 값 삭제의 시간복잡도 => O(logn)

1. 로그 개념과 효율성

log2 16=4;
logx y = N;
x^n=y;
nlog n <- n이커질수록 o(n)과 속도 차이가 크다

2. 고급정렬 종류

2.1 합병정렬

정렬할 값을 반으로 나눠 각각 정렬 후 두 정렬을 크기순으로 합침

2.1.1 고급정렬 예제

1) 아래 배열 정렬

2) 반으로 나누기->각 값이 하나씩 있을때까지

3) 각각 크기순으로 배열 합치기

2.1.2 합병정렬 시간복잡도

1) 왼쪽 /오른쪽 합병정렬 T(n/2) +T(n/2) => n
2) 두 배열 합치기 o(n)
3) T(n)=2*T(n/2)+O(n)
이걸 풀면…
T(n)=O(nlogn)

2.1.3 합병정렬 재귀함수 디자인

1) 함수 정의
2) 기저조건 s>=e이면 retrun
3) mearge(arr, s, e)
mearge(arr, s, mid)
mearge(arr, mid+1, e)

2.1.4 합병정렬 구현

1
2

2.2 퀵정렬

임의의 값 하나를 기준으로 기준값보다 큰건 오른쪽 작은건 왼쪽으로 보내기

2.2.1 예시

1) 아래 배열 퀵정렬

2) 배열 제일 앞숫자3 기준 정렬

3-1) 3기준 앞 배열 제일 앞 숫자1로 정렬

3-2) 3기준 뒤 배열 중 가장 앞 숫자 5기준으로 정렬

2.2.2 퀵정렬 시간복잡도

평균적으로는 O(nlogn) 가장 오래 걸리면 O(n^2)

2.2.3 퀵정렬 구현

1
2

2.3 힙정렬

트리구조를 이용한 정렬 나중에 나옴!

1. 재귀함수

자기자신을 부르는 함수

1.2 재귀함수가 의미있는 예제

• 펙토리얼 n! = n(n-1)(n-2)…*1

  1 2 3 4

  int getFactorial(int n){ if(n==1) return 1; else return n*getFactorial(n-1); }

함수 호출 흐름

1. main에서 getFactorial(3) 호출된다고 가정.
2. getFactorial(3)에서
   3*getFactorial(2)리턴
3. getFactorial(2)에서
   2*getFactorial(1) 리턴
4. getFactorial(1)에서 1리턴
5. 123 도출

1.2 두가지 계산반벙

1.2.1 순차적 계산방법

A를 계산, A를 이용해서 B를 계산, B를 이용해서 C를 계산..
n!=n(n-1)…1

1.2.2 귀납적 계산방법

구하려고 하는 값은 f(x) f(x)를 구하기 위해 또 f(x)를 활용함
n!= 5f(4)
n!=54f(3)
…
n! = 5432*f(1)

• n의 m제곱을 귀납적으로 정의
  n^m = nn^(m-1)
  …
  n^m = nnn..n^0

1.3 수납적 귀납법

명제 p(n)이 모든 n에 성립함을 증명.
p(k)가 성립한다고 가정후 p(k+1)이 성립함을 증명.

2 재귀함수 디자인

2.1 3가지 절차

1) 함수의 역할을 명확하게 정의

2) 기저조건에서 함수가 제대로 동작함을 보임

3) 함수가 제대로 동작한다고 가정하고 함수를 완성

2.2 재귀함수 구현

2.2.1 n의 m제곱

1) getPower(n,m)은 n의 m승을 반환하는 함수이다.

ex) getPower(2,4)=16

2) 기저조건 getPower(n,0)=1

3) getPower(n,m)=n * getPower(n, m-1)

2.2.2 이진수 출력하기

1) pringBin(x)는 X를 이진수로 바꿔출력하는 함수

2) 기저조건 printBin(1)=1, printBin(0)=0

3) printBin(x)={ print(x/2); print(x%2);}

2.2.3 펠린드롬인지 판별하기

• 펠린드롬은 좌우 대칭인 값을 말함

  1) isPal(String, start, end)

  2) 기저조건: start==end isPal(String, start, end)=true;

  3) isPal(String, start, end)

  if(String.start==String.end) return isPal(String, start+1, end-1);
  else return false;

1. 정수

1.1 약수

특정 수를 나누어 떨어지게 하는 수

1.1.1 약수 구하기 구현

1.2 소수

약수가 1과 자기자신인 수

1.2.1 소수 구하기 구현

1.2.2 에라토스테네스의 체(소수 구하기) 구현

1.3 소인수 분해

숫자N을 소수의 곱으로 나타냄

1.3.1 구현

1.4 공약수와 공배수

A,B 공약수, A와 B의 공통된 약수
AB 공배수 A와 B의 공통된 배수

1.4.1 최대공약수(GCD), 최소공배수(LCM)

1.4.2 유클리드 호제법

a, b, r(a/b)
b, r(a/b) , r(b, r(a/b))
… a, b, r==0일때, b 가 최대공약수

1.4 파스칼 삼각형

1
2
3
4
5

1
121
1331
3C0, 3C1, 3C2, 3C3
14641

콤비네이션 값 구할때 사용(20C11)

1. 시간복잡도

문제가 얼마나 빠르게 해결되는지 나타냄
대략적으로 몇개의 명령을 수행하는지?

1.1 for문

1
2
3

for(int i=0 ; i<n; i++){
  int a=0;
}

int a=0;명령을 n번 수행 >> 시간복잡도 O(n)

1.2 n*n 이중for문

1
2
3
4
5

for(int i=0 ; i<n; i++){
  for(int j=0 ; j<n; j++){
    int a=0;
  }
}

int a=0;명령을 n*n번 수행 >> 시간복잡도 O(n^2)

1.3 n(n-1)(n-2) …2*1 이중for문

1
2
3
4
5

for(int i=0 ; i<n; i++){
  for(int j=0 ; j<i; j++){
    int a=0;
  }
}

int a=0;명령을 n(n-1)/2번 수행 >> 1/2nn >> 상수는 무시 >> 시간복잡도 O(n^2)

1.4 if절 있는 for문

1
2
3
4
5

for(int i=0 ; i<n; i++){
  if(i==1){
    int a=0;
   }
}

최악의 경우 n번 수행(if절 결과에 따라) > O(N)
최고차항만 체크

2. 입력크기에 따른 수행시간

1. n의 입력 값에 따라 수행시간 다름
2. 컴퓨터 사양에 따라 다름

2.1 O(N) 시간복잡도

• n이 9000만개일때 보통 1초

2.2 O(N^2) 시간복잡도

• n이 10000개일때 보통 1초 > 명령어 실행수 대략 1억에 1

3. 정렬의 시간복잡도

3.1 선택정렬

최소값 1번 찾는데 O(N)번 * N번 > O(n^2)

3.2 삽입정렬

원소 하나 삽입 시 O(N)걸림 * N번 > O(n^2)

3.3 버블 정렬

인접한 원소 비교해서 뒤로 보냄 O(n) 걸림 * n번 > O(n^2)

• 선택, 삽입, 버블 정렬은 시간복잡도가 안 좋은편!!

1.정렬

오름차순, 내림차순

1.1 정렬의 종류

1. 선택정렬
2. 삽입정렬
3. 버블정렬

1.1.1 선택정렬 예시

배열을 순서대로 탐색하면서 최소값을 앞으로 이동시킴

0) 주어진 배열

1) 첫번째 정렬(1과 2 자리변경)

2) 두번째 정렬(배열2부터 최소값찾기/2와 5자리 변경)

3) 세번째 정렬(배열3부터 최소값찾기/3와 6자리 변경)

4) 네번째 정렬(배열4부터 최소값찾기/5와 7자리 변경)

5) 다섯번째 정렬(배열5부터 최소값찾기/6와 7자리 변경)

6) 선택정렬끝!!

1.2.1 삽입정렬

기준 배열과 나머지 배열 비교하여 작은것 것을 앞으로 바꿈

ex)

0) 주어진 배열

1) 첫번째 정렬

(2와 5비교 유지)

(2와 9비교 유지)

(2와 1비교 1과 2위치 변경)

(1과 6비교 유지)

2) 두번째 정렬(배열2부터 최소값찾기/2와 5자리 변경)

(5와 9비교 유지)

(5와 2비교 자리변경)

(2와 6비교 유지)

3) 세번째 정렬(배열3부터 최소값찾기/3와 6자리 변경)

(5와9비교 유지)

(5와 6비교 유지)

4) 네번째 정렬(배열3부터 최소값찾기/3와 6자리 변경)

(9와9비교 변경)

5) 삽입정렬끝!!

1.3.1 버블정렬

인접한 두 원소 비교 해서 큰 수를 뒤로 보냄

ex)

0) 주어진 배열

1) 첫번째 정렬

(3과 2비교 자리 바꿈)

(3과 5비교 유지)

(5와 1비교 자리 변경)

(5와 4비교 변경 > 5자리 확정)

2) 두번째 정렬

(2와 3비교 유지)

(3와 1비교 자리변경)

(3와 4비교 유지 > 4자리 확정)

3) 세번째 정렬

(2와1비교 변경)

(2와 3비교 유지 > 3자리 확정)

4) 네번째 정렬

(1와2비교 유지 > 2자리 확정)

5) 버블정렬끝!!

1. QuickSort(퀵정렬)

1.1 퀵정렬 이란?

1. 배열중에 임의의 한 값을 선택해 그 기준값을 기준으로 작은건 왼쪽, 큰건 오른쪽에 정렬.

문제.2751 [백준] 수 정렬하기 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		quickSort(arr);
		for (int i : arr) {
			System.out.println(i);
		}
	}

	public static void quickSort(int[] arr) {
		sort(arr, 0, arr.length - 1);
	}

	private static void sort(int[] arr, int start, int end) {
		if (start >= end)
			return;

		int mid = partition(arr, start, end);
		sort(arr, start, mid - 1);
		sort(arr, mid, end);
	}

	private static int partition(int[] arr, int start, int end) {
		int pivot = arr[(start + end) / 2];
		while (start <= end) {
			while (arr[start] < pivot)
				start++;
			while (arr[end] > pivot)
				end--;
			if (start <= end) {
				swap(arr, start, end);
				start++;
				end--;
			}
		}
		return start;
	}

	private static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}

• 4,3,2,1,0 배열을 정렬할때 아래 순으로 졍렬된다.

1. 병합정렬(MeargeSort)

1.1 병합 정렬이란?

1. 정렬할때 가장 작은 단위로 나눠서 정렬후(sort) 병합(mearge)하는 것을 말한다.

문제.2751 [백준] 수 정렬하기 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void mergeSort(int[] arr) {
		mergeSort(arr,  0, arr.length - 1);
	}

	public static void mergeSort(int[] arr, int start, int end) {

		int[] tmp = new int[arr.length];
		if (start < end) {
			int mid = (start + end) / 2;
			mergeSort(arr, start, mid);
			mergeSort(arr,  mid + 1, end);
			mearge(arr, start, mid, end);
		}

	}

	private static void mearge(int[] arr, int start, int mid, int end) {
		int[] tmp = new int[arr.length];
		for (int i = start; i <= end; i++) {
			tmp[i] = arr[i];
		}
		int part1 = start;
		int part2 = mid + 1;
		int index = start;
		while (part1 <= mid && part2 <= end) {
			if (tmp[part1] <= tmp[part2]) {
				arr[index] = tmp[part1];
				part1++;
			} else {
				arr[index] = tmp[part2];
				part2++;
			}
			index++;
		}

		for (int i = 0; i <= mid - part1; i++) {
			arr[index + i] = tmp[part1 + i];
		}

	}

	private static void printArray(int[] arr) {
		for (int i : arr) {
			System.out.println(i);
		}
	
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		mergeSort(arr);
		printArray(arr);
	}
}

• 4,3,2,1 배열을 정렬할때 아래 순으로 졍렬된다.