📌 알고리즘
알고리즘
- 문제를 해결하기 위한 일련의 동작들의 모음 또는 과정
검색 알고리즘
- 선형 검색 : 배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사함.
- 이진 검색 : 만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복하면 됩니다.
알고리즘 표기법
- Big O 표기법 : O는 "on the order of"의 약자로, 쉽게 생각하면 "~만큼의 정도로 커지는"것이라고 볼 수 있다. O(n)은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 된다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n)이라고 볼 수 있다.
💡 실행시간의 상한이 낮은 알고리즘이 더 좋을까요, 하한이 낮은 알고리즘이 더 좋을까요?
- 상한이 낮은 알고리즘이 더 좋다. 상한이 낮은 알고리즘일수록 시간적으로 효율적이기 때문에 더 좋은 알고리즘이라고 할 수 있다.
알고리즘의 시간 복잡도
- Big O - 최악의 경우, 알고리즘 실행시간의 상한
- Big Ω - 최선의 경우, 알고리즘 실행시간의 하한
- Big 세타 - O와 오메가가 같은 경우 세타로 표현
정렬 알고리즘
- 선택 정렬(Selection Sort)
- 정렬되지 않은 수 중에 가장 작은 수를 찾아 정렬되지 않은 첫 번째 위치의 수와 교환하는 방식의 정렬
- O(n^2) - 버블 정렬(Bubble Sort)
- 두 개의 인접한 수를 비교하면서 위치를 교환하는 방식의 정렬
- O(n^2) - 병합 정렬(Merge Sort)
- 원소가 한 개가 될 때까지 계속 반으로 나눈 뒤 다시 합쳐 나가며 정렬하는 방법
- O(nlogN) - 삽입 정렬(Insertion Sort)
- 배열의 모든 요소를 앞에서부터 차례로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식의 정렬이다.
- O(n^2) Ω(n)
정렬 알고리즘의 실행 시간
- 실행시간의 상한
- O(n^2): 선택 정렬, 버블 정렬
- O(n log n)
- O(n): 선형 검색
- O(log n): 이진 검색
- O(1) - 실행시간의 하한
- Ω(n^2): 선택 정렬, 버블 정렬
- Ω(n log n)
- Ω(n)
- Ω(log n)
- Ω(1): 선형 검색, 이진 검색
재귀
- 함수가 본인 스스로를 호출해서 사용하는 것
💡반복문을 쓸 수 있는데도 재귀를 사용하는 이유는 무엇일까요?
- 재귀의 장점은 코드를 간결하게 쓸 수 있고 가독성도 높다는 점이다. 하지만 재귀를 쓸때에는 system stack을 활용하게 되어 반복문을 써서 구현한 코드보다 메모리가 비효율적으로 운용된다는 단점이 있다.
병합정렬
- 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식.
💡 병합 정렬을 선택 정렬이나 버블 정렬과 비교했을 때 장점과 단점은 무엇이 있을까요?
- 병합정렬의 빅오 표기법으로 봤을때 다른 정렬 알고리즘 보다 시간이 짧다는 장점이 있지만 배열을 분할하는 과정에서 메모리 사용량이 증가하고 어느 정도 정렬된 상황에서는 효율성이 떨어지는 단점이 존재함.
팀미션 👩🏻💻
- 숫자 애너그램 찾기
- 버블 정렬을 활용한 코드
#include <stdio.h>
void bubbleSort(int num[]); // 함수 미리 정의 해주기
void isAnagram(int original[], int num[]);
int main(void){
// TestCase
// 입력값: 12345, 54321 -> 출력값: True
// 입력값: 14258, 25431 -> 출력값: False
// 입력값: 11132, 21131 -> 출력값: True
int original[5] = {1,1,1,3,2};
int num[5] = {2,1,1,3,1};
// 각각의 배열을 정렬해주기
bubbleSort(original);
bubbleSort(num);
isAnagram(original, num);
}
void bubbleSort(int num[] ){
int temp = 0;
for(int i = 0; i<5; i++){
for(int j = 0; j <5 - i - 1; j++){
if(num[j] > num[j+1]){
temp = num[j];
num[j] = num[j+1];
num[j+1] = temp;
}
}
}
}
void isAnagram(int original[], int num[]){
for(int i =0; i < 5; i++){
if(original[i] != num[i]){
printf("False\n");
return ;
}
}
printf("True\n");
}- 입력값을 비교한 코드
#include <cs50.h>
#include <stdio.h>
int main()
{
int arr1[5];
int arr2[5];
int count = 0;
printf("첫번째 값을 입력하세요\n");
for(int i =0; i<5; i++){
arr1[i] = get_int("%d : ",i+1);
}
printf("\n두번째 값을 입력하세요\n");
for(int i =0; i<5; i++){
arr2[i] = get_int("%d : ",i+1);
}
for(int i = 0; i<5; i++){
count = 0;
for(int j =0; j<5; j++){
if(arr2[j] != -1 && arr1[i] == arr2[j]){
arr2[j] = -1; // -1로 체크 처리
break;
}
count++;
}
if(count == 5){
printf("False\n");
return 1;
}
}
printf("True\n");
return 0;
}- 친구들과 최단거리에 있는 집 구하기
- 평균값이 아닌 중앙값을 이용하여 풀어야되는 문제
#include <stdio.h>
int main(void) {
int a[5] = {3, 2, 6, 4, 2};
int n = 5;
int median, left, right, i, j, temp;
int sum_dist = 0;
left = 0;
right = n-1;
do {
median = a[left];
i = left;
j = right;
while (i<=j) {
while (i <= right && a[i] <= median) i++;
while (j > left && a[j] >= median) j--;
if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
a[left] = a[j];
a[j] = median;
if (j < n/2) {
left = j+1;
} else {
right = j-1;
}
}while (j != n/2);
printf("%d\n", median);
return 1;
}- 최단 시간에 다리 건너기 ( 난이도 상 )
- 방법 1
- 1번과 2번이 건너간다 > 1번이 돌아온다 > n-1번과 n번이 건너간다 > 2번이 돌아온다 >(1번과 2번이 건너간다)
- 총 걸린시간: 2번 + 1번 + n번 + 2번 (+ 2번) - 방법 2
- 1번과 n번이 건너간다 > 1번이 돌아온다 > 1번과 n-1번이 건너간다 > 1번이 돌아온다 > (1번과 2번이 건너간다)
- 총 걸린시간: n번 + 1번 + n-1번 + 1번 (+ 2번)
// !!!! Ellie코치 3조 코드 !!!!
#include <stdio.h>
void array_sort(int *arr, int n){ // 배열 오름차순 정렬
for(int i=0; i<n; i++){
for(int j=0; j<n-i-1; j++){
if(arr[j]>arr[j+1]){
int temp= arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
void method_1(int *arr, int n){ // 첫 번째 방법 총 시간 계산
int total= 0;
for(int i=n-1; i>2; i-=2){
total+= 2*arr[1] + arr[i] + arr[0];
}
if(n%2 == 0){
total+= arr[1];
}
else{
total+= arr[0] + arr[1] + arr[2];
}
printf("%d\n", total);
}
void print_method_1(int *arr, int n){ // 첫 번째 방법 과정 출력
for(int i=n-1; i>2; i-=2){
printf("%d%d\n", arr[0], arr[1]);
printf("%d\n", arr[0]);
printf("%d%d\n", arr[i-1], arr[i]);
printf("%d\n", arr[1]);
}
if(n%2 == 0){
printf("%d%d\n", arr[0], arr[1]);
}
else{
printf("%d%d\n", arr[0], arr[2]);
printf("%d\n", arr[0]);
printf("%d%d\n", arr[0], arr[1]);
}
}
void method_2(int *arr, int n){ // 두 번째 방법 총 시간 계산
int total= 0;
for(int i=n-1; i>1; i--)
{
total+= arr[0] + arr[i];
}
total+= arr[1];
printf("%d\n", total);
}
void print_method_2(int *arr, int n) // 두 번째 방법 과정 출력
{
for(int i=n-1; i>1; i--)
{
printf("%d%d\n", arr[0], arr[i]);
printf("%d\n", arr[0]);
}
printf("%d%d\n", arr[0], arr[1]);
}
int main()
{
int n;
scanf("%d", &n);
int arr[n];
for(int i=0; i<n; i++)
{
scanf("%d", &arr[i]);
}
array_sort(arr, n);
if(arr[1]*2 < arr[0]+arr[n-2])
{
method_1(arr, n);
print_method_1(arr, n);
}
else
{
method_2(arr, n);
print_method_2(arr, n);
}
}- 가장 큰 낙하거리 찾기 ( 난이도 상 )
- 각 열의 최상단에 있는 box로부터 오른쪽에 빈 칸 수를 세어 최대값 저장
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main()
{
int n = get_int("N : ");
int m = get_int("M : ");
int arr[n];
int max = 0;
int count = 0;
for(int i =0; i<n; i++){
arr[i] = get_int("%d : ",i);
}
for(int i =0; i<n; i++){
count = 0;
for(int j = i+1; j<n; j++){
if(arr[i] > arr[j]){
count++;
}
}
if(count > max){
max = count;
}
}
printf("%d\n",max);
return 0;
}회고 ✍🏻
재밌는 문제가 많았던 4주차. 2번문제 그냥 생각없이 평균값아니야??하고 평균값으로 바로 풀어버렸는데 응 아니야 ~ 중앙값이야 ~ 주어진 예제에선 평균값과 중앙값이 같지만 {0,0,0,4}일때 평균값인 1로 계산 시 모든 거리의 합은 6이고 중앙값인 0으로 계산 시 모든 거리의 합이 4이기 때문에 거리의 합이 최소인 중앙값으로 계산해줘야 한다. 3번문제는 제일 어려웠다 .. 힌트 안보고 풀 수 없는 문제 .. ^^ 최소시간을 구할 수 있는 경우가 두가지 이고 상황에 따라 어느 경우를 택해야 되는지 결정해야 되는 문제였다. 그 두가지 경우를 생각해내는 과정이 어려울뿐 구현하기엔 그렇게 어렵지 않은 문제였다. 4번문제는 의외로 쉽게 풀었다. 3번보다 더 쉬웠던것 같기도.. 벌써 4주차!!! 시간 증말로 빠르다 앞으로 남은 2주차도 화이팅 ~
