목록전체 글 (402)
happy coding
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/FpkNC/btrR79RFwVm/qgqcVo8XZPZLMZLhL15FkK/img.png)
수업을 듣고 정리한 내용입니다. 선택 정렬(Selective sort) 입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음엔 0번 원소를 제외한 나머지 원소에서 최솟값을 선ㅌ개하여, 배열 1번 원소와 자리를 바꾸는 방식을 통해 마지막에 2개의 원소 중 작은 것을 선택해 자리를 바꾼다. 이렇게 최솟값을 선택해 정렬하는 것을 선택 정렬이라고 한다. //selective sort 입력 : 크기가 n인 배열 출력 : 정렬된 배열 A for i=0 to n-2 min = i for j=i+1 to n-1//A[i] ~ A[n-1]에서 최솟값을 가짐 if A[j] < A[min] min = j A[i] A[min]//min이 최솟값이 있는 원소의 인덱스임 return A 시간복잡도 코드의..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/4vgT3/btrR8uuaKOf/ukXNPVGuYvZE7cFPYp1k20/img.png)
버블 정렬(Bubble Sort) 버블 정렬은 이웃하는 숫자를 비교해 작은 수를 앞쪽으로 이동시키는 과정을 반복해 진행하는 정렬이다. 이 모습이 마치 버블과 같아 그러한 이름이 붙였다. 패스(pass) 버블 정렬에는 입력을 전반적으로 1번 처리하는 것을 패스라고 한다. //Bubble sort 입력 : 크기가 n인 배열 A 출력 : 정렬된 배열 A for pass=1 to n-1 for i=1 to n-pass if(A[i-1] > A[i])//위의 원소가 아래의 원소보다 크다면 A[i-1] A[i]//자리 바꾸기 return A 시간 복잡도 버블 정렬은 for 루프 속에서 for 루프를 수행하게 되는데 pass가 1인 경우 n-1 번 비교하게 되고 따라서 총 비교 횟수는 (n-1) + (n-2) .....
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/rMN1M/btrR7942jyi/wq73hfC1hrhfntuTd2Lew1/img.png)
내부 정렬(Internal sort) 내부 정렬이란 입력의 크기가 주기억 장치보다 크지 않은 경우에 수행하는 정렬이다. 예시로서는 버블, 선택, 삽입, 퀵, 힙, 쉘, 기수, 이중 피복 퀵, Tim sort 등이 있다. 외부 정렬(External sort) 내부 정렬과 반대로 외부 정렬은 보조 기억 장치에 있는 입력을 여러 번에 나눠 주기억장치에 읽어들인 후, 정렬해 보조 기억 장치에 다시 저장한다. 외부 정렬에는 다방향 합병(p-way Merge)과 다단계 합병(Polyphase Merge)이 있다.
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/GoVE5/btrR7KR5LTD/tgAve6reCw1RxDGivUcguK/img.png)
수업을 듣고 정리한 내용입니다. 동전 거스름돈 문제는 그리디 알고리즘으로 안 풀리는 경우가 있는데, 이때 동적계획 알고리즘은 항상 최적해를 구할 수 있게 해줍니다. 부분 문제 동전 거스름돈 문제에서의 부분 문제를 정의하기 위해 먼저 문제에 주어진 요소인 1. 동전의 종류 2. 거스름돈 에 대해 정리해본다. 동전의 종류를 d1, d2, ... dk 등으로 정하는 경우 d1 > d2 > ... > dk = 1을 만족해야 한다. 거스름돈은 n원이라고 둔다. 배낭 문제의 DP 알고리즘에서는 배낭의 용량을 1kg씩 증가시켜가며 문제를 해결하게 되는데, 이때 1원씩 증가시키고, 거스름돈을 배낭의 용량과 같이 생각해본다면 해결된다. //DPCoinChange 입력 : 거스름돈 n원, k개의 동전의 액면, d1 > d..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/ncBT5/btrRQi21xBf/gsaV4BOA8wggcbYY8ihZfK/img.png)
TCP school을 보고 정리한 내용입니다. 메모리 구조 프로그램이 실행되기 위해서는 먼저 프로그램이 메모리에 load되어야 한다. 또한 프로그램에서 사용되는 변수들을 저장할 메모리도 필요하다. 메모리 공간은 1. 코드(code)영역 2. 데이터(data) 영역 3. 스택(stack) 영역 4. 힙(heap) 영역 이 있다. 1. 코드 영역 은 실행할 프로그램의 코드가 저장되는 영역으로 텍스트 영역이라고도 부른다. CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리하게 된다. 2. 데이터 영역 은 프로그램의 전역 변수와 정적 변수가 저장되는 영역이다. 데이터 영역은 프로그램의 시작과 함께 할당되며, 프로그램이 종료되면 소멸한다. 3. 스택 영역 은 함수의 호출과 관계되는 지역 변수와 매개변수가 ..
포인터와 배열의 관계 배열은 배열의 이름은 그 값을 변경할 수 없는 상수라는 점을 제외하면 포인터와 같기 때문에 포인터 상수(constant pointer)라고 부르며, 포인터 상수는 포인터 변수가 가리키고 있는 주소 값을 변경할 수 없는 포인터를 의미하며, 상수 포인터(pointer to constant)란 상수를 가르키는 포인터를 의미한다. int arr[3] = (1,2,3);//배열 선언 int* ptr_arr = arr;//포인터에 배열의 이름을 대입함 위의 코드에서 포인터에 배열의 이름을 대입한 후, 해당 포인터를 배열의 이름처럼 사용하게 되는데, C언어에서는 배열의 이름을 포인터처럼 사용할 수 있을 뿐만 아니라, 포인터를 배열의 이름처럼 사용할 수도 있다. 하지만 배열의 크기를 계산할 때 배..
TCP school을 보고 정리한 내용입니다. 포인터(pointer) 포인터란 메모리의 주소값을 저장하는 변수이며, 포인터 변수라고도 부른다. 주소값이란 해당 데이터가 저장된 메모리의 시작 주소를 의미하며, C언어에서는 이러한 주소값을 1바이트 크기의 메모리 공간으로 나누어 표현한다. 포인터 연산자는 1. 주소 연산자(&) 2. 참조 연산자(*) 가 있다. 주소 연산자(&) 주소 연산자는 변수의 이름 앞에 사용하여, 해당 변수의 주소값을 반환한다. '&' 기호는 ampersand이며, 번지 연산자라고도 불린다. 참조 연산자(*) 참조 연산자는 포인터의 이름이나 주소 앞에 사용하여, 포인터에 가리키는 주소에 저장된 값을 반환한다. 포인터의 선언 타입* 포인터이름;//선언 타입* 포인터이름 = &변수이름;/..
배열(array) 배열이란 같은 타입의 변수들로 이루어진 유한 집합이다. 배열을 구성하는 각각의 값을 배열 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다. C언어에서 인덱스는 언제나 0부터 시작하며, 0을 포함한 양의 정수만을 가질 수 있다. 배열은 같은 종류의 데이터를 많이 다뤄야 하는 경우에 사용할 수 있는 가장 기본적인 자료 구조이다. 1차원 배열 1차원 배열은 가장 기본적인 배열이다. 타입 배열이름 [배열길이]; 타입은 배열 요소로 들어가는 변수의 타입을 명시하며, 배열 이름은 배열이 선언된 후에 배열로 접근하기 위해 사용된다. 배열의 길이는 해당 배열이 몇 개의 배열 요소를 가지게 되는지 명시한다. 여기서 배열을 선언만 하고 초기화하지 않으면, 각..