재귀 호출에 대해서 저번시간에 쭉 배워보았습니다. 이번에는 자료구조 스택에 대해서 배워보고, 활용을 해 보도록 하겠습니다. 사실 계산기 프로그램 하나로 될 거 같긴 하지만, 더 좋은 예제가 없는지 고민을 해 보겠습니다. 하튼, stack은 나중에 넣은 원소가 먼저 빠진다는 특성 (Last In First Out : LIFO)을 가지고 있는데요. 주요 연산들만 간단하게 알아보는 시간 가지도록 합시다. 먼저 스택은 크게 2가지 포인터로 이루어져 있습니다. base pointer, 줄여서 bp입니다. 그리고 top pointer, sp라고 많이 이야기를 할 거에요. base는 스택의 시작점이 되는 포인터, 그리고 top은 실제로 꼭대기에 있는 원소를 가리키게 되어요. 만약에, 비어 있다면 top은, 배열로 구..
분류 전체보기 검색 결과
파이썬을 공부할 때도 얕은 복사, 깊은 복사에 대한 이야기는 상당히 많이 나옵니다. 톡이나 메일로 받은 질문 중에서 높은 빈도로 있었던 것 중 하나였습니다. 얕은 복사는 주솟값을 복사합니다. 즉, 사본이 바뀐다면 원본도 바뀝니다. 깊은 복사는 내용물을 복사합니다. 그렇기 때문에, 사본을 복사해도 원본이 바뀌지 않습니다. 간단한 예제 프로그램을 보면서 이해해 봅시다. 프로그램 1을 봅시다. 저는 Monster 객체 2개를 생성했습니다. 하나는 hp가 3700이고 데미지가 270인 몬스터를 생성했습니다. 그리고 다른 하나 b에는 a를 집어 넣었는데요. 이 때 어떤 일이 일어나는지 봅시다. a는 새로 생성된 객체를 가리킬 겁니다. 그런데 b에다가 a의 값을 넣었어요. 그러면 b도 같은 객체를 가리킬 겁니다. ..
오늘은 선택 정렬 알고리즘에 대해 공부해 봅시다. selection sort는 매 회전마다, 제일 우선 순위가 높은 값을 선택해서 재정렬 하는 알고리즘입니다. 배열 arr의 크기가 n이라고 해 봅시다. 그러면 총 n회전을 돌 건데요. i회전일 때 이러한 일을 수행합니다. 구간 [i,n]에서 우선순위가 가장 높은 위치 lo를 찾습니다. 그리고 배열에서 i번째 원소와 lo번째에 있는 값을 맞바꿉니다. 구간 [i,n]은 정렬이 되어 있지 않기 때문에, 우선 순위가 가장 높은 값과 위치를 찾기 위해서, i에서부터 n까지 보아야 합니다. 그러므로, 회전마다 O(n-i)만큼 걸리게 되고, 결과적으로 시간 복잡도는 O(n^2)가 됩니다. 매 회전마다, O(log(n)) 급에 해결할 수 있는 방법이 있는데, 특수한 자..
사원 이름 name과 월급 salary로 구성되어 있는 db 테이블이 있다고 생각해 봅시다. 아직 직급 필드는 없다고 생각해 봅시다. 월급 협상이 안 된 신입 직원 분들도 있다고 해 봅시다. 그럴 일이 있을지는 잘 모르겠지만요. 그러면 salary가 null값인 레코드가 있다는 것입니다. 일단 레코드 5개만 추가해 봅시다. 데이터 베이스 이름은 worker입니다. 필드가 2개입니다. 하나는 worker_name, 다른 하나는 salary입니다. worker_name은 반드시 5자가 아니기 때문에, 가변 길이를 이용하였습니다. 그리고 월급은 정수형으로 표현할 수 있기 때문에, int로 설정하였습니다. 그리고 다음과 같이 데이터를 넣습니다. salary 필드에 not null 조건이 붙어 있지 않은 걸로 보..
c++이나 java에는 부분 문자열을 가지고 오는 함수가 있습니다. 각각 substr과, substring이에요. 예를 들어, 어떠한 문자열 str = "chogahui"가 있고, 1번째부터 3번째까지 가지고 온 부분 문자열 sub = "hog"일 거에요. 이걸 가지고 오는 함수를 string.h에서는 찾기가 힘듭니다. 그러면 이것을 어떻게 구현해야 할지, 생각해 봅시다. 사실 핵심적인 것은 간단합니다. 어떠한 시작 위치에서부터 t개 만큼을 어딘가로 복사한다. 만약에 문자열 str에서 [s,e)까지의 부분 문자열을 복사한다면 e-s개를 어딘가로 복사를 하는 것입니다. 그러면, 문자열을 복사를 하는데, 시작 위치로부터 t개만큼 copy 하는 함수를 찾으면 되는데요. 그것이 strncpy 함수입니다. cha..
최근댓글