Algorithm] 동적계획법 - 연속 행렬 곱셈

연속된 행렬들의 곱셈에 필요한 원소 간 최소 곱셈 횟수를 찾는 문제로,일단 연속된 행렬 간의 곱셈이 모두 가능하다는 전제 조건 하에 이루어진다. A=10X20, B=20X5, C=5X15 다음 세 행렬에 대한 계산을 예로 들면, AxBxC는 두 가지 방법으로 계산할 수 있다. 1. (AxB)xC2. Ax(BxC) 두 가지 계산은 결과는 아무 차이가 없지만, 순서에 따라서 두 행렬 곱셈의 횟수가 차이가 나기 때문에이를 최소화하고자 하는 방법을 구성할 필요가 있다. 일단, 1번의 계산을 예로 들면, 1번의 계산에서는 AxB는 10x20x5로, 1000회의 원소 곱셈을 시행하고,AxB 행렬은 10x5로, (AxB)xC는 750회 곱셈을 진행해 전체적으로 1750회의 원소 곱셈을 시행해야 한다. 2번의 계산은 ..

해시테이블(Hash Table)과 체이닝(Chaining)에 대한 간략한 정리

해싱과, 해시테이블 그리고 충돌을 처리하는 체이닝 기법에 대해서 한 번 정리해보자.이 글을 시작하기에 앞서, 스택오버플로우의 많은 자료들 그리고 위키피디아, 각종 유튜브 강의를 참고했다는 사실을 먼저 알립니다. 해시와 해시함수 해시 함수(Hash Function)는 데이터의 효율적인 관리를 위해 길이가 각기 다른 데이터를 고정 길이로 매핑하는 함수다. 이 때 매핑하는 과정을 해싱(Hashing)이라고 하며, 매핑하기 전의 데이터를 키(Key), 매핑 후의 데이터를 해시 값(Hash Value; 때로는 Value)이라 한다. 해시의 목적 해시 테이블(Hash Table)해시 테이블은 데이터의 해시 값을 테이블 내 주소로 이용해먹는 탐색 알고리즘으로, 잘 구현하면 이진 탐색보다 빠르게 처리할 수 있다. 암호..

두근두근 자료구조 2장 연습문제

어떤 것들은 심심할 때마다 다시 공부하곤 하는데, 자료구조도 그 중 하나다. 개인적으로 공부하면서 정리한 것들이고 답이 틀렸을 수도 있기 때문에 지적은 언제나 환영한다. 1. int a[10][20]에서 배열이 차지하는 메모리 공간의 크기는 얼마인가? int형은 4바이트라고 하자.(4) 800 바이트, 10x20x4 2. float a[100]으로 선언된 배열의 시작 주소를 1000번지라고 할 때, 배열의 10번째 요소의 주소는 몇 번지인가?(4) 1040번지, 1000+10x4 3. 다음 배열 중에서 크기가 가장 큰 배열은?메모리 크기 기준(2) double array2[10]; 10x8 = 80바이트인덱스 크기 기준(3) char array3[40]; 40 4. 크기가 10인 배열 two[]를 선언하..

C, C++] 이중 포인터를 이용해 2차원 배열 사용하기

동적 할당을 사용하면 포인터는 배열처럼 사용할 수 있다.여기까진 포인터를 어렴풋이 아는 입문자들도 포인터의 연산과 배열의 인덱스를 연관지어 어렵지 않게 이해할 수 있는 부분인데, 문제는 이중 포인터를 이용해서 2차원 배열을 선언할 때 발생한다. 일단 본론에 들어가기 앞서, 포인터를 이용해서 배열을 사용하는 방법을 그림과 식으로 이해해보자. Cint* ptr = NULL; ptr = (int*)malloc(sizeof(int)*5); C++ int* ptr = nullptr; ptr = new int[5]; 어렵지 않게 요소 5개 짜리 int형 배열을 동적 할당했다. 포인터를 외우듯 공부한 사람들이어도 아래 그림까지는 어렵지 않게 그려내고 이해할 수 있다. 이제 2차원 배열을 어떻게 동적 할당할 지 생각해..

C,C++ 2018.05.16 2

DataStructure] C언어로 쉽게 풀어쓴 자료구조 4장 - 2

DataStructure] C언어로 쉽게 풀어쓴 자료구조 4장 - 2 C언어로 쉽게 풀어쓴 자료구조4장 Exercise 문제들이다.필자가 학교 다니면서 자료구조론 수업을 들었는데,과제로 제출했던 것들이고,난항을 겪고 있는 사람들에게 참고가 되었으면 하는 마음으로 올린다.자고로, 버그가 존재할 수 있으니 디버깅 작업은 필수다. 14. 단순 연결 리스트에 정수가 저장되어 있다. 단순 연결 리스트의 모든 데이터 값을 더한 합을 출력하는 프로그램을 작성하여라. 15. 단순 연결 리스트에서 특정한 데이터 값을 갖는 노드의 개수를 계산하는 함수를 작성하라. 16. 단순 연결 리스트에서의 탐색 함수를 참고하여 특정한 데이터 값을 갖는 노드를 삭제하는 함수를 작성하라. 17. 단순 연결 리스트의 헤드 포인터가 주어져 ..