전체 글 검색 결과

해당 글 904건
링크드 리스트 : 왜 순회 시간이 배열보다 오래 걸릴까요?

리스트와 배열의 차이점은 면접에서 자주 나오는 질문 중에 하나입니다. 저에게 메일로 질문이 들어온 것 중 하나는, 순회 속도가 어떻게 차이가 나느냐였습니다. 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)라면 이건 어떨까요?..
자료알고/알고리즘 2019. 7. 3. 00:25
c언어 단축 평가 : 언제 조건을 볼 필요가 없을까?

단축평가는, 계산을 하는 도중에 이미 결과값이 확정된 경우에, 나머지 계산 과정을 생략하는 것입니다. 예를 들어서 A or B or C라는 수식이 있다고 해 봅시다. 만약에 A가 참이라면 어떨까요? B나 C가 참이던 거짓이던 A or B or C는 참이 될 겁니다. 즉, B나 C는 볼 필요가 없다는 겁니다. 예제를 통해서 이해해 봅시다. 먼저, a, b, c의 값은 각각 0, 0, 0입니다. 논리 연산자는 좌측에서 우측으로 들어가는데요. ((b++
코딩/C 2019. 7. 2. 00:20
java hashCode vs identityHashcode : 이 둘은 무엇이 다를까요?

Java hashCode랑 identityHashCode의 차이점이 무엇일까요? 그에 대해서 답을 하기 전에, 간단한 실험을 하고 넘어갑시다. identityHashCode는 객체가 다르면, 무조건 다른 값을 리턴할까요? 즉, 이 메서드의 리턴 값이, 객체의 고윳값이 될 수 있을까요? 사실 저는 그런 줄 알았습니다. 100만개짜리 Object 객체 배열을 만들었습니다. 그리고, 100만개의 Object 객체를 만들었습니다. 그리고, 객체 arr[i]의 identityHashCode 값을 treeset에다가 넣었습니다. 만약에, 객체 각각의 identityHashCode가 고유하다면, treeset에 들어간 원소 갯수는 100만개였을 겁니다. 그런데 실제로는 999768개입니다. TreeSet은 기본적으로..
레퍼런스/분석 2019. 7. 1. 00:15