• pintos에서 알람 기능이 Busy waiting으로 구현되어 있는데, 이 기능을 sleep/wake up을 이용하여 재구현.
• 여기서 Busy waiting이란 Thread가 CPU를 점유하면서 대기하고 있는 상태로, CPU 자원 낭비, 소모 전력이 불필요하게 낭비된다.
• 수정해야 할 파일: thread/thread., devices/timer. 파일들

1. 기본 스레드 순환 구조

2. 주요 코드 정리

<--------- thread 관련 함수 --------->
[pintos/src/threads/thread.c]

static struct list ready_list // Ready 상태의 thread를 관리하는 list, CPU를 기다리는 쓰레드들의 배열

static struct list all_list // 모든 thread를 관리하는 list

void thread_yield(int64_t ticks) // 인터럽트 상태 확인 후, ready_list 가장 마지막에 현재 스레드를 삽입 후 스케줄링(다음 스레드에게 cpu 점유 양보)

<--------- timer 관련 함수 --------->

void timer_sleep(int64_t ticks){
    int64_t start = timer_ticks();

    while(timer_elapsed(start) < ticks) // 인자로 전달된 ticks이후 몇 tick이 지났는지 반환
        thread.yield(); 
}
// 시간이 ticks를 넘어갈 때까지 thread.yield()를 반복

3. 내가 생각한 과제 내용 및 해결 방안

timer_sleep()에서 while문을 보면 스레드가 계속 잠을 자야 되는데 thread_yield()라는 함수가 잠을 자려는 스레드를 ready_list의 맨 뒤로 삽입하게 하는데, 이렇게 되면 ready_list에 들어가게 된 스레드는 잠을 자도 편히 잘 수가 없게 된다. 정해진 ticks동안 아무것도 하지 않도록 잠을 자야 하는데 잠에서 깨지 이전에 ready_list에서 스케줄링 되어 다시 running상태가 될 수 있기 때문에 완벽하게 자는 상태가 아니게 된다. 그래서 과제를 해결하기 위해서 몇 가지 선언해야 할 것들이 있다.

thread.c 위와 같이 잠자는 스레드를 모아놓는 list와 스레드가 일어날 시각을 나타내는 next_tick_to_awake를 선언해서 cpu 점유 제한 시간을 나타내준다.

선언한 next_tick_to_awake를 getter, setter해주는 메소드를 작성함으로써 점유시간을 불러들이거나 저장할 수 있도록 해준다.

그리고 당연히 thread_init에 위에서 선언해 놓은 sleep_list를 초기화해주는 작업을 추가로 작성한다.

원래 있던 thread_yield()와는 전혀 다른 기능을 해야 하기 때문에, 스레드를 재우는 함수와 스레드를 깨우는 함수를 각각 작성해준다. thread_sleep(): 현재 스레드를 받아와서, next_tick_to_awake()로 자는 시간을 저장해주고 새롭게 만든 sleep_list에 받아온 스레드를 삽입한 후, block을 시킨다. thread_awake(): 자고 있는 스레드들 중에 깨어날 시각이 미리 저장되어있던 ticks인 스레드를 깨워준다.

1. start.spring.io 에서 프로젝트 생성

위 사진과 같이 Dependency들을 추가해서 프로젝트를 생성해 줍니다.

로그인 기능은 spring-security를 사용해서 구현할 예정입니다.

spring security란?

-> 스프링 기반 애플리케이션의 보안을 담당하는 프레임워크이며, 직접 보안 관련 코드를 작성하는 수고를 덜 수 있다. -> 제공하는 기능으로는 간단하게 애플리케이션 모든 url에 대해 인증을 요구하며, 로그인 양식을 생성해주고, 아이디 및 암호를 가진 사용자의 양식 기반 인증 기능 등 여러가지 기능을 제공해줍니다. 이외에도 여러 서블릿 API 메소드들과 통합이 가능합니다.

2. MVC 및 설정 파일 작성

여기서 User에는 이메일, 비밀번호, 권한(유저인지 관리자인지) 필드가 필요하고, 파라미터가 없는 생성자를 자동 생성해주는 NoArgsConstructor 어노테이션을 사용합니다.

그리고 유저 엔티티들 뿐만 아니라 이 프로젝트에서 생성되는 모든 엔티티들은 Service를 거쳐 Repository로 가서 저장되도록 코드를 작성해줍니다.

UserService.java

UserRepository.java

그리고 사용할 데이터베이스에 대한 config 파일도 작성합니다.

데이터베이스 config 파일 설정이 완료되었다면, spring security 파일을 생성해서 작성합니다.

spring security의 웹 보안 기능 초기화 및 설정을 담고있는 WebSecurityConfigureAdapter를 상속해주고, 설정 클래스를 알려주는 Configuration 어노테이션과 웹 보안 활성화를 위한 EnableWebSecurity 어노테이션을 추가로 작성합니다. anyRequest().authenticated()는 어떠한 URI로 접근하던지 인증이 필요함을 나타내고 formLogin()은 폼 방식 로그인을 사용할 것임을 알리고, defaultSuccessURI로 로그인 성공 시 이동할 uri를 작성합니다.

spring security 참고 사이트(nahwasa)

원래 같았으면 위 사진과 같이 WebSecurityConfigurerAdapter를 extends로 상속받아서 설정을 오버라이딩 하는 방식으로 코드를 작성했겠지만 현재 스프링 부트에서 WebSecurityConfigurerAdapter를 사용할 수 없게 되었다. 그래서 구글링을 해본 결과, 바뀐 방식에서는 상속받아 오버라이딩 하지 않고, 모두 Bean으로 등록하는 방식으로 코드를 작성해야 합니다.

코드

package com.project.webChat.Security;


import com.project.webChat.Service.UserService;
import lombok.RequiredArgsConstructor;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import org.springframework.security.config.annotation.web.builders.HttpSecurity;
import org.springframework.security.config.annotation.web.configuration.EnableWebSecurity;
import org.springframework.security.crypto.bcrypt.BCryptPasswordEncoder;
import org.springframework.security.crypto.password.PasswordEncoder;
import org.springframework.security.web.SecurityFilterChain;
import org.springframework.security.web.access.AccessDeniedHandler;

import javax.servlet.http.HttpServletResponse;

@Configuration
@EnableWebSecurity
@RequiredArgsConstructor
public class SecurityConfig{

    private final Logger log = LoggerFactory.getLogger(getClass());
    private final UserService userService;

    @Bean
    public PasswordEncoder passwordEncoder() {
        return new BCryptPasswordEncoder();
    }

    @Bean
    public AccessDeniedHandler accessDeniedHandler(){
        log.warn("accessDeniedHandler");
        return (request, response, e) -> {
            response.setStatus(HttpServletResponse.SC_FORBIDDEN);
            response.setContentType("text/plain;charset=UTF-8");
            response.getWriter().write("ACCESS DENIED");
            response.getWriter().flush();
            response.getWriter().close();
        };
    }

