연숲하는 블로그

Quick Sort 분할 정복 알고리즘이라고도 하며, 특정값을 기준으로 한 배열을 두개의 부분 배열로 나누어 정렬하는 알고리즘이다. pivot을 정하고, 나머지 배열의 양쪽끝에서부터 검사를 한다. 배열의 왼쪽에는 pivot보다 작은 값, 배열의 오른쪽에는 pivot보다 큰 값이 놓이도록, 잘못된 위치에 있는 원소들을 교환한다. 한 검사가 끝나면 적어도 pivot은 제 위치를 찾은 것이고, 나눠진 배열들에 또 퀵 정렬을 적용하고 반복하면 정렬이 완료되게 된다. 이 알고리즘은 while문과 재귀함수로 구현할 수 있다. 배열들을 검사하며 교환하는 while문과 나눠진 두 배열에 퀵 정렬을 적용하는 재귀함수로 이루어진다. 퀵 정렬은 최선의 경우와 최악의 경우에 따라 시간 복잡도가 달라지는데 정렬된 배열을 검사할..

Insertion Sort 원소를 하나씩 삽입하는 것처럼 정렬하는 알고리즘이다. 삽입시 정렬된 이전 원소들과 비교하여, 자신이 더 작다면 자리를 교환하고, 이것을 반복한다. 이 알고리즘은 중첩 for문으로 구현할 수 있는데, 삽입 원소를 선정하는 for문과 삽입 원소와 이전 원소들을 비교하는 for문으로 이루어진다. 삽입 정렬은 최선의 경우와 최악의 경우에 따라 시간 복잡도가 달라지는데 정렬된 배열을 검사할 땐 원소를 비교하는 for문을 거치지 않아 O(n)이 되고 역순 배열을 검사할 땐 O(n^2)이 된다. 코드 #include using namespace std; void insertion_sort(int arr[],int n) { for(int i=1;i=0;j--) { if(new_>=arr[j]..

Selection Sort 최솟값을 이용한 방식으로, 배열의 최솟값인 원소를 찾고 배열의 앞과 값을 교환해서 정렬하는 알고리즘이다. 한 번 검사를 완료하면 최솟값이 앞에 놓이게 되고 다음 검사에선 그 부분을 제외하며 검사를 한다. 이 알고리즘도 중첩 for문으로 구현되는데, 검사 범위를 줄이는 for문과 최소값을 찾는 for문으로 이루어진다. 버블 정렬보단 교환의 수가 줄었지만 중첩 for문이기 때문에 시간 복잡도는 O(n^2)이 된다. 코드 #include using namespace std; void select_sort(int arr[],int n) { for(int i=0;i

Bubble Sort 가장 기본적이고 단순한 방식으로, 배열에서 인접 원소 2개를 비교하고, 교환해서 정렬하는 알고리즘이다. 앞부터 끝까지 검사를 완료하면 가장 큰 값이 끝에 놓이게 되고, 다음 검사에선 그 값을 제외하고 검사를 하기때문에 검사를 할 수록 검사 범위가 줄어들게 된다. 이 알고리즘은 중첩 for문으로 구현할 수 있는데, 검사 범위를 줄이는 for문과 시작부터 끝까지 검사하는 for문으로 이루어진다. 따라서 시간 복잡도는 O(n^2)이 된다. 코드 #include using namespace std; void bubble_sort(int arr[],int n) { for(int i=n-1;i>0;i--){ //검사 범위 축소: 0~n-1, 0~n-2, ... for(int j=0;jarr[j..

https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 1.문제 유형 - 브루투포스 알고리즘, 그래프 탐색, 그래프 이론 , 플로이드-워셜 2.문제 파악 2-친구가 가장 많은 사람을 구하는 문제이다. 문제에서 제시한 2-친구의 설명이 모호한데 A와 C가 1-친구가 아니어도, A와 B가 1-친구이고, B와 C가 1-친구라면 A와 C는 2-친구이다. 라고 이해했다. 또한 문제에서 친구 관계를 "NYN"이런식으로 표현하고 있는데 첫번째 줄에 "NNY"라고 나와..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1.문제 유형 -DFS & BFS 2.문제 파악 문제에서 제시하는 밭을 탐색하여 배추 묶음의 개수를 구한다. ( 배추 묶음의 개수 == 배추 흰지렁이 개수) 밭을 탐색한다, 인접한 다른 배추로 이동할 수 있다 등등에서 DFS와 BFS 관련 문제임을 확인할 수 있다. 3.문제 풀이 해당 글에서는 DFS로 풀었다. 특별한 추가 조건이 없기 때문에 배추 밭에 대한 2차원 그래프를 그리고, 배추가 있는 칸을 방문하여..

https://www.acmicpc.net/problem/1251 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 1.문제 유형 문자열, 브르투포스(완전탐색) 단어의 길이가 최대 50이고 시간제한도 2초로 넉넉하기 때문에 완전탐색 방법(모든 경우를 다 확인)을 사용할 수 있다. 2.문제 파악 문자를 세부분으로 나누고, 각각 뒤집고, 합쳤을 때 사전순으로 가장 앞서는 단어를 출력하는 코드를 짜야한다. 주의할 점은 나눠진 부분의 길이가 1이상이어야한다. ex) ABCD를 ABC/D 이렇게 나누면 안된다. 문자열 함..