짱아의 개발 기록장

힙 정렬은 개인적으로 heap구조를 구현해야하기 때문에 어려운? 알고리즘 중 하나라고 생각한다. 혼자서 짜보려고 노력해봤지만.. 한계를 느껴 다른 분의 해설을 보고 구현해보았다. 나는 주어진 배열을 힙의 형태로 만들어주는 방식으로 정렬을 했다. *핵심 포인트* 1) 주어진 배열을 위->아래 순으로 자식이 부모보다 큰 경우를 처리해준다. 2) 아래->위로 각 배열의 원소들을 루트 노드로 올려 자식들 중 큰 값이랑 교한해주는 힙 구조로 정렬을 해나갔다. *시간 복잡도* Best Avg Worst O(nlog(n)) O(nlog(n)) O(nlog(n)) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ..

처음에는 전혀 감을 잡지 못하고 결국.. 다른 분의 코드를 약간 참고해서 구현했다. dp를 사용하여 "SAMSUNG"을 dp[0]~dp[6]으로 잡아서 1) "S" 일때는 0, 3이니까 dp[0] = dp[0]+1; dp[3] = dp[2]+dp[3] 2) "A"일때는 1이니까 dp[1] = dp[0]+dp[1] ....이런식으로 dp를 이용하면 된다. 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 // 8676. 동현이와 한결이는 아이돌 #include #include #include using namespace std; int t..

간단한 문자열 처리 문제입니다. 앞의 두 글자와 뒤의 두 글자를 나눠서 1) 둘 다 01~12에 해당한다면, "AMBIGUOUS" 2) 앞에만 01~12에 해당한다면, "MMYY" 3) 뒤에만 01~12에 해당한다면, "YYMM" 4) 둘 다 해당되지 않는다면, "NA" 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 // 10059. 유효기간 #include #include using namespace std; int testc..

합병정렬의 핵심은 left, mid, right값을 잡고 분할(divide)+정복(conquer)+합병(combine)해주는 과정이다. 분할(divide)는 merge_sort()함수로 구현해줬고 정복(conquer)는 merge()함수를 통해 구현했습니다. *시간복잡도* Best Avg Worst O(nlog(n)) O(nlog(n)) O(nlog(n)) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 // 합병 정렬 구현(오름차순) #include using..

삽입정렬은 idx기준으로 더 이전의 idx값들과 비교하면서, 기준값들보다 더 큰 값이 있다면 자리를 바꿔주는 형태로 진행된다. 삽입정렬은 최선의 경우에 n번만 비교를 하게 되므로 ex) 1, 2, 3, 4 ,5 -> O(n)의 시간복잡도를 가진다. O(n^2)의 시간복잡도를 가지는 sorting algorithm 중에서는 가장 빠르다. *시간복잡도* Best Avg Worst O(n) O(n^2) O(n^2) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 // 삽입 정렬 구현(오름차순) #include using namespace std; int arr[5] = {8, 5, 6, 2, 4}; void ..

idx값을 기준으로, idx+1부터 배열 끝까지 중 가장 작은 값과 idx값을 비교하여 기준값이 더 크다면 위치를 바꿔주면 된다. 즉, idx값을 저장해놓고 바꾸는 식으로 진행된다. *시간복잡도* Best Avg Worst O(n^2) O(n^2) O(n^2) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 // 선택 정렬 구현(오름차순) #include #include using namespace std; // 초기 배열 상태 int arr[5] = {9, 6, 7, 3, 5}; void selection_sort(int arr[], int size) {..

0~n-1까지 인접한 값들을 비교하면서, 크기가 더 큰 원소를 뒤로 보내주는 연산을 (원소의 개수-1)만큼 반복해주면 된다. 왜? (원소의 개수-1)만큼 반복해주나? 5, 4, 3, 2, 1 처럼 모든 원소의 자리를 바꿔야 하는 경우에는 총 4번을 연산하면 1, 2, 3, 4, 5와 같은 형태로 바꿀 수 있다. 즉, 최악의 경우까지 고려하여 (원소의 개수-1)만큼 반복 연산해주면 오름차순으로 정렬할 수 있다. *시간복잡도* Best Avg Worst O(n^2) O(n^2) O(n^2) 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 // 버블 정렬 구현(오름차순) #include using namespace..

문자열 처리문제이다. 나는 생각보다 쉬운 문제지만, 어떻게 풀지 고민하는 데에 상당히 많은 시간을 할애한 것 같다. 잘못된 방식으로 풀었다가 시간 낭비를 많이 했다. ex) abaa -> 1211 / ccbc -> 1121 / abcd -> 1234 이런식으로, 같은 문자는 같은 번호로 다른 문자라면 +1을 증가시켜주는 형태로 전체 문자열을 숫자로 표현해주었다. 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 // 비슷한 단어 #include #include #includ..