분류 전체보기 검색 결과

해당 글 904건
삽입 정렬 알고리즘 : 원소가 들어갈 위치는 어디인가?

정렬 알고리즘 시리즈를 쓰려고 합니다. 총 20 ~ 25편 정도로 구성이 될 듯 싶습니다. 먼저 O(n^2)짜리 알고리즘 3대장을 써 볼 건데요. 아마도, 알고리즘 교재에서는 맨 처음에 나올 듯 싶습니다. 오늘은 그 중, 삽입 정렬에 대해서 알아보겠습니다. 이 글을 이해하기 위해서는 memcpy와 memmove를 이해하면 더없이 좋을 겁니다. [관련글] 메모리 복사 함수는 어떻게 쓸까요? 삽입정렬 알고리즘은 Loop를 돌면서 해당 원소가 이미 정렬된 부분 배열에서 어디로 들어가면 좋은지를 구한 다음에, 그 위치에 넣는 식으로 동작합니다. [6, 3, 4, 2, 1, 3]을 오름차순으로 정렬한다고 해 봅시다. 수가 작을수록 우선 순위가 높을 겁니다. 먼저 1회전을 돌 겁니다. 6을 선택합니다. 제가 파란색..
자료알고/알고리즘 2019. 7. 11. 11:44
java stringbuilder vs stringbuffer : 동적 배열인 건 같은데 뭐가 다를까?

Java에는 StringBuilder와 StringBuffer가 있습니다. 이들은 어떻게 구현이 되어 있길래 append 연산을 하는데, String보다 압도적으로 빠를까요? 사실, 이 두 클래스에는 메서드 2개가 공통적으로 있다는 것을 보실 수 있습니다. 그 중에서, capacity는 눈에 띄는 함수입니다. 이것은 실제로 StringBuilder와 StringBuffer가 얼마만큼의 문자를 넣을 수 있는지 리턴해 주는 메서드인데요. 동적 배열로 따지면, 실제 배열에 할당된 크기를 의미합니다. 그러면 size와 String의 무엇과 대응이 될까요? 당연하게도 length일 거에요. 실제로 저거랑 size가 쌍으로 붙어 있다면 십중 팔구 동적 배열이다. 라고 생각하셔도 무난합니다. 저는 이 두 메서드를 가..
레퍼런스/분석 2019. 7. 10. 21:15
c언어 memcpy vs memmove : 메모리를 바이트 단위로 복사한다

메모리를 바이트 단위로 복사할 때, c나 c++ 에서는 memcpy와 memmove를 많이 사용합니다. 물론, pod 타입이여야 한다는 전제가 깔리긴 하지만요. 이 둘은 어떻게 쓸까요? c언어 memcpy나, memmove는 1번째 인자가 dest 포인터, 2번째 인자는 orignal 포인터, 3번째 인자를 몇 바이트만큼을 복사할 것인지를 넘겨줍니다. 메모리에 있는 내용을 바이트 단위로 복사하는 것은 두 함수의 공통점입니다. 삽입 정렬을 구현할 때, 이 두 함수를 잘 이용하면 좋겠지요. 첫 번째 예제 프로그램을 봅시다. int형 20개를 저장할 수 있는 ori 배열과 des 배열을 선언했습니다. 저는 ori 배열에 0, 1, ... , 19를 넣었습니다. 원소 갯수는 20개입니다. 그리고, 저는 des가..
레퍼런스/예제 2019. 7. 9. 20:36
재귀 함수 : 자기 자신을 호출한다.

뜬금없이 C언어 시간에 배우셨을 재귀함수를 왜 자료구조 카데고리에 쓸까요? 사실, 재귀 호출은, 스택을 이용한 것이거든요. 이번 시간에는 간단하게 팩토리얼 함수와 피보나치 함수 정도를 재귀로 어떻게 구현하는지 이야기 해 보도록 하겠습니다. 재귀 함수는 아시다시피, 자기 자신을 호출하는 함수를 의미하는데요. 팩토리얼 함수 f(x) = f(x-1)*x로 정의를 할 수 있어요. 그러면, 다음과 같이 작성할 수 있을 거에요. 그런데, 이렇게만 작성을 하고 컴파일을 해서 프로그램을 실행시켜 보시면, 팩토리얼 5의 값이 나오지 않는 것을 알 수 있어요. 그냥 일정 시간동안 실행이 되다가, 종료가 되어 버리는 것을 알 수 있는데요. 이건 왜 그럴까요? fact 함수 내부를 보면 x에다가 fact(x-1)의 값을 리턴..
자료알고/자료구조 2019. 7. 8. 20:10
대우 명제 : 언제 이 도구를 증명하기 위해 쓸까요?

생각난 김에, 간단하게 글을 써 보도록 하겠습니다. 수학 시간에 대우 명제를 써서 증명하는 것은 많이 해 보셨을 겁니다. 이런 걸 대체 ps 문제를 푸는 데 어떻게 쓰는 걸까요? 백준 12858번은 문제가 짧습니다. 구간 s에서 e까지의 수를 t로 바꾼다. 그리고 구간 s에서 e까지 최대 공약수를 구한다. 생각보다 문제에서 요구하는 것은 많지 않습니다. 그러면 이걸 어떻게 풀어야 할까요? 명제 p이면 q이다가 있다고 해 봅시다. 그러면 not Q이면 not P이다 또한 참입니다. ~not P는 ~not Q와 빨간색으로 칠한 부분을 합친 것이기 때문입니다. 보통 P이면 Q다. 라는 명제를 증명하기 어렵지만, ~Q이면 ~P이다를 증명하기가 상대적으로 쉬울 때, 대우 명제를 끌어와서 증명을 많이 합니다. 12..
자료알고/알고리즘 2019. 7. 6. 01:04