우리들이 흔히 알고 있는 정렬 알고리즘인 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘은 모두 시간 복잡도 O(N^2)을 가지는 알고리즘이었습니다. 사실 이러한 복잡도를 가지는 알고리즘은 데이터의 갯수가 10만 개만 넘어가도 일반적인 상황에서 사용하기가 매우 어려운 알고리즘입니다. 그렇기 때문에 더욱 빠른 정렬 알고리즘이 사용될 필요가 있습니다. 그 대표적인 빠른 알고리즘이 바로 퀵정렬 알고리즘입니다. 퀵정렬은 대표적인 '분할 정복' 알고리즘으로 평균 속도가 O(N * logN) 입니다. 퀵 정렬은 하나의 큰 문제를 두개의 작은 문제로 분할하는 식으로 빠르게 정렬합니다. 더 쉽게 말하자면 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눕니다. "특정한 값을 기준으로 큰 숫자..

Introduction 알고리즘 (Algorithm) ※ 주어진 일(또는 문제)을 처리하여 원하는 결과(output)를 얻기까지의 과정을 명확하고 단계적으로 서술한 것 예) 조리법 : 음식을 만드는 알고리즘 길안내 : 낯선 도시에서 길을 찾아가기 위한 알고리즘 세탁기조작법 : 세탁기 조작을 위한 알고리즘 악보 : 음악연주를 위한 알고리즘 ※ 알고리즘을 찾는 작업의 효시 현대의 컴퓨터가 개발되기 훨씬 전부터 수학의 한 분야로 시작 ※ 목표 특정 유형의 모든 문제들을 해결할 수 있는 방법을 서술하는 일련의 명령들을 찾는 것 ※ 알고리즘의 예 : 유클리디안 알고리즘(Euclidean algorithm) 그리스 수학자 유클리드가 발견함 ※ 일단 작업을 수행하기 위한 알고리즘을 찾은 다음에는 알고리즘이 기초하고 ..

1. RAM의 특성과 종류 - RAM의 특징 - RAM의 용량과 성능 - RAM의 종류 2. 메모리의 주소 공간 - 물리 주소와 논리 주소 - 물리 주소와 논리 주소의 변환 - 메모리 보호 3. 캐시 메모리 - 저장 장치 계층 구조 - 참조 지역성의 원리

1. 빠른 cpu를 위한 설계 기법 - 코어와 멀티코어 - 스레드와 멀티스레드 - 하드웨어적 스레드, 소프트웨어적 스레드 2. 명령어 병렬처리 기법 - 명령어 파이프라인 3. 메모리 집합구조 - CISC - RISC

1. ALU와 제어장치 - ALU - 클럭 2. 레지스터 - 상대주소지정방식 - 베이스주소지정방식 3. 명령어 사이클과 인터럽트 - 명령어 사이클 - 인터럽트 - 동기 인터럽트 - H/W인터럽트 처리과정(비동기)

1. 소스코드와 명령어 - 고급언어 - 저급언어 2. 명령어의 구조 - 연산코드+오퍼랜드 - 주소 지정 방식 3. C언어 컴파일 과정 - 전처리기 - 컴파일러 - 어셈블러 - 링커

1. 0과 1로 숫자를 표현하는 방법 - 2진법 -16진법 2. 0과1로 문자를 표현하는 방법 - 아스키 코드 - 유니 코드

1. 컴퓨터의 구조를 알아야 하는 이유 - 문제 해결능력 상승 - 성능, 용량, 비용을 고려하며 개발 가능 2. 컴퓨터 구조의 큰 그림 - 컴퓨터가 이해하는 정보 - 컴퓨터의 4가지 핵심부품

플로이드-워샬(Floyd-Warshall) 알고리즘 모든 정점들간의 상호 최단거리(All Pairs Shortest Path)를 구하는 알고리즘이다. 응용 예시로는 Road Atlas, 네비게이션 시스템, 네트웍 커뮤니케이션 등이 있다. 그렇다면 플로이드-워샬이 무엇이고, 왜 쓰이는지 알아보자. 앞서 배운 다익스트라, 벨만-포드 알고리즘은 시작점이 주어지면 하나의 정점에서 다른 모든 정점으로의 최단경로를 구했다면, 플로이드-워샬 알고리즘은 모든 정점으로부터 모든 정점으로의 최단경로를 구하는대 사용된다. 알고리즘 구현 방식도 다르다. 다익스트라 알고리즘은 vertex set에서 가장 작은 노드를 꺼내서 하나씩 더하면서 최소값을 찾아가는 Greedy한 알고리즘을 사용하지만, 플로이드-워샬은 각 노드를 하나씩..

벨만-포드(Bellman-Ford) 알고리즘 벨만포드 알고리즘도 그래프에서 최소비용을 구할 수 있는 알고리즘 중에 하나이다. 벨만포드 알고리즘은 최소비용을 구하는 알고리즘 중에서도, 한 정점에서 다른 모든 정점으로 가는데 걸리는 최소비용을 구하는데 사용하는 알고리즘이다. 이 점은 다익스트라와 동일하다. 그런데 벨만포그와 다익스트라 알고리즘 중에서 언제 무엇을 사용해야 하는 걸까?? 그리고 시간 복잡도에서 말하겠지만, 벨만포드 알고리즘은 일반적으로 다익스트라 알고리즘보다 더 시간이 오래 걸리는 탐색 방법인데 굳이 이 방법을 써야할까 ?? 우선 벨만포드의 특징 부터 살펴보자 먼저 다익스트라와 마찬가지로 시작점이 존재한다. 하지만 벨만포드의 가장 중요한 포인트는 가중치가 0보다 작을 수 있다는 점이다. 음의 ..