개발바닥

삽입 정렬 (insertion sort) 란? 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘입니다. 삽입 정렬은 정렬된 부분과 정렬되지 않는 부분으로 나누어서 정렬되지 않는 부분의 첫번째 요소를 정렬된 부분의 알맞은 위치에 삽입한다고 생각하시면 됩니다. 아래 그림을 통해서 확인하겠습니다. 삽입정렬 소스 코드 https://github.com/jokerKwu/java/blob/master/JavaStructure/src/InsertionSort.java

선택 정렬 (selection sort) 란? 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘입니다. 아래 그림과 같이 동작합니다.. 선택 정렬 소스 코드 https://github.com/jokerKwu/java/blob/master/JavaStructure/src/SelectionSort.java

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

문제 https://www.acmicpc.net/problem/1485 실패한 이유 이렇게 많이 실패한 문제는 오랜만인거 같다... (결국엔 문제를 해결을 못해서 Crocus님 코드를 참조해서 풀었습니다.) 정사각형을 구하기 위해서 여러가지 방법을 생각을 해봤다. 1. 네 각이 90도 일경우 정사각형이므로 각도를 구해서 풀려고 했으나 마름모일 경우 수식을 어떻게 변경해야될지 몰라서 틀렸습니다. 2. 두 벡터를 구해서 내적을 해서 0이 나오면 90도 이므로 모든 점들에 2개에 벡터를 구해서 내적을 해서 0이 나오면 정사각형으로 판단하고 제출했지만... 계속 틀려서 결국 Crocus님 문제 해결 방법을 참조하였습니다. 문제 해결 방법 각 4변의 길이가 모두 같고 두 대각선에 길이가 같다면 정사각형으로 판단해..

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