    @Bean
    public SecurityFilterChain filterChain(HttpSecurity http) throws Exception {
        http
                .authorizeRequests()
                    .anyRequest().authenticated()
                .and()
                    .formLogin()
                    .defaultSuccessUrl("경로 지정", true)
                    .permitAll()
                .and()
                .logout();

        return http.build();
    }
}

위와 같이, 원래는 configure() 함수 안에 있던 코드들을 @Bean으로 등록한 뒤, SecurityFilterChain으로 리턴 타입을 설정한 뒤 그래도 복사해서 붙여넣고, return http.build()를 합니다.

1. 호출 스택 : 호출 순서대로 쌓이며, 역순으로 실행. 즉 LIFO구조(Last In First Out)

2. 이벤트 구조 : 이벤트 발생 시, 호출할 콜백 함수들을 관리하고, 호출할 순서를 결정

   • 태스크 큐(Task Queue) : 이벤트 발생 후, 호출될 콜백 함수들이 기다리는 공간
   • 백그라운드 : 타이머나 I/O 작업 콜백, 이벤트 리스너들이 대기하는 공간

4 -> main이 먼저 실행되고, 그 다음에 setTimeout이 실행되므로 호출 스택에는 그림과 같이 스택이 쌓이게 된다. 그리고 setTimeout과 main 함수가 실행 완료 후, 호출 스택이 비워지면 이벤트 루프가 태스크 큐의 콜백을 호출 스택으로 올린다. (호출 스택이 비워져야 올림) 5 -> 호출 스택에 함수가 존재하면, 3초가 지난 후에도 run()은 태스크 큐에서 대기할 수 있다. (타이머 오차도 발생) 6 -> run 이 호출 스택에서 실행되고, 완료 후 호출 스택에서 나감, 이벤트 루프는 태스크 큐에 다음 함수가 들어올 때까지 대기한다. 이러한 태스크 큐는 여러 개 존재하며, 이들의 순서는 이벤트 루프가 결정한다.

3. var, let, const 비교

