전체 글(55)
-
그래프
그래프 비선형적 자료구조. 회사 조직도와 같은 계층을 표현한다던가 친구 관계도를 표현하는 것처럼 말이다. 그래프(graph)는 관계에 특화된 자료구조로 정점(Vertex)과 간선(Edge)으로 구성되어 있다. 각 정점은 고유하게 식별되는 객체이고, 간선은 정점 간의 관계를 표현한다. 종류 그래프의 종류에는 간선이 방향성을 가는것으로 그래프를 판단해서 알수있는 방향 그래프와 무방향 그래프로 구분할수있으며 간선이 단순 연결 이상의 정보를 가지는 가중치 그래프도 있다. 용어 정점끼리는 인접(Adajcent)하다고 한다. 부속(Incident)되어 있다고 한다. 정점에 부속되어 있는 간선의 수를 차수(Degree)라고 하며 정점으로 들어오는 방향인지, 나가는 방향인지 구분해 진입 차수(In-degree), 진출..
2022.07.05 -
나무(Tree)
트리는 그래프의 일종으로 계층형 자료구조 트리는 데이터가 저장된 노드(Node)와 노드 간 관계를 표현하는 간선(Edge)으로 구성된다. 용어 트리에는 여러가지 용어가 있다. 그림을 참고하자 루트(Root) : 첫 노드 조상(Ancestor) 노드 : 한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드 자손(Descendant) 노드 : 조상 노드의 반대 차수(Degree) : 한 노드가 가지는 서브 트리의 수. 노드의 차수 중 최댓값을 트리의 차수라 한다. 내부(Internal) 노드 : 단말 노드를 제외한 나머지 노드 ex) A , B , C , D , E 포레스트(Forest) : 트리의 집합 레벨(Level) : 높이 순회 전위 순회 DFS 방식과 비슷하다 A - B - D - ..
2022.07.04 -
Stack 1,2,3,4
https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 10820번 vector로 품 더보기 #include #include #include using namespace std; //1. 명령어의 수 2. 둘쨰 줄부터 N개의 줄에는 명령이 하나씩 주어진다. //주어지는 정수는 1보다 크거나 같고, 100000보다 작거나 같다. //문제에 ㅏㄴ와있지 않은 명령이 주어지는 경우는 없다. int main() { std::vector sta..
2022.06.22 -
자료 구조 리스트(선형리스트,연결리스트)
(선형리스트) 순차 자료 구조 (배열을 이용) 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 구현 방식 모든 데이터가 메모리에 연속적으로 저장된다. 데이터 저장을 위해 정확하게 데이터 크기만큼 메모리를 사용한다. 읽기 선형 리스트는 임의 접근이 가능하기 때문에 O(1)의 시간이 걸린다. 검색 하나하나 원소를 비교해가야 하므로 O(n)의 시간이 걸린다. 정렬되어 있다면 이진 검색을 사용할 수 있으며 이 경우 O(logn)이다. 삽입 원소를 어디에 삽입하냐에 따라 시간이 달라진다. 맨 끝에 데이터를 추가할 경우 O(1)이지만, 처음이나 중간이라면 모든 데이터를 이동해야 하기에 O(n)이 걸린다. 삭제 삽입과 마찬가지로 원소를 어디에서 삭제하냐에 따라 시간이 달라진다. 맨 끝의 데이터를 삭제할 ..
2022.06.21 -
프로그래머스
수포자 모의고사 https://programmers.co.kr/learn/courses/30/lessons/42840# 교수님이 나의 생각으로 접근한 방식 더보기 #include #include #include using namespace std; vector solution(vector answers) { size_t size = answers.size(); int counts[3] = { 0 }; for (size_t i = 0; i < size; i++) { int currentAnswer = answers[i]; if (currentAnswer == 1) { if (i % 5 == 0) { counts[0]++; } if (i % 8 == 1) { counts[1]++; } if (i % 10 =..
2022.06.21 -
c++ 프로그래밍 6/17일
C++ 문자열 라이브러리 empty() 빈 문자열 확인하는 함수 push_back() : 첫글자 삽입 함수 append() : 문자열에서 문자열 삽입 함수 연산자 "문자열" 해도 문자열 삽입가능하다. insert (문자열 자리, 삽입할 문자열) pop_back() :마지막 문자삭제 erase(5,9) :삭제할문자열 첫자리부터 끝자리까지 == , != , > ,
2022.06.17