오늘 한 일 

이진탐색트리, 수식트리, 레드블랙트리를 복습했다.

삽입정렬, 퀵정렬을 공부했다. 

마크다운문법을 이리저리 써봤다. 

생각거리

이번주 금요일부터 스터디를 다시 시작한다. 

연구실 사람들이랑 할 생각을 하니까 설렌다. 

벌써 6월이다. 

5월은 슬럼프가 긴 기간이었다. 잘 이겨내서 다행이다. 

[ 6월의 우선순위]

1. 취업준비 스터디 성실하게 참여.

2. 알고리즘 100문제 풀기.

3. 일 하기.

4. 즐거운 운동 주4회. (필라테스, 요가)

5. 매일 아침 명상.

버블정렬

버블 정렬이란?

거품이 보글보글 올라오는 모양처럼 정렬이 일어난다고 해서 버블 정렬이다.

버블 정렬은 '이웃끼리' 교환을 통해 요소를 정렬한다.

한 사이클을 순회할 때 마다 '가장 큰 수'가 자리를 잡게 된다.

예시

5 1 6 4 2 3

제일 왼쪽에 있는 요소 부터 이웃 데이터끼리 비교하여 오름차순으로 정렬한다.

5와 1을 비교한다.

1 5 6 4 2 3

5와 6을 비교한다. 교환이 필요없으므로 넘어간다.

6과 4를 비교한다.

1 5 4 6 2 3

6과 2를 비교한다.

1 5 4 2 6 3

6과 3을 비교한다.

1 5 4 2 3 6

한 사이클이 끝나면, 가장 큰 수가 가장 마지막에 자리를 잡을 수 있다.

보글보글 하면서 가장 큰 수가(6) 마지막에 가 있고.

그 다음 사이클에는 또 보글보글 하면서 그 다음 큰 수(5)가 마지막에 가 있고.

그 다음 사이클에는 보글보글 하면서 그 다음 큰 수(4)가 마지막에 가 있고. ... 를 반복하게 된다.

얼마나 빠를까

데이터를 순회할 때 마다 순회할 데이터의 개수가 1개씩 줄어든다.

데이터 요소가 N개라면, n-1회, n-2회, n-3회 ... 1회.

따라서 n-1 부터 1까지의 합을 구하면 버블 정렬의 비교연산 횟수가 된다.

오래걸리지만 구현은 간단하다는 장점이 있다.

선택정렬의 경우, 한 사이클을 돌면서 교환(Swap)을 딱 1번만 한다. 

교환 할 요소의 인덱스를 기억해 두었다가 내부 for문이 종료되면 교환을 1번 하기 때문이다. 

반면 버블정렬은 가장 큰수를 가장 마지막 자리로 보내는데에 1번 이상이 필요하다.

버블 정렬은 시간 복잡도가 매우 큰 정렬 방식이다. 

버블정렬 코드

#include <stdio.h>

void BubbleSort(int dataset[], int num){ // 배열과 배열길이를 입력받음

    int i = 0, j=0, temp = 0;
    
    for(i=0; i<num-1; i++){ // num-1 만큼 순회  
        
        for(j=0; j<num-(i+1); j++){ // 정렬할 요소가 1개씩 줄어든다 
            
            if(dataset[j] > dataset[j+1]){ // 교환 조건
                temp = dataset[j];
                dataset[j] = dadtaset[j+1];
                dataset[j+1] = temp;
            }
        }
    }
}

int main(){
    
    int dataset[] = {10, 5, 1, 15, 4, 8, 9};
    int num = sizeof(dataset) / sizeof(dataset[0]);
    int i = 0;
    
    BubbleSort(dataset, num);
    
    for(i=0; i<num; i++){
        printf("%d ", dataset[i]);
    }
    
    return 0;
}

문제

N명의 수학성적이 주어지면 그 중 3등을 한 수학성적을 출력하는 프로그램을 작성하세요.

만약 학생의 점수가 100점이 3명, 99점이 2명, 98점이 5명, 97점이 3명 이런식으로 점수가 분포되면 1등은 3명이며, 2등은 2명이며 3등은 5명이 되어 98점이 3등을 한 점수가 됩니다.

입력

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 수학성적 점수가 공백을 사이에 두고 입력됩니다. 수학성적 점수는 100점 만점 기준으로 입력됩니다.

출력

3등을 한 점수를 출력합니다.

입출력 예시

입력
7
80 96 75 82 96 92 100

출력
92

리뷰

선택정렬을 하고 나서, 정렬된 배열을 순회하되, 앞의 수와 뒤의 수가 차이가 나면 rank를 하나씩 증가시켜서 rank가 3이 되는 순간의 숫자를 출력하도록 풀었다.
근데 테스트케이스를 통과하지 못해서 선생님해설을 봤더니 내가 생각한 것과 풀이법은 똑같았다.
내 코드의 어디가 틀린건지 혼자 찾아내고 싶었는데 잘 안됬다.
내코드와 선생님 코드의 차이점을 보니까 나는 3등이 아니라 4등을 출력하고 있었고, 3등을 찾아내는 반복문의 인덱스를 하나 빼먹고 있었다.
마지막까지 꼼꼼하게 확인하는 습관을 들여야겠다.

