알고리즘은 어떻게 증명해야할까?나도 모르겠다..같이 한 번 알아보도록 하자.증명을 위해서는 명제에서 시작된다.명제.명제는 참, 거짓을 판단할 수 있는 문장이나 식을 뜻한다.조건 P와 Q가 있을 때, "P이면 Q이다"가 명제이다. 기호로는 P->Q로 나타낸다. 그런데 이떄, P이면이라는 것은 거짓인 상태이다.예를들어, P가 5시 전이면, Q가 공부를 한다. 라고 가정해보자. if, 5시가 되지 않았으면 P는 참이다. 이때 공부를 하면 Q도 참이므로 P->Q도 참이다.하지만 공부를 하지 않았다면 Q는 거짓이고 P->Q도 거짓이다. 그런데 5시가 지났다고 가정해보자. 그러면 P는 거짓이다. 이때 Q, 공부를 한다면 참인데, P->Q는 뭘까?P 시간🕐Q 공부🏫P->Q 🕐 🏫 참참참참거짓거짓거짓참공부함.거..

병합정렬 알고리즘은 Divide and Conquer 알고리즘의 원칙을 기반으로 합니다.정렬되지 않은 데이터는 divide됩니다. 그리고 비교를 거쳐 정렬되게 됩니다.Divide and ConquerDivide and Conquer은 배열을 반반씩 나누며 하나가 될때까지 divide과정을 거친다.위의 예시에서는 6, 5, 12, 10, 9, 1 이 될때까지 divide를 한다.그리고 Conquer(정복)하는 과정에서 큰 수를 오른쪽으로 보내며 병합한다.왼쪽의 첫 번째 요소를, 오른쪽 배열의 모든요소와 비교하여 더 큰게 없다면 Merge할 배열의 인덱스에 차곡차곡 넣는다.그다음에는 오른쪽 배열의 요소를 왼쪽 배열과 비교하는 식으로 차례차례 반복한다.MergeSort알고리즘MergeSort(A, p, r):..

선택정렬은 각 반복에서 정렬되지 않은, 가장 작은 요소를 선택하고, 해당 요소를 배열의 가장 앞쪽에 위치시켜 차례대로 정렬시키는 알고리즘입니다.선택 정렬 알고리즘1. 첫 번째 요소를 minimum으로 설정합니다.2. 두 번째 요소(12)와 비교합니다.두 번째 요소가 minimum보다 작으면, 두 번째 요소를 minimum으로 선택합니다.이후 세번째 요소와 비교하여 minimum(지금 두번째 요소)보다 세번째 요소가 더 작으면,세번째 요소를 minimum으로 선택합니다.이 process는 마지막까지 반복되어, 한 바퀴가 끝나면 첫 번째 minimum자리에 가장 작은 값이 위치하게 됩니다. 선택된 minimum은 배열의 첫 번째 자리에 위치하게 됩니다. 모든 요소가 올바른 위치에 배치될때까지 1~3단계를 반..

안녕하세요, 알고리즘 공부하는 컴공 3학년입니다..ㅎ개강을 시작함과 동시에 이번에 알고리즘 과목을 수강하는데, 수업 전에 미리 공부한 다음 이해한 내용을 토대로 글을 작성해봅니다.알고리즘을 공부하면서 수많은 정렬을 배우게 될거에요, 뭐 버블정렬, 선택정렬, 삽입정렬, 병합정렬, 퀵정렬, 힙정렬 등등(또 있나요?) 이렇게 배우게 될건데.정렬이 뭔지 아시나요?한국인한테 너무 쉬운걸 물어봤죠? 정렬은 알고리즘에 맞게 설명하면, 난잡한... 정리되지 않은 데이터들을 옳바르게 정렬하는거에요. 1, 5, 2, 0, 3.. 이런거 보면 쪼금 불편하지 않나요?우리가 나중에 데이터를 처리하려면 데이터를 가져와야겠죠.. 근데 위처럼 가져오려는 데이터가 지저분~~ 하면 쪼금 거시기 하잖아요? 그래서 정렬 하는겁니다.버블정렬..