4. 템플릿 문자열 : 기존에는 '+'를 사용해서 문자열을 연결해서 사용했지만, 가독성을 떨어뜨리므로 `(백틱)을 사용이 가능하다.

5. 객체 리터럴 : 훨씬 간결한 문법으로 객체 리터럴 표현이 가능

6. 함수 호이스팅 : 함수 선언을 유효 scope의 최상단으로 올려 함수 선언 전에도 호출 가능. 하지만, 의도치 않은 실수 유발이 가능하다. 여러 줄의 코드와 다른 사람과 함께 코드를 작성할 때, 같은 이름으로 된 함수를 서로 다른 사람이 작성해서 의도치 않은 기능이 작동되어 에러를 발생할 수 있다.

그리고 함수 표현식을 변수나 상수로 할당 가능하다. const, let으로 할당하여 호이스팅 방지

7. 화살표 함수

   • 한 줄짜리 return 구문만 존재하는 함수는 return 생략 가능.
   • 1줄 짜리 함수는 {}를 ()로 변경이나 생략 가능.
   • 매개 변수가 하나면 매개변수의 () 생략 가능.

8. 구조분해 할당

- javascript로 만든 프로그램들을 실행할 수 있게 해준다.
- 런타임 : 특정 언어로 만든 프로그램을 실행할 수 있는 환경
- Chrome의 V8엔진

노드의 내부구조

- V8과 libuv를 포함한다.
- V8엔진 : 오픈소스 JavaScript 엔진, JavaScript 엔진이란 JavaScript 코드를 실행하는
          프로그램 또는 인터프리터
- libuv : 이벤트 기반, 비동기/non-blocking 입출력 모델을 구현한 라이브러리

노드의 특성

1. 이벤트 기반 : 이벤트가 발생할 때, 미리 저장해둔 작업을 수행하는 방식
2. non-blocking IO : 이전 작업이 완료될 때까지 대기하지 않고, 다음 작업을 수행 ex) I/O 작업, 압축, 암호화등 수행하는데 오래 걸리는 작업만
3. 싱글 스레드 : 주어진 일을 동시에 하나 밖에 처리하지 못한다.

-> 블로킹이 발생할 경우, 나머지 작업은 모두 대기하게 되는데 이 방식은 너무 비효율적 -> 그래서 논블로킹 모델을 채택하여 일부 코드를 백그라운드에서 실행하도록 한다. -> 즉 요청을 먼저 받고, 완료될 때 응답하고 I/O 관련 코드가 아닌 경우, 싱글 스레드, 블로킹 모델과 동일하다.

노드의 역할

1. 서버 활용 : 노드는 서버를 구성할 수 있게하는 모듈을 제공
2. 서버 외 활용 : JavaScript 런타임으로 용도가 서버에만 한정되지 않는다. 웹, 모바일, 데스크탑 애플리케이션에도 사용 가능하다. ex) 웹 프레임워크 : React, Angular, Vue, Meteor ex) 모바일 웹 프레임워크 : React Native, Ionic, NativeScript ex) 데스크탑 개발 도구 : Electron

해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하다. 이렇게 연산에 의해 직접 접근이 가능한 구조를 해시 테이블이라고 하고, 해시 테이블을 이용한 탐색을 해싱(Hashing)이라고 한다. 해싱을 일상생활에서 비유하자면 정리정돈과 비슷하다고 할수 있다. 물건을 정리하는 사람은 각 물건마다 고유한 위치가 있고 그 위치에 물건을 정리한다. 또 어떤 물건이 필요하다 싶으면 해당 위치에 찾아가서 물건을 가져온다. 이런 점이 해싱과 비슷하다고 할 수 있다. 해싱은 보통 "사전"이라는 자료 구조를 구현할 때에 가장 좋다. 예로 영어 사전의 경우, 영단어가 키(key)가 되고 단어에 대한 설명이 값이 된다.

해싱은 자료 저장에 배열을 사용한다. 해싱은 다른 요소들에 접근할 필요없이 원하는 항목의 키만을 가지고 배열의 인덱스를 결정하므로 배열이 가장 최적이다.

해쉬 테이블 구조

해시 함수

• 충돌이 적어야 한다.
• 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포 되어야 한다.
• 계산이 빨라야 한다.

1. 제산 함수

나머지 연산자(mod)를 이용하여 키를 테이블의 크기로 나눈 나머지를 주소로 사용. -> 가장 일반적임.

2. 폴딩 함수

키가 해시 테이블의 크기보다 더 큰 정수일 경우에 사용된다. 키를 여러 부분으로 나누어 모두 더한 값을 주소로 사용한다. 키를 나누고 더하는 방법에는 이동 폴딩(shift folding)과 경계 폴딩(boundary folding)이 대표적.

1. 이동 폴딩 : 키를 여러 부분으로 나눈 값들을 더하여 사용

2. 경계 폴딩 : 키의 이웃한 부분을 더하여 주소를 얻는다.

3. 중간 제곱 함수

키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성한다. 비교적 고르게 주소가 분산된다.

4. 비트 추출 방법

테이블의 크기가 2의 제곱일 때 키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용한다. 이 방법은 키의 일부 정보만을 사용하므로 해시 주소의 집중 현상이 일어날 가능성이 높다.

5. 숫자 분석 방법

숫자로 구성된 키에서 각각의 위치에 있는 수의 특징을 미리 알고 있을 때 유용하다. 예를 들어, 1712345가 학생의 학번이라 하면 앞의 17은 입학년도를 의미하므로 가급적 사용하지 않고 나머지 수를 조합하여 해시 주소로 사용하는 것이다.

6. 탐색키가 문자열일 경우 주의할 점

문자열일 경우 해시 주소를 만들 경우 가장 간단한 방법은 아스키 코드값을 주소로 사용하는 것이다. 그러나 'cup'과 'car'는 구별이 불가능하므로 충돌을 막기 위해서는 문자열안의 모든 문자를 골고루 사용하는 것이 가장 좋다. 그러나 이 방법 또한 문자열안의 문자들이 모두 동일한 문자로 이루어져 있을 경우 구분하기 힘들다. 이러한 충돌을 없애기 위해 글자들의 아스키 코드 값에 위치에 기초한 값을 곱하는 것이다.

충돌 대처

1. 선형 조사법(Linear Probing)

특정 버킷에서 충돌이 발생하면, 비어있는 버킷을 찾아 항목을 저장하는 방법이다. 만약 hashtable[i]에서 충돌이 발생했다면 hashtable[i+1]로 가서 비어있는지 보고 비어있으면 항목을 넣고 비어있지 않으면 또 다시 i+2가 되서 빈 상태인지 확인을 반복한다. 이럼에도 아무 곳에도 빈 곳이 없다면 table resizing을 통해 해시 테이블 크기를 늘려서 이미 존재하는 데이터들을 재 정렬하고 기존에 넣을 곳을 찾고 있었던 데이터를 가지고 빈 공간을 계속 찾는 작업을 한다.

코드 ( 대학교수님의 수업 자료 )

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define KEY_SIZE    10    // 탐색키의 최대길이  
#define TABLE_SIZE    13    // 해싱 테이블의 크기=소수 

typedef struct
{
    char key[KEY_SIZE];
    // 다른 필요한 필드들 
} element;

element hash_table[TABLE_SIZE];        // 해싱 테이블 
void init_table(element ht[])
{
    int i;
    for (i = 0; i < TABLE_SIZE; i++) {
        ht[i].key[0] = NULL;
    }
}

// 문자로 된 키를 숫자로 변환
int transform1(char* key)
{
    int number = 0;
    while (*key)
        number = number + *key++;
    return number;
}
// 제산 함수를 사용한 해싱 함수
int hash_function(char* key)
{
    // 키를 자연수로 변환한 다음 테이블의 크기로 나누어 나머지를 반환
    return transform1(key) % TABLE_SIZE;
}
#define empty(item) (strlen(item.key)==0)
#define equal(item1, item2) (!strcmp(item1.key,item2.key))

// 선형 조사법을 이용하여 테이블에 키를 삽입하고, 
// 테이블이 가득 찬 경우는 종료     
void hash_lp_add(element item, element ht[])
{
    int i, hash_value;
    hash_value = i = hash_function(item.key);
    //printf("hash_address=%d\n", i);
    while (!empty(ht[i])) {
        if (equal(item, ht[i])) {
            fprintf(stderr, "탐색키가 중복되었습니다\n");
            exit(1);
        }
        i = (i + 1) % TABLE_SIZE;
        if (i == hash_value) { // 한바퀴 돌고 와서
            fprintf(stderr, "테이블이 가득찼습니다\n");
            exit(1);
        }
    }
    ht[i] = item;
}

// 선형조사법을 이용하여 테이블에 저장된 키를 탐색
void hash_lp_search(element item, element ht[])
{
    int i, hash_value;
    hash_value = i = hash_function(item.key);
    while (!empty(ht[i]))
    {
        if (equal(item, ht[i])) {
            fprintf(stderr, "탐색 %s: 위치 = %d\n", item.key, i);
            return;
        }
        i = (i + 1) % TABLE_SIZE;
        if (i == hash_value) {
            fprintf(stderr, "찾는 값이 테이블에 없음\n");
            return;
        }
    }
    fprintf(stderr, "찾는 값이 테이블에 없음\n");
}
// 해싱 테이블의 내용을 출력
void hash_lp_print(element ht[])
{
    int i;
    printf("\n===============================\n");
    for (i = 0; i < TABLE_SIZE; i++)
        printf("[%d]    %s\n", i, ht[i].key);
    printf("===============================\n\n");
}

// 해싱 테이블을 사용한 예제 
int main(void)
{
    const char* s[7] = { "do", "for", "if", "case", "else", "return", "function" };
    element e;

    for (int i = 0; i < 7; i++) {
        strcpy(e.key, s[i]);
        hash_lp_add(e, hash_table);
        hash_lp_print(hash_table);
    }
    for (int i = 0; i < 7; i++) {
        strcpy(e.key, s[i]);
        hash_lp_search(e, hash_table);
    }
    return 0;
}

2. 체이닝(Chaining)

선형 조사법이 탐색 시간이 많이 걸리는 이유는 충돌 때문에 해시 주소가 다른 키하고도 비교를 해야 하는데에 있다. 체이닝은 이러한 오버플로우를 리스트로 구현함으로써 해결한다. 리스트는 크기를 예측할 수 없으므로 연결리스트로 구현한다. 물론 버킷 내에서 원하는 항목을 찾을 경우 연결 리스트를 순차 탐색한다.

Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리로서 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1이하인 이진 탐색 트리. AVL트리는 트리가 비균형 상태가 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. 따라서 항상 균형트리로 보장되기 때문에 O(logn)시간 안에 끝나게 된다. 또한 삽입과 삭제 연산도 O(logn)시간 안에 할 수 있다. 균형 상태를 알 수 있게 하는 용어로 균형 인수라는 단어를 사용한다. 균형 인수란 (왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이)로 정의된다. 모든 노드의 균형 인수가 ±1이하이면 AVL트리이다. 아래 그림을 보면 이해가 쉽게 된다.

탐색 연산

일반적인 이진 탐색 트리와 동일, O(logn)

삽입 연산

삽입 연산 시에 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있으므로 새로운 노드 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형 인수가 ±2가 된 가장 가까운 조상 노의 서브 트리들에 대하여 다시 균형을 잡아야한다. 균형을 다시 잡는 경우에는 총 4가지의 경우가 있다.

오른쪽으로 shift하고 오른쪽 서브트리를 오른쪽 형제노드에게 붙여준다.

왼쪽으로 shift하고 왼쪽 서브트리를 왼쪽에 형제노드에게 붙여준다.

LR노드를 RR회전(반시계 방향) 후 LR을 LL회전(시계 방향)을 시켜준다.

RL노드를 LL회전(시계 방향) 후 RL을 RR회전(반시계 방향)을 시켜준다.

코드

#include<stdio.h> 
#include<stdlib.h> 

// AVL 트리 노드 정의
typedef struct AVLNode
{
    int key;
    struct AVLNode* left;
    struct AVLNode* right;
} AVLNode;

int Max(int x, int y)
{
    if (x >= y)
        return x;
    else return y;
}
// 트리의 높이를 반환
int getHeight(AVLNode* node)
{
    int height = 0;

    if (node != NULL)
        height = 1 + Max(getHeight(node->left),
            getHeight(node->right));

    return height;
}
// 노드의 균형인수를 반환
int getBalance(AVLNode* node)
{
    if (node == NULL) return 0;

    return getHeight(node->left)
        - getHeight(node->right);
}

// 노드를 동적으로 생성하는 함수
AVLNode* createNode(int key)
{
    AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    return(node);
}

// 오른쪽으로 회전시키는 함수
AVLNode* rotateRight(AVLNode* parent)
{
    AVLNode* child = parent->left;
    parent->left = child->right;
    child->right = parent;

    // 새로운 루트를 반환
    return child;
}

// 왼쪽으로 회전시키는 함수
AVLNode* rotateLeft(AVLNode* parent)
{
    AVLNode* child = parent->right;
    parent->right = child->left;
    child->left = parent;

    // 새로운 루트 반환
    return child;
}

// AVL 트리에 새로운 노드 추가 함수
// 새로운 루트를 반환한다. 
AVLNode* insert(AVLNode* node, int key)
{
    // 이진 탐색 트리의 노드 추가 수행
    if (node == NULL) // node가 비어있을 때
        return(createNode(key));

    if (key < node->key) // insert할 key값이 현재 노드보다 작을 때
        node->left = insert(node->left, key);
    else if (key > node->key)// insert할 key값이 현재 노드보다 클 때
        node->right = insert(node->right, key);
    else    // 동일한 키는 허용되지 않음
        return node;

    // 노드들의 균형인수 재계산
    int balance = getBalance(node);

    // LL 타입 처리
    if (balance > 1 && key < node->left->key)
        return rotateRight(node);

    // RR 타입 처리
    if (balance < -1 && key > node->right->key)
        return rotateLeft(node);

    // LR 타입 처리
    if (balance > 1 && key > node->left->key)
    {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }

    // RL 타입 처리
    if (balance < -1 && key < node->right->key)
    {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }
    return node;
}

// 중위 순회 함수
void inorder(AVLNode* root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("[%d] ,%d ", root->key, getBalance(root));

        inorder(root->right);
    }
}

//전위순회함수
void preorder(AVLNode* root)
{
    if (root != NULL)
    {

        printf("[%d] ,%d ", root->key, getBalance(root));
        preorder(root->left);
        preorder(root->right);
    }

}
int main(void)
{
    AVLNode* root = NULL;

    // 예제 트리 구축
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);
    root = insert(root, 27);
    root = insert(root, 29);

    printf("중위 순회 결과 \n");
    inorder(root);
    printf("\n\n");
    printf("전위 순회 결과 \n");
    preorder(root);



    return 0;
}

여러 개의 자료 중에서 원하는 자료를 찾는 작업. 탐색 중에서 가장 기초적인 방법은 배열을 사용하여 자료를 저장하고 찾는 것. 탐색 기능을 향상하고자 한다면 이진 탐색 트리 보다 진보된 방법으로 자료를 저장하고 탐색해야 한다.

탐색의 단위는 항목이다. 항목은 가장 간단하게 숫자일 수 있고, 복잡하게는 구조체가 될 수도 있다. 항목 안에는 항목들을 구별시켜주는 키(key)가 존재한다. 이를 탐색키라 하고, 탐색이란 탐색키와 데이터로 이루어진 여러 개의 항목 중에서 원하는 탐색키를 가지고 있는 항목을 찾는 것이다.

정렬되지 않은 배열에서의 탐색

순차 탐색

탐색 방법 중 가장 간단하고 직접적인 탐색 방법으로 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법이다.

순차 탐색 코드

int seqSearch(int key,int low, int high){
    int i;

    for(i = low;i <= high ; i++){
        if(list[i] == key)
            return i;
    }
    return -1;
}

개선된 순차 탐색

순차 탐색에서 반복문을 보면 키 값의 비교 연산이 있다. 이 비교 연산을 줄이기 위해 리스트의 끝에 찾고자 하는 키 값을 저장하고 반복문의 탈출 조건을 키 값을 찾을 때까지로 설정하도록 설정한 것이 개선된 순차 탐색이다. 성공할 경우 해당 위치를 가리키고 실패했을 경우 -1을 반환한다.

개선된 순차 탐색 코드

int seqSearch2(int key,int low, int high){
    int i;

    list[high+1] = key;
    for(i = low; list[i] != key ; i++) ;

    if(i == (high + 1)) return -1;
    else return i;
}

결론 : 두개의 탐색방법이 뭐가 다른지는 확실히 모르겠음...

정렬된 배열에서의 탐색

이진 탐색

배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내서 탐색의 범위를 반으로 줄인다. 이 방법을 찾고자 하는 key를 찾을 때까지 반복 수행한다. 이 방법은 배열이 미리 정렬되어 있어야 하므로 데이터를 삽입, 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터들에 대한 탐색에 적합하다.

코드(순환 호출 버전)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define MAX_ELEMENTS 10
int list[MAX_ELEMENTS];
int count;    // 수행횟수

int binSearch(int list[], int n, int searchNum)
{
    int left = 0;
    int right = n - 1;
    int middle;

    count = 0;
    while (left <= right) {        // 아직 숫자들이 남아 있으면
        count++;
        middle = (left + right) / 2;
        if (searchNum == list[middle]) {
            return middle;
        }
        else if (searchNum < list[middle]) {
            right = middle - 1;
        }
        else {
            left = middle + 1;
        }

    }
    return -1;        // 발견되지 않음 
}

int main()
{
    int i;
    int search_number;
    int return_value;

    for (i = 0; i < MAX_ELEMENTS; i++)
        list[i] = i;

    printf("숫자를 입력하시요.\n");
    scanf("%d", &search_number);

    return_value = binSearch(list, MAX_ELEMENTS, search_number); // 이진탐색

    printf("return value=%d\n", return_value);
    printf("문자의 수행횟수=%d\n ", count);

    return 0;
}

정렬된 배열에서의 색인 순차 탐색

인덱스라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법이다. 인덱스 테이블은 자료 리스트에서 일정 간격으로 발췌한 자료를 가지고 있다. 인덱스 테이블에 m개의 항목이 있고, 자료 리스트의 데이터 수가 n이면 각 인덱스 항목은 자료 리스트의 각 n/m번째 데이터를 가지고 있다. 이때 자료 리스트, 인덱스 항목은 모두 정렬되어 있어야 한다.

우선 인덱스 테이블에서 index[i] 〈= key 〈 index[i+1] 을 만족하는 항목을 찾는다. 이 조건을 만족하는 항목으로부터 자료 리스트에서 순차 탐색을 수행한다. 이걸로 탐색 시간을 상당히 줄일 수 있으므로 빠른 시간 안에 원하는 항목을 발견할 수 있게 해주므르 파일 처리, 데이터베이스 등의 응용 분야에서 많이 사용한다.

코드

#include <stdio.h>

#define MAX_SIZE 9
#define INDEX_SIZE 3

int list[MAX_SIZE] = { 3, 9,15, 22, 31, 55, 67, 88, 91 };
int n = MAX_SIZE;
typedef struct {
    int key;
    int index;
} itable;
itable indexList[INDEX_SIZE] = { {3,0}, {22,3}, {67,6} };

int seqSearch(int key, int low, int high)
{
    int i;
    for (i = low; i <= high; i++)
        if (list[i] == key)
            return i;  /* 탐색에 성공하면 키 값의 인덱스 반환 */
    return -1;    /* 탐색에 실패하면 -1 반환 */
}

/* INDEX_SIZE는 인덱스 테이블의 크기,n은 전체 데이터의 수 */
int indexSearch(int key) // key : 31
{
    int i, low, high;
    /* 키 값이 리스트 범위 내의 값이 아니면 탐색 종료 */
    if (key<list[0] || key>list[n - 1])
        return -1;

    /* 인덱스 테이블을 조사하여 해당키의 구간 결정 */
    for (i = 0; i < INDEX_SIZE - 1; i++) {
        if (indexList[i].key <= key &&
            indexList[i + 1].key > key)
            break; // key값과 가장 비슷한 값이 있는 index번호를 찾는다.
    }
    if (i == INDEX_SIZE - 1) {  /* 인덱스테이블의 끝이면 */
        low = indexList[i].index;
        high = n - 1;
    }
    else {
        low = indexList[i].index;
        high = indexList[i + 1].index - 1;
    }
    /* 예상되는 범위만 순차 탐색 */
    return seqSearch(key, low, high);
}

//
void main()
{
    int i;
    i = indexSearch(31);
    if (i >= 0) {
        printf("탐색 성공 i=%d\n", i);
    }
    else {
        printf("탐색 실패\n");
    }

    for (int j = 0;j < 3;j++) {
        printf("%d %d\n", indexList[j].index, indexList[j].key);
    }
}

보간 탐색

사전이나 전화번호부를 탐색하는 방법과 같이 탐색키가 존재할 위치를 예측하여 탐색하는 방법. 예로 사전을 찾을 때 'ㅎ'으로 시작하는 단어는 사전의 뒷부분에서 찾고 'ㄱ'으로 시작하는 단어는 앞부분에서 찾는 것과 같은 원리이다. 보간 탐색은 이진 탐색과 비슷하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색한다.

Ex) (3, 9, 15, 22, 31, 55, 67, 88, 89, 91)로 구성된 리스트에서 탐색 구간이 0 ~ 9 이고, 찾을 키 값을 55라고 해보자.

탐색 위치 = (55 - 3) / (91 - 3) * (9-0) + 0 = 5.31 ≒ 5

코드

#include <stdio.h>

#define MAX_SIZE 1000
int list[MAX_SIZE];

initList()
{
    int i;
    for (i = 0;i < 1000;i++)
        list[i] = 7 * i;
}

int searchInterpolation(int key, int n)
{
    int low, high, j;
    low = 0;
    high = n - 1;
    while ((list[high] >= key) && (key > list[low])) {
        j = ((float)(key - list[low]) / (list[high] - list[low]) *
            (high - low)) + low;
        if (key > list[j]) low = j + 1;
        else if (key < list[j]) high = j - 1;
        else low = j;
    }
    if (list[low] == key) return(low);  //found(r[low])
    else return -1;  // notfound(key)
}

//
void main()
{
    int i = 0;
    initList();
    i = searchInterpolation(49,1000);
    if (i >= 0) {
        printf("탐색 성공 i=%d\n", i);
    }
    else {
        printf("탐색 실패\n");
    }
}

1. 비교연산: 하나의 합병 단계에서 최대 n번의 비교연산이 필요함으로 최대 nlog2n번 필요하다.

2. 이동연산: 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생하므로 하나의 합병 단계에서 2n개가 필요하다. 따라서 log₂n개의 합병 단계가 필요하므로 총 2nlog₂n개의 이동 연산이 필요하다.

결론 : 둘 다 O(nlog₂n)의 복잡도를 가진다.

3. 장점 : 안정적인 정렬 방법, 데이터의 분포에 영향을 덜 받는다. 최악, 평균 ,최선 모두 O(nlog₂n)인 정렬 방법이다.

4. 단점 : 임시 배열이 필요하다는 것, 레코드들의 크기가 큰 경우, 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래

퀵 정렬

분할 정복 기법에 근거하고, 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵정렬하는 분할-정복법을 사용한다. 하지만 합병 정렬과 다르게 비균등하게 분할한다. 먼저 리스트 안에서 한 요소를 피벗(pivot)으로 설정한다. 첫 번째 요소를 피벗으로 설정하고, 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. 결과적으로 왼쪽은 피벗보다 작은, 오른쪽은 피벗보다 큰 요소들로 이루어진다. 이 상태에서 피벗을 제외한 왼쪽, 오른쪽 리스트를 다시 정렬하면 전체 리스트가 정렬된다. 위와 같은 작업이 2개로 나뉘어지는 부분 리스트들이 더 이상 분할이 불가능할 때까지 나뉘어진다.

코드

#include <stdio.h>

#define MAX_SIZE 9
//int n = 9;
int list[MAX_SIZE] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
//int list[MAX_SIZE] = { 9, 9,9,9,9,9,9,9,9};

#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
//
void print(int list[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", list[i]);
    printf("\n");
}
//
int partition(int list[], int left, int right)
{
    int pivot, temp;
    int low, high;

    low = left;
    high = right + 1;
    pivot = list[left];     /* 피벗 설정 */
    do {
        do
            low++;
        /* 왼쪽 리스트에서 피벗보다 큰 레코드 선택 */
        while (low <= right && list[low] < pivot);
        do
            high--;
        /* 오른쪽 리스트에서 피벗보다 작은 레코드 선택 */
        while (high >= left && list[high] > pivot);
        if (low < high) SWAP(list[low], list[high], temp); /* 선택된 두 레코드 교환 */
    } while (low < high);      /* 인덱스 i,j가 엇갈리지 않는 한 반복 */

    SWAP(list[left], list[high], temp); /* 인텍스 j가 가리키는 레코드와 피벗 교환 */
    return high;
}

//
void quickSort(int list[], int left, int right)
{
    if (left < right) {     /* 리스트에 2개 이상의 레코드가 있을 경우 */
        int q = partition(list, left, right);
        //print(list, 9);
        quickSort(list, left, q - 1);         /* 왼쪽 부분리스트를 퀵정렬 */
        quickSort(list, q + 1, right);       /* 오른쪽 부분리스트를 퀵정렬 */
    }
}
//
int main()
{
    print(list, 9);
    quickSort(list, 0, 8);
    print(list, 9);
}

분석

1. 비교연산 : O(nlog₂n) 여기서 레코드의 이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.

2. 최악의 경우 : 리스트가 계속 불균형하게 나누어질 경우, O(n²)이 된다. 이럼에도 불구하고, 평균적인 경우의 시간 복잡도가 O(nlog₂n)으로 나타난다.

3. 장점 : 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는다.

4. 단점 : 정렬되어 있는 리스트에 대해서 오히려 수행시간이 더 많이 걸린다.

물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 의미.

분류

1. 단순하지만 비효율적인 방법 - 삽입 정렬, 선택 정렬, 버블 정렬 등.

2. 복잡하지만 효율적인 방법 - 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬 등.

3. 내부 정렬 : 정렬하기 전에 모든 데이터가 메인 메모리에 올라와 있는 정렬.

4. 외부 정렬: 외부 기억 장치에 대부분의 데이터가 있고 일부만 메모리에 올려놓은 상태에서 정렬.

선택 정렬

왼쪽 리스트와 오른쪽 리스트, 두 개의 리스트가 있다고 가정하고, 왼쪽 리스트에는 정렬이 완료된 숫자들이 들어가게 되며 오른쪽 리스트에는 정렬되지 않은 숫자들이 들어 있다. 초기 상태에서 왼쪽 리스트는 비어 있고 정렬되어야 할 숫자들은 모두 오른쪽 리스트에 들어 있다. 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 되풀이 한다. 오른쪽 리스트가 공백이 될 때까지 반복한다.

코드

#include<stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))

void selectionSort(int list[], int n)
{
    int i, j, least, temp;
    for (i = 0;i < n;i++) {
        least = i;
        for (j = i + 1; j < n;j++)
            if (list[least] > list[j]) least = j;
        SWAP(list[i], list[least], temp);
    }
}



void print(int list[], int n)
{
    int i;
    for (i = 0;i < n;i++)
        printf("%d ", list[i]);
    printf("\n");
}

void main()
{
    int i;
    int a[MAX_SIZE] = { 1,3,4,9,7,6,5,8,2,10 };
    printf("정렬 전: ");
    print(a, 10);
    selectionSort(a, 10);
    printf("정렬 후: ");
    print(a, 10);
    int list[10];
    for (i = 0;i < 10;i++)
        list[i] = rand() % 100;
    printf("정렬 전: ");
    print(list, 10);
    selectionSort(list, 10);
    printf("정렬 후: ");
    print(list, 10);
}

분석

비교횟수: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)

레코드 교환 횟수는 외부 루프의 실행 횟수와 같으며 한번 교환하기 위하여 3번의 이동이 필요하므로 3(n-1)

장점 : 자료 이동 횟수가 미리 결정된다.

단점 : 이동 횟수가 상당히 큰 편이고, 안정성을 만족하지 않는다.

삽입 정렬

정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복.

코드

#include<stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))

void insertionSort(int list[], int n)
{
    int i, j, key;
    for (i = 1;i < n;i++) {
        key = list[i];
        for (j = i - 1;j >= 0 && list[j] > key;j--)
            list[j + 1] = list[j];
        list[j + 1] = key;
    }
}

void print(int list[], int n)
{
    int i;
    for (i = 0;i < n;i++)
        printf("%d ", list[i]);
    printf("\n");
}

void main()
{
    int i;
    int a[6] = { 1,3,4,9,7,6 };
    printf("정렬 전: ");
    print(a, 6);
    insertionSort(a,6);
    printf("정렬 후: ");
    print(a, 6);
    int n = MAX_SIZE;
    int list[MAX_SIZE];
    for (i = 0;i < n;i++) {
        list[i] = rand() % n + 1;
    }
    printf("정렬 전: ");
    print(list, n);
    insertionSort(list, n);
    printf("정렬 후: ");
    print(list, n);
}

분석

비교 횟수: n-1번

총 이동 횟수: 2(n-1)번

시간 복잡도: O(n), 최악일 경우:입력 자료가 역순일 경우 -> O(n^2)

장점: 레코드 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬보다 유리할 수 있고, 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적인다.

단점: 레코드 양이 많고 레코드 크기가 클 경우 적합하지 않다.

버블 정렬

인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이 과정이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 이 과정이 전체가 정렬이 될 때까지 반복을 한다. 정렬이 안된 오른쪽 리스트를 한번 스캔하면 오른쪽 리스트의 오른쪽 끝에 가장 큰 레코드가 위치하게 되고, 오른쪽 리스트는 추가된 레코드를 포함하여 정렬된 상태가 된다.

코드

#include<stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t))

void bubbleSort(int list[], int n)
{
    int i, j, temp;
    for (i = n - 1;i > 0;i--) {
        for (j = 0;j < i;j++)
            if (list[j] > list[j + 1])
                SWAP(list[j], list[j + 1], temp);
    }
}

void print(int list[], int n)
{
    int i;
    for (i = 0;i < n;i++)
        printf("%d ", list[i]);
    printf("\n");
}

void main()
{
    int i;
    int a[6] = { 1,3,4,9,7,6 };
    printf("정렬 전: ");
    print(a, 6);
    bubbleSort(a,6);
    printf("정렬 후: ");
    print(a, 6);

    int n = MAX_SIZE;
    int list[MAX_SIZE];
    for (i = 0;i < n;i++) {
        list[i] = rand() % n + 1;
    }
    printf("정렬 전: ");
    print(list, n);
    bubbleSort(list, n);
    printf("정렬 후: ");
    print(list, n);
}

분석

비교 횟수: 최선, 평균, 최악 -> O(n^2)

이동 횟수: 최악 -> 역순으로 정렬되어 있는 경우 비교연산*3, 최선->이미 정렬되어 있는 경우 => 결국 O(n^6)

단점: 순서에 맞지 않은 요소를 인접한 요소와 교환한다. 일반적으로 자료의 교환 작업이 자료의 이동작업보다 더 복잡하기 때문에 버블 정렬은 그 단순성에도 불구하고 거의 쓰이지 않는다.

쉘 정렬

삽입 정렬과는 다르게 쉘 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 대신에 먼저 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트가 정렬되면 쉘 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이 한다. 위의 과정은 부분 리스트의 개수가 1이 될 때까지 되풀이 된다. 부분 리스트를 구성할 때는 각 k번째 요소를 추출한다. 각 스텝마다 k를 줄여가므로 반복될 때마다 하나의 부분 리스트에 속하는 레코드들의 개수는 증가된다. 마지막 스텝에서는 k가 1이된다.

코드

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10
#define SWAP(x,y,t) ((t) =(x),(x)=(y),(y)=(t))
void inc_insertion_sort(int list[], int first, int last, int gap)
{
    int i, j, key;
    for (i = first + gap;i <= last;i = i + gap) {
        key = list[i];
        for (j = i - gap;j >= first && key < list[j];j = j - gap)
            list[j + gap] = list[j];
        list[j + gap] = key;
    }
}
void shell_sort(int list[], int n)
{
    int i, gap;
    for (gap = n / 2;gap > 0;gap = gap / 2)
    {
        if ((gap % 2) == 0) gap++;
        for (i = 0;i < gap;i++)
            inc_insertion_sort(list, i, n - 1, gap);
    }
}

void printList(int list[], int n)
{
    int i;
    for (i = 0;i < n;i++)
        printf("%d ", list[i]);
    printf("\n");
}
void main()
{
    int i;
    int a[6] = { 1,3,4,9,7,6 };
    printf("정렬 전: ");
    printList(a, 6);
    shell_sort(a, 6);
    printf("정렬 후: ");
    for (i = 0;i < 6;i++)
        printf("%d ", a[i]);
    printf("\n");
    int n = MAX_SIZE;
    int list[MAX_SIZE];
    for (i = 0;i < n;i++)
        list[i] = rand() % n + 1;

    printf("정렬 전: ");
    printList(list, n);
    shell_sort(list, n);
    printf("정렬 후: ");
    printList(list, n);
}

분석

장점1: 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 반면 삽입정렬에서는 한 번에 한 칸씩만 이동한다. 따라서 교환되는 자료들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.

장점2: 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면 쉘 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 빠르게 수행된다.

시간 복잡도: 최악 -> O(n^2), 평균 -> O(n^1.5)

합병 정렬

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 정렬이다. 분할 정복 기법을 기반으로 작은 2개의 문제로 분리하고, 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 기법이다. 분리된 문제가 아직도 해결하기 어렵다면(충분히 작지 않다면) 분할 정복 기법을 연속하여 다시 적용한다.

1. 분할: 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

2. 정복: 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.

3. 결합: 정렬된 부분 배열들을 하나의 배열에 통합한다.

실제로 합병이 이루어지는 시점은 2개의 리스트를 합병하는 단계이다. 그리고 그림상으로는 리스트가 2개로 나뉘어지지만 코드로 살펴보면 구간을 나누는 것 뿐이고, 합병을 하면서 2개 리스트의 각 데이터들을 비교해가면서 작은 데이터를 먼저 골라서 새롭게 생성한 리스트에 순서대로 넣고 그 리스트를 반환하는게 합병에서 이뤄지는 작업이다.

코드

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZES 20
//int sorted[MAX_SIZES];

void merge(int list[], int left, int mid, int right)
{
    int i, j, k, l;
    i = left;  j = mid + 1;  k = left;

    //int *sorted=new int[right+1];
    int* sorted = (int*)malloc(sizeof(int) * (right + 1));

    /* 분할 정렬된 list의 합병 */
    while (i <= mid && j <= right) {
        if (list[i] <= list[j])
            sorted[k++] = list[i++]; 
        else
            sorted[k++] = list[j++];
    }
    if (i > mid)    /* 남아 있는 레코드의 일괄 복사 */
        for (l = j; l <= right; l++)
            sorted[k++] = list[l];
    else    /* 남아 있는 레코드의 일괄 복사 */
        for (l = i; l <= mid; l++)
            sorted[k++] = list[l];
    /* 배열 sorted[]의 리스트를 배열 list[]로 재복사 */
    for (l = left; l <= right; l++)
        list[l] = sorted[l];

    // delete []sorted;
    free(sorted);
}
//
void mergeSort(int list[], int left, int right)
{
    int mid;
    if (left < right) {
        mid = (left + right) / 2;     /* 리스트의 균등 분할 */
        mergeSort(list, left, mid);    /* 부분 리스트 정렬 */
        mergeSort(list, mid + 1, right); /* 부분 리스트 정렬 */
        merge(list, left, mid, right);    /* 합병 */ // 안나눠질때까지 나눈 후 merge함수 실행
    }
}

void main()
{
    int list[10] = { 6,56,3,2,47,4,5,12,23,10 };
    //    int list[MAX_SIZES];

    int    n = 10;
    int i;
    printf("정렬 전: \n");
    for (i = 0;i < n;i++)
        printf("%d ", list[i]);
    printf("\n");

    mergeSort(list, 0, n - 1);

    printf("정렬 후: \n");
    for (i = 0;i < n;i++)
        printf("%d ", list[i]);
    printf("\n");

}

대표적인 예시 : 지하철 노선도, 전기 소자를 그래프로 표현하게 되면 어떻게 연결되어있는지를 표현해야 회로가 제대로 동작하는지 분석할 수 있고, 운영 체제에서는 프로세스와 자원들이 어떻게 연관되는지를 그래프로 분석하여 시스템의 효율이나 교착상태 유무등을 알아낼 수 있다.

그래프로 표현할 수 있는 것들 : 도로, 미로, 선수과목(위상정렬)

그래프의 정의

정점과 간선들의 유한 집합. 정점은 node라고도 불리고, 간선은 link라고 불린다.

용어 정리

정점의 차수 : 정점에 인접한 정점의 수.

진입 차수 : 외부에서 오는 간선의 개수.

진출 차수 : 외부로 향한 간선의 개수.

예시 : 0의 차수->3, 0의 진입 차수->3, 0의 진출 차수->3

무방향 그래프에서 한 정점의 진입차수와 진출차수는 같다.(양방향이므로)

단순 경로 : 0->1->3->2

사이클 : 0->1->3->0

연결 그래프 : 모든 정점쌍에 대하여 항상 경로가 존재하는 그래프

비 연결 그래프 : 그렇지 않은 그래프

완전 그래프 : 모든 정점이 서로 연결되어 있는 그래프

그래프의 탐색

깊이 우선 탐색(Depth First Search)

탐색 순서

코드(행렬)

#include <stdio.h>
#define MAX_VERTICES 50
#define TRUE 1
#define FALSE 0

int visited[MAX_VERTICES];

typedef struct {
    int n;
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
}GraphType;

void graph_init(GraphType* g)
{
    int r, c;
    g->n = 0;
    for (r = 0;r < MAX_VERTICES;r++)
        for (c = 0;c < MAX_VERTICES;c++)
            g->adj_mat[r][c] = 0;
}

void insert_vertex(GraphType* g, int v)
{
    if (((g->n) + 1) > MAX_VERTICES) {
        printf("그래프:정점의 개수 초과");
        return;
    }
    g->n++;
}

void delete_vertex(GraphType* g, int v)
{
    if (v >= g->n || v < 0) {
        printf("error\n");
        return;
    }
    g->n--;
}
//insert edge in undirected graph(무방향 그래프)
void insert_edge(GraphType* g, int start, int end)
{
    if (start >= g->n || end >= g->n) {
        printf("그래프 :정점 번호 오류");
    }

    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}

void delete_edge(GraphType* g, int start, int end)
{
    if (start >= g->n || end >= g->n) {
        printf("그래프 :정점 번호 오류");
    }

    g->adj_mat[start][end] = 0;
    g->adj_mat[end][start] = 0;
}


void print_graph(GraphType* g)
{
    int r, c;
    for (r = 0;r < g->n;r++)
        for (c = 0;c < g->n;c++) {
            if (g->adj_mat[r][c])
                printf("<%d , %d>", r, c);
        }

    printf("\n");
}

void dfs_mat(GraphType* g, int v)
{
    int w;
    visited[v] = TRUE;
    printf("%d ", v);
    for (w = 0;w < g->n;w++)
        if (g->adj_mat[v][w] && !visited[w])
            dfs_mat(g, w);
}

void main()
{
    int i;
    GraphType g;
    graph_init(&g);

    for (i = 0;i < 4;i++)
        insert_vertex(&g, i);
    insert_edge(&g, 0, 1);
    //    insert_edge(&g,1,0);
    insert_edge(&g, 0, 3);
    insert_edge(&g, 1, 2);
    insert_edge(&g, 1, 3);
    insert_edge(&g, 2, 3);
    print_graph(&g);

    //dfs_mat(&g,0);
    printf("\n");
    delete_edge(&g, 0, 1);
    dfs_mat(&g, 0);
    printf("\n");

    print_graph(&g);

}

너비 우선 탐색(Breath First Search)

탐색 순서

코드(행렬)

include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct { // 큐 타입
    element  queue[MAX_QUEUE_SIZE];
    int  front, rear;
} QueueType;

// 오류 함수
void error(char* message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}

// 공백 상태 검출 함수
void queue_init(QueueType* q)
{
    q->front = q->rear = 0;
}

// 공백 상태 검출 함수
int is_empty(QueueType* q)
{
    return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(QueueType* q)
{
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

// 삽입 함수
void enqueue(QueueType* q, element item)
{
    if (is_full(q))
        error("큐가 포화상태입니다");
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType* q)
{
    if (is_empty(q))
        error("큐가 공백상태입니다");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}


#define MAX_VERTICES 50
typedef struct GraphType {
    int n;    // 정점의 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];

// 그래프 초기화 
void graph_init(GraphType* g)
{
    int r, c;
    g->n = 0;
    for (r = 0; r < MAX_VERTICES; r++)
        for (c = 0; c < MAX_VERTICES; c++)
            g->adj_mat[r][c] = 0;
}
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end)
{
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}
void bfs_mat(GraphType* g, int v)
{
    int w;
    QueueType q;

    queue_init(&q);     // 큐 초기화 
    visited[v] = TRUE;          // 정점 v 방문 표시 
    printf("%d  방문 -> ", v);
    enqueue(&q, v);            // 시작 정점을 큐에 저장 
    while (!is_empty(&q)) {
        v = dequeue(&q);        // 큐에 정점 추출 
        for (w = 0; w < g->n; w++)    // 인접 정점 탐색 
            if (g->adj_mat[v][w] && !visited[w]) {
                visited[w] = TRUE;    // 방문 표시
                printf("%d 방문 -> ", w);
                enqueue(&q, w);     // 방문한 정점을 큐에 저장
            }
    }
}

int main(void)
{
    GraphType* g;
    g = (GraphType*)malloc(sizeof(GraphType));
    graph_init(g);
    for (int i = 0; i < 6; i++)
        insert_vertex(g, i);
    insert_edge(g, 0, 2);
    insert_edge(g, 2, 1);
    insert_edge(g, 2, 3);
    insert_edge(g, 0, 4);
    insert_edge(g, 4, 5);
    insert_edge(g, 1, 5);

    printf("너비 우선 탐색\n");
    bfs_mat(g, 0);
    printf("\n");
    free(g);
    return 0;
}

트리는 이 중에서 비선형 자료구조에 속한다. 특히 계층구조가 있는 가족의

가계도, 회사의 조직도, 컴퓨터의 디렉토리 구조 등의 계층적인 구조를 표

현할 때 사용된다.

*트리의 용어들 : *

(1) A는 루트노드.

(2) B는 D와 E의 부모노드.

(3) C는 B의 형제 노드.

(4) D와 E는 B의 자식 노드.

(5) B의 차수는 2. (차수 : 자식 노드의 개수)

(6) 위의 트리의 높이는 3.

(7) 자식 노드가 없는 노드는 단일 노드.

*트리의 종류 : *

1. 일반 트리 : 자식의 개수가 무한대

2. 이진 트리 : 자식의 개수가 최대 2개.

이진 트리

정의 : 공집합이거나 루트와 왼쪽, 오른쪽 서브트리로 구성된 노드들의 유한 집합. 이진트리의 서브트리는 모두 이진트리여야 한다.

n개의 노드를 가진 이진트리는 정확하게 n-1개의 간선을 가진다.

종류

포화 이진 트리 : 각 레벨에 노드가 꽉 차있는 이진트리.

완전 이진 트리 : 높이가 k일 때, 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서 왼쪽부터 오른쪽으로 노드가 순서대로 채워져있는 이진트리.

기타 이진트리 : 이 이외에 이진트리.

설명 : 정수가 아닌 문자열을 데이터로 작성한 단순 연결 리스트

코드 설명

(1) head라는 ListNode포인터를 생성

(2) head를 insertLast,insertFirst라는 함수로 데이터와 함께 보낸다 -> 함수에서 return 값으로 노드를 받는다.

(insertLast함수)

head가 NULL일 때, 동적생성한 노드에 data를 넣고 link가 자기 자신을 가리키게 한다.(원형 연결리스트이기 때문에)

head가 NULL이 아닐 때, head의 마지막에 노드를 이어붙이는 함수 이므로 동적생성한 노드의 link가 head의 link를 가리키게 한다. (여기서 head는 마지막 노드를 가리킨다.)

(insertFirst함수)

head가 NULL일 때, insertLast함수와 같다.

head가 NULL이 아닐 때, insertFirst함수와 같고, head포인터를 마지막에 삽입된 노드를 가리키도록 한다.

(3) head의 모든 노드들을 출력한다.

코드 설명

(1) head라는 노드를 동적으로 생성한다.

(2) 초기화 작업을 해준다.

(3) for문을 돌려서 0,1,2,3,4 head에 삽입한다. 삽입하는 함수에서도 동적으로 새로운 노드를 생성한 후, 생성한 노드에 데이터를 삽입하고 llink는 앞에 노드를, rlink는 앞에 노드가 가리켰던 노드를 가리키게 한다. (맨 앞에 노드를 삽입)

(4) 또다시 for문을 돌려서 삭제를 한다. 삭제하는 함수에서도 head가 NULL이면 return을 시키고, 앞에 노드 부터 삭제한다. -> 삭제 함수에 매개변수로 head와 head 다음 노드를 보내서 head 의rlink가 매개변수로 온 head의 다음노드의 다음노드를 가리키게 하고 매개변수로 온 head의 다음노드의 rlink가 가리키는 노드이 llin가 head의 매개변수로 온 head의 다음노드의 llink를 가리키게 하면 head를 가리키게 되고 결국 매개변수로 온 head의 다음노드를 가리키는 노드는 아무것도 없게 되므로 free를 시켜준다.

설명 : c언어를 활용한 단순 연결 리스트

설명 : c언어를 활용한 원형 덱을 이용해서 작성한 은행 시뮬레이션

설명 : c언어를 활용해 원형 덱을 작성. 첫 번째 for문에서는 front에 데이터를 넣고 front를 앞으로 이동킨다. 두 번째 for문에서는 rear에서 데이터를 빼고 rear뒤로 front쪽으로 점점 이동시킨다.

설명 : c언어를 이용해 원형 큐 작성. 데이터는 최대 4개까지 입력 가능

설명 : c언어를 활용해 작성한 원형 큐를 가지고 fibonacci생성 원하는 수의 인덱스를 입력하면 해당 인덱스의 숫자가 출력된다.

** 설명 : 첫 번째 for문에서 생성한 q에 1부터 10까지 넣고 두 번째 for문에서 선입선출에 따라 1부터 10까지 차례로 데이터를 삭제한다.**