#include <stdio.h>  
#include  
#include  
using namespace std;

int main(int argc, char\*\* argv) {

    int num=0, arr\[101\], i=0, j=0, idx=0, tmp=0, rank=0, res=0;

    //freopen("input.txt", "rt", stdin);

    scanf("%d", &num);

    // 숫자들 읽기  
    for(i=0; i<num; i++){  
        scanf("%d", &arr\[i\]);  
    }

    for(i=0; i<num-1; i++){ // 선택정렬

        idx = i; // i를 기준으로.  

    	for(j = i+1; j<num; j++){

        	if(arr[j] > arr[idx]) idx = j;  // 작은 값의 '인덱스'를 기억해둔다  
        }
        
        tmp = arr[i];
        arr[i] = arr[idx];
        arr[idx] = tmp;

    }

    for(i=1; i<num; i++){ // 3등 찾기

        if(arr[i-1] > arr[i]){
            rank++;
        }

        if(rank == 2){
            printf("%d", arr[i]);
            break; 
        }
    }

	return 0;  
}

제 8절. ORDER BY 절

1. ORDER BY 정렬

특정 칼럼을 기준으로 정렬하여 출력하는데 사용한다.

ORDER BY 절에 칼럼명 대신 ALIAS나 칼럼 순서를 나타내는 정수도 사용 가능하다.
기본 정렬 방식은 오름차순이다. (ASC)
SQL 문장 가장 마지막에 위치한다.

ORACLE 에서는 NULL 값을 가장 큰 값으로 간주하기 때문에 오름차순으로 정렬한 경우 NULL값이 가장 마지막에 출력된다.

2. SELECT 문장 실행 순서

ORDER BY 가 가장 마지막이다!

데이터가 있는 테이블을 참조한다 (FROM)
조건식으로 대상이 아닌 데이터를 제거한다 (WHERE)
소그룹화 한다 (GROUP BY)
그룹화 할 때 조건을 만족하는 것만 그룹화한다 (HAVING)
조회한다 (SELECT)
정렬한다 (ORDER BY)

이 순서는 옵티마이저가 SQL 문장의 문법, 구문 에러를 점검하는 순서이기도 하다.

ORDER BY 절에는 SELECT 문에 나타나지 않은 문자형 항목이 포함될 수 있다.
왜냐하면 데이터베이스가 데이터를 메모리에 올릴 때 행 단위로 모든 칼럼을 가져오게 되기 때문이다.
그래서 SELECT 절에서 일부의 칼럼만 선택하더라도 ORDER BY 절에서 메모리에 올라와 있는 다른 칼럼의 데이터를 사용할 수 있다.

5. SELECT 칼럼명
1. FROM 테이블명
2. WHERE 조건식
3. GROUP BY 칼럼이나 표현식
4. HAVING 그룹조건식
6. ORDER BY 칼럼이나 표현식 ;

3. TOP N 쿼리

ROWNUM

ORDER BY 절과 WHERE 절의 ROWNUM 조건을 같이 사용하면 순위가 높은 N 개의 행을 추출할 수 있다.
주의할 점은 오라클에서 데이터가 조회된 후 정렬을 한다는 점이다. (SELECT 이후에 ORDER BY 수행 )

사용 예) 게시판에서 페이지에 맞게 일정 개수의 글목록을 가져올 때 사용한다.

TOP

제 7절. GROUP BY, HAVING 절

1. 집계함수 (Aggregate Function)

집계함수는 여러 행들이 모여 단 하나의 결과를 돌려준다.

집계함수의 특징

GROUP BY 절은 행들을 소그룹화 한다.
SELECT 절, HAVING 절, ORDER BY 절에 사용할 수 있다.

집계함수의 종류

SUM, AVG, MIN, MAX ,STDDEV(표준편차), VARIAN(분산)

주의할 점

COUNT(*) : 전체 행 수
COUNT(HEIGHT) : 키의 건수
COUNT 안에 컬럼명을 적으면 NULL 값은 제외한 건수를 출력한다.

2. GROUP BY 절

GROUP BY 절은 데이터를 소그룹화 하여 항목별 통계 정보를 얻을 때 사용한다.

SELECT [DISTINCT] 칼럼명 
FROM 테이블명
[WHERE 조건식]
[GROUP BY 칼럼이나 표현식]
[HAVING 그룹조건식];

GROUP BY 절과 HAVING 절의 특징

• GROUP BY 절을 통해 소그룹별 기준을 정한 후, SELECT 절에 집계 함수를 사용한다.
• 집계 함수는 WHERE 절에 올 수 없다.
  (집계 함수를 사용할 수 있는 GROUP BY 보다 WHERE 절이 먼저 수행되기 때문이다. )