삽입 정렬 알고리즘에 대해 정리하겠습니다. 1. 삽입 정렬(Insertion Sort)이란?삽입 정렬은 정렬되지 않은 순차적인(sequence) 데이터를 하나씩 리스트에 정렬하여 삽입하는 알고리즘입니다.정렬된 부분의 맨 끝부터 새로운 데이터를 어디에 넣을지 비교하면서 알맞은 자리를 찾습니다. 처음에는 이해가 어려워 카드 놀이를 예시로 설명하겠습니다. 2. 삽입 정렬 Logic1) 첫 번째 요소(1)은 이미 정렬된 것으로 간주하고, 2번째 부터 정렬을 시작합니다.2) 두 번째 요소부터 마지막 요소까지 반복하면서, 현재 요소 'Key'를 앞의 정렬된 부분과 비교하여 올바른 위치에 삽입합니다.3) 이 과정을 모든 요소가 정렬될 때까지 반복합니다. 3. 삽입 정렬 동작원리 ex)카드놀이여러분은 친구들과 카드게임..

안녕하세요, 여러분! 👋 오늘은 컴공생인 저가,, “알고리즘”에 대해 한 번 짚어보려고 해요.알고리즘, 왜 중요할까요?먼저, 알고리즘이 뭔지부터 알아볼까요?알고리즘은 문제를 해결하기 위한 단계적인 절차를 말해요. 쉽게 말해, 우리가 어떤 문제를 해결하기 위해 따라야 할 ‘레시피’라고 생각하면 돼요.🍰컴퓨터가 빠르고 효율적으로 문제를 해결할 수 있도록 도와주는 이 ‘레시피’가 알고리즘이에요. 알고리즘이 실제로 어떻게 쓰일까?알고리즘은 우리가 매일 사용하는 앱이나 웹사이트에서도 중요한 역할을 해요.이해를 돕기 위해 예를 들자면, 구글 검색이나 유튜브 추천 영상들이 신기할 정도로 본인의 관심사에 맞게 떠오르지 않나요?모두 알고리즘 덕분에 우리가 원하는 정보를 빠르게 찾을 수 있는 겁니다. 🔍 또한, 알고..

메모리 관리란 다중 프로그래밍을 위한 다수의 프로세스를 수용하기 위해서 주기억 장치를 동적으로 분할하는 것을 말한다.이를 위해서는 5가지의 요구조건이 있다.1) 재배치 : 프로세스가 스왑되었다가 다시 재배치 될때 주소를 새로 부여한 다음에 위치시킨다.2) 보호 : 다른 프로세스로부터 간섭을 보호한다.3) 공유 : 필수적인 부분만 침해하지 않는다면 융통성있게 접근을 허용한다.4) 논리적 구성 : 모듈단위로 구성한다. 독립적으로 이루어질 수 있도록 -> 뒤에서 설명할 세그먼테이션5) 물리적 구성 : 주기억장치와 보조기억 장치 사이를 스왑하는 것메모리 관리기법메모리 관리 기법에는 1) 연속 메모리 관리와 2) 불연속 메모리 관리가 있다.그리고 연속 메모리 관리에는 1) 고정 분할 기법과 2) 동적 분할 기법이..

교착상태는 데드락이라고도 한다.무엇이냐면, 2개 이상의 프로세스들이 공유자원!! 에 대해서 경쟁하거나 통신, 즉 둘이 동시에 접근하려고 할 때 발생한다.나도 사용하고, 너도 사용하려고 둘다 기다리면서 무한정 대기~~~> 로 이루어짐. 위의 예제의 경우 Pocess P가 A를 가지고 B를 요청하고 있다. Q는 B를 가지고 A를 요청하고 있다.근데 B와 A모두 각각 P와 Q가 이미 가지고 있으므로 둘은 무한정 대기하게 된다. 방출을 위해서는 서로거를 가져와야만 하는데 서로 가지고만 있기 때문에.해결을 위해서는 P가 A를 사용후 먼저 종료를 해줘야만 Q가 사용가능하므로 위의 예시처럼 변경하여 사용이 가능하다. 교착상태의 다른 예제를 살펴보도록 하겠다.총 사용할 수 있는 메모리의 크기는 200이다.근데 P1에서..