All :L

[그래프의 종류와 구현]그래프그래프(Graph) : 정점이라 불리는 데이터를 간선 혹은 링크로 연결한 형태데이터 간의 연결 관계를 표현연결 그래프(connected graph) : 임의의 두 정점 사이의 경로가 존재하는 그래프비연결 그래프(disconnected graph) : 정점 사이에 경로가 존재하지 않을 수 있는 그래프방향 그래프(directed graph) : 간선에 방향이 있는 그래프무방향 그래프(undirected graph) : 간선에 방향이 없는 그래프가중치 그래프(weighted graph) : 간선에 가중치가 부여된 그래프비용(cost) : 간선에 부여된 값서브 그래프(subgraph) : 특정 그래프의 정점과 간선의 일부분으로 이루어진 그래프인접 행렬 기반 그래프 표현N X N 크기..

[트리]트리트리(tree) : 주로 계층적인 구조를 표현하기 위한 자료구조노드(node) : 데이터를 저장하는 구성 요소간선(edge) : 노드와 노드를 연결하는 선, 링크라고도 함링크로 연결된 노드는 상하 관계 형성용어설명부모 노드(parent node)어떤 노드의 상위에 연결된 노드자식 노드(child node)어떤 노드의 하위에 연결된 노드형제 노드(sibling node)같은 부모 노드를 공유하는 노드조상 노드(ancestor node)부모 노드와 그 부모 노드들자손 노드(descendant node)자식 노드와 그 자식 노드들루트 노드(root node)트리의 최상위 노드, 부모 노드가 없는 노드리프 노드(leaf node)트리의 최하위 노드, 자식 노드가 없는 노드차수(degree)어떤 노드가..

[해시 테이블]해시 테이블해시 테이블(hash table) : 키(key)와 값(value)의 대응으로 이루어진 테이블과 같은 형태의 자료구조키(key) : 해시 테이블에 대한 입력값(value) : 키를 통해 얻고자 하는 데이터버킷(bucket) : 값이 저장되어 있는 곳여러 개 존재 → 여러 버킷이 배열 형성로드 팩터(load factor) : 해시 테이블에 저장된 데이터 수를 버킷의 수로 나눈 값테이블이 얼마나 가득 차 있는지에 대한 지표로드 팩터가 클수록 해시 테이블 성능 ↓구조검색, 삽입, 삭제 연산의 시간 복잡도 : O(1) → 입력과 무고나하게 항상 일정한 속도 보장단점속도 ↑ but, 메모리 공간 소모 多공간 복잡도가 시간 복잡도만큼 우수하지 X충돌 문제 해결 필요[해시 함수]해시 함수해시..

[스택]스택스택(stack) : 한 쪽에서만 데이터 삽입 및 삭제가 가능한 자료구조푸시(push) : 데이터를 저장하는 연산팝(pop) : 데이터를 빼내는 연산후입선출(LIFO) : 한 쪽에서만 데이터 저장, 관리되기 때문에 나중에 삽입된(후입) 데이터가 먼저 나옴(선출)활용 사례 1) 최근에 임시 저장한 데이터를 가장 먼저 활용해야 할 때 (매개변수 저장) int bar(int y) { return y + 2; } int foo(int x) { bar(2); return x + 1; } foo(1);매개변수 x → 1로 초기화bar 함수 호출 → 매개변수 y → 2로 초기화bar 함수 (2 + 2) 반환 → 매개변수 y 삭제foo 함수 (1 + 1) 반환 → 매개변수..

[배열]배열배열 : 일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조각 요소는 0부터 시작하는 고유한 순서 번호인 인덱스를 매김인덱스가 주어졌을 때 특정 요소에 접근하는 연산 : O(1)서로 다른 N개의 데이터에서 특정 데이터를 찾는 연산 : O(N)특정 인덱스의 요소를 추가하는 연산 : O(N)특정 인덱스의 요소를 삭제하는 연산 : O(N)정적 배열프로그램을 실행하기 전 크기가 고정되어 있는 배열프로그램 도중 변경 X동적 배열실행 과정에서 크기가 변할 수 있는 배열배열의 크기를 알기 어려운 경우, 유연하게 요소 개수를 조정해야 하는 경우 사용동적 배열을 벡터라는 이름으로 구현한 프로그래밍 언어도 존재[연결 리스트]연결 리스트노드 : 데이터와 다음 노드의 위치(메모리 상의 주소) 정..

[자료구조와 알고리즘]자료구조자료구조 : 데이터를 다루기 위한 어떠한 구조알고리즘알고리즘 : 어떠한 목적을 이루기 위해 필요한 일련의 연산 절차⇒ 어떤 자료구조가 사용되었는지에 따라 사용 가능한 알고리즘이 달라짐[시간 복잡도와 공간 복잡도]시간 복잡도시간 복잡도(time complexity) : 입력 크기에 따른 프로그램 실행 시간(연산 횟수)의 척도실행 시간은 연산의 횟수에 비례공간 복잡도공간 복잡도(space complexity) : 입력에 따른 메모리 사용량의 척도메모리 사용량 多 → 공간 복잡도 大 / 메모리 사용량 少 → 공간 복잡도 小⇒ 소스 코드나 프로그램이 얼마나 효율적인지 판단하는 척도 (대부분 시간 복잡도 사용)표기법빅 오 표기법(big O notation) : 함수의 점근적 상한을 표..