• GROUP BY 절에는 SELECT 절과는 달리 ALIAS 를 사용할 수 없다.
• GROUP BY 절에서 소그룹별로 집계된 데이터 중에서 HAVING 절에 쓰여진 제한 조건을 만족한 것만 출력한다.
• 집계 함수의 통계 정보는 NULL 값을 가진 행을 제외하고 수행한다.
• GROUP BY는 그룹화만 하는 것이지 정렬을 하지 않는다. ORDER BY 절이 데이터 정렬을 해준다.

3. HAVING 절

WHERE 절의 조건에 맞춰 걸러진 행들만 GROUP BY 의 대상이 된다. (그래서 WHERE 절에는 집계함수 사용이 불가하다.)
GROUP BY가 그룹화를 할 때 HAVING 절에서'조건'을 줄 수 있다.

SELECT  POSITION 포지션, ROUND(AVG(HEIGHT), 2) 평균키
FROM PLAYER
GROUP BY POSITION
HAVING AVG(HEIGHT) >= 180;

4개의 포지션 중에 평균키가 180 이 넘는 데이터를 출력한다.

GROUP BY 절과 HAVING 절의 순서를 바꿔도 에러가 없고 결과물도 동일하다. 하지만 GROUP BY 절 뒤에 HAVING 절을 쓰는 것을 권고한다.

가능한 WHERE 절에서 데이터를 많이 필터링 해둬서 GROUP BY의 계산 대상을 줄이는 것이 효율적인 자원 활용 측면에서 바람직하다.

4. CASE 표현을 활용한 월별 데이터 집계

IF-THEN-ELSE-END

IF    SAL > 2000
    THEN REVISED_SALARY = SAL
    ELSE REVIED_SALARY = 2000
END-IF

IF-THEN-ELSE

CASE
    SIMPLE_CASE_EXPRESSION 조건
    ELSE 표현절
END

5. NULL 관련 함수 (중요)

NULL 값의 특징

• 아직 정의 되지 않은 값이다.
• 0 또는 공백과는 다르다. ( 0은 숫자이고, 공백은 문자이다.)
• 연산에 NULL이 포함되면 결과는 NULL이다.

NVL(exp1, exp2) 함수 NVL/ISNULL

• 결과값을 "NULL이 아닌 다른 값"으로 얻고자 할 때 NVL/ISNULL 함수를 쓴다.
• NVL(exp1, exp2)
• exp1 이 NULL이라면 exp2 를 출력한다.
• exp2는 대체값인 것이다.

NULLIF(exp1, exp2)

• 특정 값을 null로 대체하는 경우에 주로 사용한다.
• exp1 과 exp2가 같으면 NULL을 리턴한다. 다르면 exp1을 리턴한다.

COALESCE(exp1, exp2, ...)

• 인수 중에서 NULL이 아닌 최초의 인수를 리턴한다.
• 모든 인수가 NULL이라면 NULL을 리턴한다.
• 인수의 개수가 무한하다.

오늘 한 일 

SQLD 기출문제를 풀었다. 

'SQL 기본' 부분에 대해서 가이드북 보면서 다시 정리했다. 

내일은 '활용'쪽이랑 최적화쪽을 마무리 할 생각이다. 

제 6절. 함수

1. 내장함수 (Built-In function) 개요

함수를 크게 분류하면 벤더에서 제공하는 내장함수와 사용자가 정의하는 함수가 있다.
입력 값이 단일행 값이 입력되는 단일행 함수와 여러 행의 값이 입력되는 다중행 함수가 있다.

함수는 입력되는 값이 많아도 출력되는 값은 1개다.

함수이름 (칼럼이나 표현식 [, 인수1, 인수2, ...])

단일행 함수의 종류

• 문자형 함수
• 숫자형 함수
• 날짜형 함수 : DATE 타입 값을 연산한다.
• 변환형 함수
• NULL 처리 함수

단일행 함수의 특징

• SELECT, WHERE, ORDER BY 절에 사용 가능하다.
• 여러 인자를 입력해도 하나의 결과만 리턴한다.
• 함수의 인자로 함수를 가질 수 있다.

2. 문자형 함수

문자 데이터를 매개 변수로 받아서 문자나 숫자 값의 결과를 돌려준다.

DUAL 테이블

ORACLE의 DUMMY 테이블이다.
사용자 SYS가 소유하며 모든 사용자가 액세스 가능한 테이블이다.
DUMMY라는 문자열 유형의 칼럼에 'X'라는 값이 들어있는 행을 1건 포함한다.
반면 Sybase나 SQL Server에는 SELECT 절만으로도 SQL문장이 수행되므로 더미 테이블이 필요없다.

3. 숫자형 함수

숫자 데이터를 입력받아 처리하고 숫자를 리턴하는 함수다.

4. 날짜형 함수

5. 변환형 함수

• 명시적 데이터 유형 변환 : 데이터 변환형 함수 이용

• 암시적 데이터 유형 변환 : 데이터베이스가 자동으로 데이터유형을 변환하여 계산

• TO_NUMBER(문자열)

• TO_CHAR(숫자 | 날짜 [, FORMAT])

• TO_DATE(문자열 [, FORMAT])