본문 바로가기

computer

해시테이블 개념 2020. 8. 7. 00:45 ※이 자료는 공부를 목적으로 출처에 기입한 여러 자료를 단순히 정리한 것입니다. 해시테이블 해시테이블은 키를 값에 매핑할 수 있는 구조인 연관 배열 ADT를 구현하는 자료구조이다. 컴퓨터는 숫자를 해석하는 것으로 컴퓨터에서 숫자는 해석에 따라 숫자, 글자, 픽셀, 명령어 등으로 나뉜다. 해시테이블은 자료구조 컨테이너 중 모든 것은 숫자로 표현한다는 특성을 이용해 효율적인 삽입, 삭제, 탐색이 가능한 자료구조이다. 해시함수(hash function) 해시 함수는 임의 길이의 데이터를 고정된 길이로 매핑하는 함수이다. 해시 함수의 결과 값을 해시 값, 해시 코드, 해시 체크섬, 간단하게 해시라고 한다. 성능이 좋은 해시 함수의 특징은 아래와 같다. 해시 함수 값 충돌의 최소화 쉽고 빠른 연산 해시 테이블 전..
Python 리스트의 편리함 2020. 2. 13. 15:14 요즘 C로 자료구조를 공부하고 있다. 한편으로는 석사 신입생 교육에 인공지능 조교로 참여하고 있다. 조교로써는 파이썬을 교육을 보조하고 있는데, 시간이 남아 파이썬으로 DFS, BFS를 구현하던 중 파이썬의 리스트가 편리하다는 것을 다시 한번 느꼈다. 리스트에 extend()를 통하여 element를 추가하면 queue나 stack 자료구조에 삽입하는 것과 같이 동작한다. 데이터를 pop할때는 pop(0)을 하게 되면 queue처럼, pop()을 하게되면 stack처럼 동작한다. c의 배열은 리스트와 같은 역할을 하지만 리스트는 길이를 정하지 않고 리스트를 사용하기 쉽다. pop으로 자료를 추출해도 index를 다시 조정하지 않아도 된다. c에서는 배열이나 링크드 리스트를 통해 stack과 queue를 ..
하나의 테이블에서 0값을 포함해 count 하기 2018. 11. 28. 18:08 하나의 테이블에서 0값을 포함해 count 하기 프로젝트 중 웹에 올리기 위해 db에서 쿼리를 날리던 중 해결이 안되던 부분이 있어 Stackoverflow에 질문을 올려 도움받았다. [sql count(including null) from table where two conditions]의 제목으로 질문했다. team_summary와 team_stats 테이블에 tName과 W // Period, tName, win_lose의 컬럼이 있는데, 각 팀의 win_lose가 1인 값( 승리한 경기)를 합하려는 sql이다. 밑의 query에 대한 결과는 0을 포함하지 않는다. team_summary team_stats tName W Period tName win_lose AUT null 1 AUT 1 CAN ..
Counting sort(계수 정렬) 2018. 8. 30. 15:13 계수정렬에는 세개의 배열이 필요하다. 우선 정렬해야할 수들을 담은 array1최대 값을 기준으로 숫자들의 누적합을 담을 array2마지막으로 정렬된 수를 담을 array3이다. 예를들어 최대 값이 5라면 array2에는 0부터 5까지 index를 이용해 6가지 수의 개수를 표현할 수 있다.array1을 [4,1,0,1,1,2,1,2]라고 하자.우선 array2를 누적합이 아닌 index를 숫자로, value를 개수로 생각하면 [1,4,2,0,1,0]인 배열이 된다.이를 누적합으로 표현하면 [1,5,7,7,8,8]로 나타낼 수 있다.누적합은 0번째 index에서 시작하여 이전 index와의 합으로 누적합을 구한다. 마지막으로 array3에 정렬된 수를 넣기 위한 작업이 있다.array1의 맨 우측부터 시작..
소수 판별하기 2018. 8. 24. 12:59 백준 1978번을 풀다가 소수에 대해 생각했다. 문제의 핵심은 1000이하의 N개의 숫자가 주어졌을 때 소수의 개수를 새는 것이다. 처음에는 소수의 특징을 파악한 후 각 숫자가 소수인지 아닌지를 판별하는 방법을 써야하나 싶었는데,소수가 1과 본인을 제외한 수로 나눠지지 않는다는 특징 때문에 위의 방법을 사용하기 어려웠다. 결국 가장 효율적이라고 알려진 '에라토스테네스의 체'라는 방법을 이용해 1000이하의 수 중에서 소수만 리스트에 남기고입력받은 수 중에 리스트에 포함되있는 수를 세어 결과를 산출했다. 소수를 세기 위한 방법으로는 숫자를 그 이하 모든 수로 나눠 떨어지는지 확인하는 방법을 가장 쉽게 생각할 수 있다.이를 더 효율적으로 하기 위해 소수가 아닌 수는 결국 곱으로 나타낼 수 있고 n의 제곱근을..
k-Means 2018. 6. 5. 10:40 Basic concepts of Partitioning methodspartitioning method는 초기 분할(initial partitioning)을 하고 반복적으로 재분배 테크닉(iterative relocation technique)을 사용해 분할을 개선한다. -k-means, k-medoids, PAM K-means clustering1. 전체 데이터 포인트 중 임의로 k 개를 클러스터의 시작 중심점으로 선택2. 모든 데이터 포인트를 가장 유사한 클러스터로 할당(distance similarity (Euclidean distance))3. 각 클러스터에 할당된 포인터들을 기반으로 클러스터의 중심 점을 업데이트4. criterion function이 통합될때 까지 2-3번 과정을 반복 Eval..

티스토리툴바