개발바닥

정렬이란? 정렬은 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다. 정렬은 두가지 분류로 나눌 수 있습니다. 오름차순 정렬(ascending order)과 내림차순 정렬(descending order) 오름차순 정렬은 작은 값이 앞으로 오도록 정렬하는 것이고 내림차순 정렬은 큰 값이 앞으로 오도록 정렬하는 것입니다. 앞으로 다루고자 하는 정렬은 버블 정렬 , 삽입 정렬, 셸 정렬 ,퀵 정렬, 병합 정렬, 힙 정렬, 도수 정렬 총 7가지 정렬을 나누어서 다루겠습니다. 버블 정렬(bubble sort)이란? 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복합니다. 버블 정렬은 2중 반복문으로 간단하게 구현할 수 있습니다, 오름차순으로 정렬시 아래 그림과 같이 동작한다..

8퀸 문제란? 재귀 알고리즘에 대해서 설명할 때 자주 언급되는 알고리즘 문제이다. 8*8 체스판에 8개의 퀸을 배치하되 서로 공격하지 않게 배치해야된다. 퀸을 배치할 때 세가지 조건을 확인해야 됩니다. 1. 퀸을 배치하고자 하는 위치에서 같은 행에 퀸이 있는지 체크 ㅡ 2. 퀸을 배치하고자 하는 위치에서 오른쪽 대각선 방향으로 퀸이 있는지 체크 ( i행 + j열 ) / 3. 퀸을 배치하고자 하는 위치에서 왼쪽 대각선 방향으로 퀸이 있는지 체크 (j 열 + i행 -7 ) ＼ 각 행에 퀸이 있는지 체크는 크기가 8인 배열 변수로 체크를 한다. 오른쪽 대각선 방향에 퀸이 있는지 체크는 크기가 15인 배열 변수로 체크를 한다. 왼쪽 대각선 방향에 퀸이 있는지 체크는 크기가 15인 배열 변수로 체크를 한다. 오른..

하노이의 탑이란? 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제입니다. 모든 원반의 크기는 다르며, 처음에는 모든 원반은 첫번째 기둥에 쌓여져 있습니다. 모든 원반을 세번째 기둥으로 옮기면 되는 문제로 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없습니다. 기둥 번호를 1,2,3번으로 나타낼때 기둥 번호의 합이 6이므로 시작 기둥, 목표 기둥이 어느 기둥이더라도 중간 기둥은 6-x-y로 구할 수 있습니다. 아래와 같은 과정을 재귀로 구현하면 됩니다. 1. 바닥 원반을 제외한 원반 그룹을 시작 기둥에서 중간 기둥으로 옮깁니다. 2. 바닥 원반 숫자를 시작 기둥에서 목표 기둥으로 옮겼음을 출력합니다. 3. 바닥 원반을 제외한 원반 그룹을..

큐(Queue)란? 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조이다. 큐는 선입선출(FIFO)구조로 먼저 들어 온것이 먼저 나가는 방식이다. 큐에 데이터를 넣는 작업을 인큐(enqueue)라 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다. 데이터를 꺼내는 쪽을 프런트(front)라 하고, 데이터를 넣는 쪽을 리어(rear)라고 한다. 아래 그림에서 보듯이 스택이 엎어져있다고 생각하시면 됩니다. 자바로 원형 큐 구현 소스 https://github.com/jokerKwu/java/blob/master/JavaStructure/src/Queue.java

스택(Stack) 이란? 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로 , 데이터의 입력과 출력 순서는 후입선출(LIFO) 이다. 즉, 먼저 들어온 것이 나중에 나가고 늦게 들어온 것이 먼저 나가는 방식이다. 스택에 데이터를 넣는 방식은 푸시(push)라 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다. 스택에 푸시와 팝을 하는 위치를 top이라고 하고 가장 아랫부분을 bottom이라고 한다. 스택에 데이터를 push하고 pop하는 모습은 아래 그림과 같습니다. 자바로 스택을 구현한 소스 코드 입니다. https://github.com/jokerKwu/java/blob/master/JavaStructure/src/Stack.java

선형 검색 : 무작위로 늘어놓은 데이터 모임에서 검색을 수행이진 검색 : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행 해시법 : 추가,삭제가 자주 일어나는 데이터 몽미에서 아주 빠른 검색을 수행 선형 검색은 가장 단순한 검색 방법으로 원하는 값이 나올 때까지 처음부터 끝까지 순차적으로 탐색하는 방법이므로 생략하겠습니다. 이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘입니다. 자바에서는 기본자료형 배열에서 이진 검색을 하는 메서드를 표준 라이브러리로 제공합니다. 표준 라이브러리를 사용하기 위해서는 java.util.Arrays 클래스를 import로 추가해주셔야됩니다. 표준 라이브러리 이진 검색 사용 방법 import java.util.Array; int..

정수값을 임의의 기수로 변환하는 알고리즘을 구현해보겠습니다. 기수란? 수를 나타내느 데 기초가 되는 수로, 10진법에서는 0에서 9까지의 정수를 말합니다. 10진수 0 ... 9까지 10종류의 숫자를 사용하여 수를 나타낸다. 8진수 0 ... 7까지 8종류의 숫자를 사용하여 수를 나타낸다. 16진수 0 ... 9 A...F 총 16 종류의 문자를 사용하여 수를 나타낸다. (10 == A ....15 ==F) 2진수 0 , 1 총 2종류의 문자를 사용하여 수를 나타낸다. 알고리즘 동작 방식 데이터 변수 =1 ... 9 A ... Z 까지 순차적으로 문자들이 저장되어있다. (입력한 정수)%(진수) = 나머지 값 을 데이터 변수 인덱스로 활용해서 출력하고자 하는 변수에 0부터 순차적으로 저장한다 . (나머지 ..

배열 요소를 역순으로 정렬하는 방법 배열 요소 크기가 n사이즈라면 1. 첫 번째 인덱스인 0에 들어있는 값과 마지막 인덱스인 n-1에 들어있는 값을 서로 교환한다. swap(0,n-1) //교환 함수 2. 두 번째 인덱스인 1에 들어있는 값과 n-2에 들어있는 값을 서로 교환한다. swap(1,n-2) ...... 중간 인덱스가 될때까지 반복합니다. 그림을 통해 확인하겠습니다. 예제 소스 코드 결과 화면