Computer Science18 그래프(Graph) 그래프(Graph) 그래프(Graph)는 노드/정점(Node, Vertex)와 간선(Edge)로 구성된 비선형 자료구조를 의미한다. 트리와 다르게 정점과 정점 사이의 간선이 여러 개 있을 수 있고, 순환(Cycle)이나 자체 순환(Self-Loop)도 가능하다. 그래프는 간선에 가중치(Weight)가 부여되는 경우가 많다. 트리는 그래프의 부분 집합이다. 그래프와 트리 차이 용어 정점(vertex): 위치라는 개념. (node 라고도 부름) 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름) 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프.. Computer Science/Data Structure 2022. 5. 31. 트리(Tree) & 이진탐색트리(BST) & 힙(Heap) 트리 트리(Tree)란 그래프(Graph)의 일종으로, 여러 노드가 한노드를 가리킬 수 없는 구조이다. 즉, 회로(Cycle)가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 데이터를 순차적으로 저장하지 않으므로 비선형 자료구조다. 연결된 무방향 그래프 구조이다. 용어 용어가 많아 시간이 지나면 헷갈릴 수 있다. 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node, terminal node, external node): 자식이 없는 노드, ‘외부 노드’ 또는 ‘잎 노드’라고도 부른다. 내부 노드(internal node, non-terminal node, branch node): 단말 노드가 아닌 노드, '가지.. Computer Science/Data Structure 2022. 5. 30. 스택(Stack) & 큐(Queue) & 덱(Deque) 스택(Stack) 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. 스택은 컴퓨터에서 포인터라고 하는 자료의 위치 표시자와 넣고 빼는 명령어를 사용해서 스택을 이용한다. 주로 함수를 호출할 때 인수의 전달 등에 이용되며 대표적인 예시는 아래와 같다. 웹 브라우저 방문 기록 후위 표기법 계산 실행 취소(Undo) 역순 문자열 생성 Java에서 Stack은 Vector를 상속하여 만들.. Computer Science/Data Structure 2022. 5. 27. 시간복잡도와 공간복잡도 알고리즘 성능 분석 프로그램 규모가 커짐에 따라 처리해야 하는 데이터 양도 많아지고 있다. 따라서 효율적인 알고리즘을 통해 문제를 해결하는 것은 매우 중요한 일이다. 그러면 어떻게 효율적인지 알 수 있단 걸까? 이를 분석하기 위해 일반적으로 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)를 이용한다. 시간 복잡도 우리의 컴퓨터가 연산 1회를 처리하는데 1초가 걸린다고 가정해보자. 그러면 당연히 같은 입력 데이터가 주어졌을 때 연산 횟수가 최소인 알고리즘을 사용해야 빠르게 처리할 수 있을 것이다. 결국 우리는 알고리즘이 몇 번 연산을 수행하는지 셀 수만 있으면 된다. 아래는 n의 제곱을 1씩 n*n번 더해서 구하는 함수이다. int func (int n) { int.. Computer Science/Algorithm 2022. 5. 25. 배열(Array) & 배열 리스트(ArrayList) & 연결 리스트(LinkedList) & 벡터(Vector) 배열(Array) 배열은 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다. 일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장되어, 인덱스가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다. 대부분의 프로그래밍 언어에서 사용할 수 있는 가장 기초적인 자료 구조로, 기본적인 용도 외에 다른 복잡한 자료 구조들을 표현하기 위해서 또는 행렬, 벡터 등을 컴퓨터에서 표현하는 용도 등으로도 사용된다. 배열의 첫 번째 요소의 메모리 주소를 첫 번째 주소, 기본 주소 또는 기본 주소라고 한다. 장점 인덱스를 통해 접근하기 때문에 시간 복잡도가 O(1)이다. 데이터의 크기가 고정적일 때, 배열을 이용하면 메모리 사용량이나, 처리 속도면에서 좋다. 구현이 쉽다. 단점 크.. Computer Science/Data Structure 2022. 5. 25. [백준] 1149번: RGB거리 - Java 1. 문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2. 접근 방법 및 유의할 점 i번째 집의 색은 i-1번째, i+1번째 집과 색이다르다는 말을 i-1번째, i번째, i+1번째 집의 색이 모두 달라야한다라는 말로 이해하지 말아야한다. 예를 들어, "빨 파 빨" 도 가능하다는 뜻이다. 이는 첫 번째 집을 제외한 모든 집이 앞집과 색이 다르다는 조건으로 이해해서 활용하면 좋다. 이 힌트를 가지고 문제조건을 생각해보자... Computer Science/Coding Test(Java) 2022. 5. 2. 이전 1 2 다음