삽입(Insertion) 정렬삽입 정렬은 현재 비교하고자 하는 target(타겟)과 그 이전의 원소들과 비교하며 자리를 교환(swap)하는 정렬 방법이다. 삽입 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다. 그리고 이전에 다뤘던 선택 정렬과는 달리 삽입 정렬은 '안정 정렬'이다. 특성설명In-place 알고리즘Memory 상에서 필요 시 상호 위치만 변경될 뿐 추가적인 배열 생성이..

선택(Selection) 정렬선택 정렬은 말 그대로 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다. 좀더 정확하게 말하자면 무작위 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것이다. 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다.그리고 '불안정 정렬'이다.  특성설명In-place 알고리즘Memory 상에서 필..

버블(Bubble) 정렬두 개의 인접한 원소를 비교하여 정렬하는 방식이다. 왜 Bubble 이라는 이름이 붙었는지 찾아보니 정렬 과정에서 원소의 이동이 마치 버블이 수면위로 올라오는 것 같다고 해서 버블(Bubble) 이라는 이름이 붙었다고 한다...  정렬 방식 중 가장 쉬우니 일단 버블 정렬에 대한 특징만 짚고 넘어가보자. 버블 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다. 그..

1. 정렬 알고리즘 개요정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나이다.  숫자가 하나씩 적힌 카드가 10장 있다면, 이 카드를 오름차순으로 정렬해보자. 어떻게 이 카드들을 정렬할 수 있을까?보통 인간이라면 카드를 훑은 후 순식간에 숫자를 0부터 10까지 구성된 걸 확인하고 순차적을 나열할 것이다. 하지만 컴퓨터에게는 쉬운 작업이 아니다. 컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다. 정..

https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 조건 파악 및 접근 문제를 보고 이해하는데 살짝 시간이 걸렸는데 결국 주어진 n의 배수 중에서 1로만 이뤄진 n의 배수를 찾는 문제였다. 우선 2와 5로 나누어 떨어지지 않는다는 조건이 왜 붙었냐면, 소인수분해 시 2와 5가 있을 경우 그 중 작은 수 만큼 수의 낮은 자리수에 0이 생겨서 1로 나누어떨어지지 않게 된다. 즉, 위 조건은 언젠가 1로만 이루어진 n의 배수가 나타나는 것이 보장되었다고 얘기하는 부분이다. 해당 문제는 나머지 연산의 법칙을 ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 조건 파악 및 접근 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 컴퓨터는 100 이하는 갖지만 최대 간선 수는(n*(n-1)) / 2 이므로 4,950개까지 가능. 그래프 문제고 DFS, BFS을 활용하면 된다. 결국 1에 연결된 노드의 개수를 파악하라는게 문제의 최종적인 질문. 풀이 1. BFS 풀이 2. union-find를 활용 union으로 "동일 집합..