두런두런

이전내용 링크 완전탐색 정렬 문자열 배열,리스트 스택,큐 10. 해시(해시 함수) 특정 자료에 빠르게 접근 하기 위한 함수 Key-Value 개념으로 Key 값을 통해 Value에 접근한다. 10-1. Direct Addressing Table 테이블에 Key값 을 인덱스로 저장하는 방법이다. 예로 Value 값이 100이라면 배열의 인덱스가 100인 위치에 Key 값을 저장하고 포인터로 데이터(Value)에 연결한다. 같은 값이 존재하지 않는다고 가정하면(같은 값을 가지는 경우 충돌,Collision 이 발생한다) 데이터의 탐색, 저장, 삭제, 갱신 모두 상수 시간 O(1)에 처리가 가능하다. 하지만 Key값의 크기만큼 배열이 할당 되기 때문에 데이터의 개수가 적고 값이 큰 경우에 메모리 낭비가 발생한..

이전내용 링크 완전탐색 정렬 문자열 5. 배열 & 동적배열 일렬로 늘어선 (같은 종류의)자료 여러개를 저장하기 위한 가장 기초적인 자료구조는 배열이다. 배열과 비슷한 자료구조로 연결 리스트가 존재한다. 배열은 처음 선언할때 크기를 지정해야 하며, 선언된 크기 이상의 자료를 넣을 수 없다. 이를 해결하기 위해 동적 배열이 존재 한다. 동적 배열은 배열을 이용한 별도의 자료 구조이며 대부분의 언어에서 문법이 아닌 표준 라이브러리에 포함 되어있다. 배열(동적배열) 은 다음과 같은 특징이 있다. 원소들이 메모리의 연속된 위치에 저장된다. 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다. 동적배열의 추가적인 특징은 다음과 같다. 배열의 크기를 변경하는 연산(resize)이 가능하다(해당 연..

취업준비를 하면서 알고리즘 공부의 필요성(코딩테스트)를 느꼈고, 연구실 후배들과 알고리즘 스터디를 진행했다. 0주차 계획 수립을 마치고 1주차 스터디를 진행한다. 이론 진행을 우선 하기로 의논되었고, 첫주에는 완전탐색, 정렬, 문자열에 대해 공부했다. 1. 완전탐색 가장 단순한 알고리즘이다. 무식하게 푼다(Brute Force) 라는 말이 있다. 해당 방법은 컴퓨터의 빠른 연산 속도를 이용해 경우의 수를 모두 나열하여 답을 찾는 방법이다. 예) 10명을 일렬로 줄 세울때, 사이가 나쁜 두 사람이 붙어있지 못하게 하는 경우 10명을 일렬로 세우는 모든 방법을 찾는다(10! 약 360만 가지) 그중 두사람이 붙어있는 경우를 제외한다. 책 '알고리즘 문제해결 전략' 에서는 이와같은 완전탐색 기법을 알고리즘의 ..