삽입 정렬(Insertion Sort) 삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 위와 같은 배열을 오름차순으로 정렬한다고 하자. 두 번째 원소인 5부터 시작하여 그 앞의 원소들과 비교를 시작한다. 5와 7을 비교해 5가 더 작으므로 7을 한 칸 뒤로 옮기고 그자리에 5를 삽입한다. 세 번째 원소인 1과 그 앞의 원소 7을 비교해 1이 더 작으므로 7을 한 칸 뒤로 민다. 그 앞의 원소 5와 1을 비교해 1이 더작으므로 5를 한 칸 뒤로 밀고 1을 그 자리에 삽입한다. 네 번째 원소인 4와 그 앞의 원소 7을 비교해 4가 더 작으므로 7을 한 칸 뒤로 민다. 그 앞의 원소 5와 4를..
버블 정렬(Bubble Sort) 버블 정렬은 현재 원소와 다음 원소를 비교하여 조건에 맞으면 교환하는 식의 정렬이다. 원소가 거품처럼 올라오는 듯해 버블 정렬이라는 이름이 붙었다. 위와 같은 배열을 오름차순으로 버블 정렬한다고 하자. 처음 7과 5를 비교해 7이 더 크므로 위치를 바꾼다. 이후 배열의 끝까지 비교해서 값이 더 크다면 위치를 바꿔준다. 다시 5와 1을 비교해 5가 더 크므로 위치를 바꿔준다. 이번엔 정렬이 끝난 7 전까지만 해당 과정을 반복 해준다. 다시 1과 4를 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이후 4와 3을 비교했을 때 4가 더크므로 위치를 바꿔준다. 1과 3을 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이렇게 하면 버블 정렬이 완료된다. 버블정렬의 특징 버블 ..
선택정렬(Selection Sort) 선택정렬은 현재 위치에 들어갈 값을 찾아서 바꾸는 알고리즘이다. 오름차순으로 정렬하는 선택정렬은 다음과 같은 과정을 거친다. 1. 현재 정렬되지 않은 가장 맨 앞의 인덱스를 선택한다. 2. 현재 인덱스의 다음 인덱스부터 끝까지 가장 작은 값을 찾으면 현재 인덱스의 값과 바꿔준다. 3. 다음 인덱스에서 위 과정을 반복한다. 과정이 잘 이해가 가지 않는다면, 다음 예시를 보면 이해가 빠를 것이다. 예를 들어 위와 같은 배열을 오름차순으로 선택정렬한다고 하자. 가장 먼저 맨 앞의 7부터 시작한다. 7 뒤의 값들 중 가장 작은 값인 1과 자리를 바꾼다. i는 현재 인덱스, minIdx는 가장 작은 값의 인덱스를 나타낸다. 다음은 5와 그 이후 값들 중 가장 작은 값인 3의 ..
Web 과 HTTP 웹 페이지는 객체(object)로 구성된다. 객체(object)는 HTML 파일, JPEG 이미지, JAVA applet, 오디오 파일 등이 될 수 있다. 웹페이지는 여러 참조된 객체를 포함하는 기본 HTML 파일로 구성되며, 각 개체는 URL로 주소 지정이 가능하다. HTTP HTTP(Hyper Text Transfer Protocol)는 텍스트 기반의 통신 규약으로 인터넷에서 데이터를 주고받을 수 있는 프로토콜이다. TCP/IP 5계층에서 Application Layer(어플리케이션 계층)에 속하는 프로토콜이다. HTTP의 동작 client 측에서 브라우저를 통해 어떠한 서비스를 요청(request)하면 server에서 해당 요청사항에 맞는 결과를 찾아 사용자에게 응답(respon..
계층화(Layering)란? 계층화란 모듈들이 계층(Layer)을 이루도록 역할과 책임을 세분화 하는 것을 말한다. 시스템을 구성하는 모듈들의 상관 관계를 의존성을 이용해 구분한다. 상위 계층의 모듈은 하위 계층에서 제공하는 인터페이스를 이용해 구현되어야 한다. 계층화의 예로 비행기 서비스의 예를 들어보자. 어떤 사람이 출발 항공에서 도착 항공 까지 비행 서비스를 이용하는 것을 계층화(Layering) 한 것을 나타냈다. 매표소 계층, 수화물 계층, 게이트 계층, 활주로 계층, 비행기 계층으로 나누어 각각 계층이 역할과 책임을 세분화하여 맡는다. 이렇게 계층화를 하는 이유가 무엇일까? 계층화의 장점 복잡한 시스템을 파악하기 쉽게 단순화 시킬 수 있다. 시스템의 업데이트와 유지보수를 쉽게 할 수 있다. 한..
백트래킹이란? 백트래킹(Backtracking) 은 해를 찾는 도중 해가 아니어서 막힌다면, 되돌아가서 다시 해를 찾아가는 기법이다. 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더이상 가지 않고 되돌아간다. 이것을 가지치기(Pruning) 이라고 한다. 즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 것이다. 해가 될 가능성이 있다면 유망하다(promising)고 한다. N-Queen 문제 N-Queen 문제는 N X N 크기의 체스판에 N개의 퀸(Queen)을 서로 공격할 수 없도록 배치하는 문제이다. 이 때 퀸은 상하좌우, 대각선 방향으로 체스판의 끝까지 공격을 할 수 있다. 따라서 아래 그림처럼 직선, 대각선 상에는 퀸을 배치 할 수 ..
너비 우선 탐색, BFS 란? BFS는 그래프 탐색 방법 중 하나로 임의의 시작 정점에서부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. BFS는 큐(Queue) 자료구조를 이용해 구현한다. 큐 자료구조에 대해 알고싶다면 다음 포스팅 참고 [자료구조] 큐(Queue)의 개념, 이해 | c언어 큐 연결리스트로 구현, 소스코드 큐(Queue) 란? 큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스 code-lab1.tistory.com BFS..
DFS란? DFS 는 Depth First Search 의 줄임말로 깊이 우선 탐색이라는 뜻이다. DFS는 보통 트리 혹은 그래프 탐색에서 사용되는 알고리즘으로 깊이를 우선하여 목표노드를 찾는 탐색법을 뜻한다. DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이다. DFS 예시 위와 같은 트리 구조가 있다고 하자. 이 때 DFS 는 다음의 과정을 거치게 된다. 가장 먼저 루트노드인 A를 방문하고, 스택에 추가한다. 이후 스택의 top 부분에 있는 A의 인접 노드인 B노드를 방문하고, 스택에 B노드를 추가한다. (C노드를 먼저 방문해도 된다. 순서는 상관 없다) 이후 스택의 top부분에 있는 B의 인접 노드인 D노드를 방문하고, 스택에 D노드를 추가한다. 이후 스택..
해시 테이블(Hash Table)이란? 해시 테이블은 (Key, Value)식으로 데이터를 저장하는 자료구조 중 하나로 key를 통해 평균 O(1)에 value를 검색할 수 있는 자료구조이다. 해시 테이블은 Key 값을 해시함수(Hash Function)를 사용하여 변환한 값을 색인(index)으로 삼는다. 해시 함수(Hash Function)를 사용해 Key 값을 색인(index)으로 변환하는 과정을 해싱(Hashing)이라고 한다. 해시 함수(Hash Fucntion) 해시 함수의 가장 중요한 점은 고유한 인덱스를 만드는 것이다. 만약 중복되는 인덱스가 발생한다면 이는 충돌(Collision)로 이어지게 된다. 따라서 해시 함수를 구현하는 해시 알고리즘을 적절히 구현하는 것이 중요하다. 해시 테이블에..
그래프란? 그래프는 연결되어 있는 원소 사이의 다대다 관계를 표현하는 자료구조이다. 그래프 G는 객체를 나타내는 정점 V(vertex)와 객체를 연결하는 간선 E(edge)의 집합이다. 트리도 그래프의 한 종류이며, 그 중 사이클(cycle)이 허용되지 않는 그래프를 말한다. 그래프의 종류 방향 그래프 vs 무방향 그래프 간선에 방향이 있는 그래프는 방향 그래프(Directed Graph) 라고 하고, 간선에 방향이 없는 그래프를 무방향 그래프(Undirected Graph) 라고 한다. 완전 그래프 완전 그래프(Complete Graph)는 각 정점에서 다른 모든 정점이 연결된, 최대한 많은 간선 수를 가진 그래프를 뜻한다. 정점이 N개인 무방향 그래프에서 최대 간선 수 : N(N-1)/2 개 ( ex..