전체 글 검색 결과

해당 글 711건
재귀 함수 : 자기 자신을 호출한다.

뜬금없이 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
링크드 리스트 : 왜 순회 시간이 배열보다 오래 걸릴까요?

리스트와 배열의 차이점은 면접에서 자주 나오는 질문 중에 하나입니다. 저에게 메일로 질문이 들어온 것 중 하나는, 순회 속도가 어떻게 차이가 나느냐였습니다. n이 작을 때는 별 차이가 없을 수도 있습니다. 하지만 n이 3000 ~ 4000만 정도만 되도 이야기가 달라집니다. 배열은 순차적으로 저장이 되지만, 리스트는 그렇지 않습니다. cache를 이용하기 좋은 구조는 리스트보다 배열이라는 겁니다. 정말 그런지 실험을 해 봅시다. 배열과 링크드 리스트의 순회 성능 테스트를 위한 코드를 작성해 봅시다. node형을 하나 선언해 주었는데요. data 필드와, 다음 주소를 가리킬 필드를 선언해 주었습니다. 단일 링크드 리스트는 포인터가 1개, 더블은 2개일 거에요. C++의 리스트는 더블로 구현이 되어 있습니다..
자료구조 2019. 7. 4. 18:08
c언어 time 함수 : 현재 시간을 초단위로 리턴한다.

time.h에 들어있는 time 함수는 어떻게 쓰일까요? 이 함수는 1970년 1월 1일 0시 0분 0초부터, 현재 시간까지 경과된 초를 리턴합니다. 예를 들어서 현재 시간이 1970년 1월 2일 0시 0분 0초라면, 86400이 리턴될 겁니다. 이 함수와 관련된 문제 중에는, 2038년 문제가 있는데요. 이것은 오버 플로우를 설명할 때 다시 언급해 드리도록 하겠습니다. time_t는, time_t의 포인터 변수를 받습니다. 그리고, 리턴하는 값 또한 time_t형인데요. 이것은 그냥 integer type이라고 생각하시면 편합니다. 그런데, 1번째 인자에 NULL을 넣을 수도 있고, time_t형 변수의 주솟값을 넣을 수도 있습니다. 다음 예제를 통해서, 이 두 가지 경우에 어떻게 동작하는지 보도록 합..
레퍼런스/예제 2019. 7. 3. 18:35
냅색 알고리즘 문제 : 가방에 어떻게 넣어야 이득이 최대일까?

12번째 글은, 냅색 알고리즘 문제입니다. 이것도 꽤 여러 종류가 있는데요. 쪼갤 수 있는 물건이냐, 그렇지 못하냐에 따라서, 그리디로 접근을 할 수 있는지, 아니면 dp로 접근해야 하는지가 나뉩니다. 저는 0/1 냅색 문제를 다뤄 보겠습니다. 이것은 물건을 쪼갤 수 없어요. 물건이 n개가 있습니다. 그리고 가방에 넣을 수 있는 무게는 W입니다. 이 때, 가방에 넣을 수 있는 물건들의 최대 이익은 얼마나 될까요? 먼저 기저 조건을 생각해 봅시다. 물건 0개를 넣었을 때, 가방에 넣은 물건의 총 무게는 0, 이익 또한 0일 겁니다. 따라서, dp[0개][용량 0]을 넣었을 때 값은 0입니다. 대충 이런 경우입니다. 만약에 물건 0개를 넣었는데, 가방에 넣은 물건의 총 무게가 x(x>0)라면 이건 어떨까요?..
알고리즘/ps 2019. 7. 3. 00:25
반응형