그래프연결 관계를 표현하는 자료구조 정점이라 불리는 데이터를 간선, 혹은 링크로 연결한 형태트리도 사실 그래프의 일종이다.그런데, 트리는 노드간 상하관계를 가지며 사이클 형성 X그래프는 상하관계 X, 사이클 형성 가능 -> 기본적으로 연결 관계를 표현함연결 그래프그래프상의 임의의 두 정점 사이의 경로가 존재하는 그래프 비연결 그래프어떤 정점 사이에는 경로가 존재하지 않을 수도 있다.방향 그래프간선에 방향 존재무방향 그래프방향이 없는 그래프가중치 그래프간선에 가중치가 부여된 그래프. 이 가중치는 비용이라고도 함.서브그래프(부분 그래프)특정 그래프의 정점, 간선의 일부분으로 이루어진 그래프 ❓이 그래프들은 어떻게 구현하고 저장할까? 노드간 상하관계도 없는데... 인접 행렬 기반 그래프 표현N × N 크기..
해시 테이블 (hash table)키(key), 값(value)의 대응으로 이루어진 표(테이블)와 같은 형태의 자료구조키: 해시 테이블에 대한 입력값: 키를 통해 얻고자 하는 데이터 해시 함수 (hash function)임의의 길이를 지닌 데이터 -> 고정된 길이의 데이터로 변환하는 단방향 함수단방향이므로, 반대로 해시 값을 토대로 어떤 데이터가 입력되었는지를 도출하긴 어려움 해시 알고리즘 (hash algorithm)대표적으로 MD5, SHA-1, SHA-256, SHA-512, SHA3, HMAC 등...알고리즘에 따라 도출되는 해시값의 길이나 값이 다름 문자열이 한 글자만 달라져도 도출되는 해시값이 크게 달라짐.-> 무작위 값 만들거나, 단방향 암호 만들 때, 데이터의 무결성 검증시 사용 ❓..
자료구조란?어떠한 구조로 데이터를 다룰 것인지! 시간 복잡도입력의 크기에 따른 프로그램 실행 시간의 관계표기법: 빅 오 표기법, 빅 세타 표기법, 빅 오메가 표기법더보기빅 오 표기법: 함수의 점근적 상한 표기빅 세타 표기법: 입력에 대한 평균적인 실행 시간빅 오메가 표기법: 입력에 대한 실행 시간의 점근적 하한 빅 오 표기법: 최고차항의 차수만 고려한다. 공간 복잡도프로그램 실행시 필요한 메모리 자원의 양 (즉, 메모리 사용량의 척도) 배열과 연결 리스트 배열 (Array)일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조0부터 시작하는 고유 번호, 인덱스가 매겨짐. 인덱스를 통해 요소에 접근 or 수정하는 시간은 요소 개수와 무관하게 일정. 즉, O(1)앞부터 차례대로 특..