자료구조8

• 

  [백준/BOJ] 15926번: 현욱은 괄호왕이야!! 문제https://www.acmicpc.net/problem/15926해설처음 문제에 접근한 방법은 다음과 같았다."(" 라면 Stack에 집어넣는다.")"이며 Stack이 비어있지 않다면 길이에 2를 더한 후 max 값을 갱신한다.")"이며 Stack이 비어있다면 Stack과 길이를 초기화시킨다.문제를 너무 단순하게 접근하였는지 당연히 틀렸습니다를 받게 되었다.문제에 나와있는 테스트케이스를 모두 통과하기에 질문 게시판에서 추가 테스트케이스를 확인하였고,(()(()()(()( 위와 같은 케이스에서 답이 4가 나와야 하지만 8이라는 오답이 나오는 것을 확인할 수 있었다.나의 풀이대로면 아래와 같이 된다.이렇게 적어가면서 했다면 당연히 아니란걸 알았을테지만 너무 느낌대로 풀었던 것 같다. 때문에 다른 해결 .. PS(Problem Solving)/BOJ 2025. 4. 21.

• 

  [자료구조] 그래프(Graph) 그래프(Graph) 그래프는 연결되어있는 원소들 간의 관계를 표현한 자료구조이다. 일상 속에서의 대표적인 예시로는 지하철 노선도를 떠올릴 수 있다. 그래프 관련 용어 정점(vertex): 노드라고도 하며, 각 지점(위치)을 의미한다. 간선(edge): 정점들을 잇는 선을 의미한다. 사이클(cycle): 시작 정점과 종료 정점이 동일한 경우를 의미한다. 인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점을 의미한다. ex) A-B, C-E, C-F 정점의 차수(degree): 무방향 그래프에서 각 정점에서의 간선의 수를 의미한다. 그래프의 종류 1. 방향 그래프 간선에 방향이 존재하는 그래프 A와 B가 연결되어 있을 때, (A, B)와 (B, A)는 다르다. 2. 무방향 그래프 간선에.. 자료구조 2023. 10. 9.

• 

  [자료구조] 트리(Tree) 트리 트리는 노드로 이루어진 자료구조이며, 다음과 같은 형태를 갖는다. 예를 들어, 컴퓨터의 폴더 즉, 디렉토리를 예로 들 수 있다. 한 디렉 토리 안에는 여러 디렉토리가 들어있을 수 있고, 그 안에 또 여러 개의 파일들이 있을 수 있다. 트리 관련 용어 루트 노드(root node): 부모가 없는 노드로, 최상위 노드를 뜻한다. 위의 트리 예시에서 A에 해당한다. 단말 노드(leaf node): 자식이 없는 노드. C, D, F, G, H가 해당한다. 간선(edge): 각 노드를 연결하는 선(branch 라고도 한다.) 형제(sibling): 동일한 부모를 갖는 노드를 의미한다. C, D, E는 B라는 동일한 부모를 가졌으므로 형제이다. 차수(degree): 각 노드가 지닌 간선의 수이다. 트리의 차수.. 자료구조 2023. 10. 2.

• 

  [자료구조] 큐(Queue) 큐(Queue) 큐는 양 끝이 뚫린 파이프를 생각하면 된다. 한 쪽으로 데이터를 계속 해서 추가할 때, 다른 한 쪽으로 데이터를 빼내려 한다면 제일 처음 넣은 값부터 차례대로 나오게 된다. 즉, 처음 넣은 값이 처음 나오게 되는 First Input First Output(FIFO) 원리를 갖는다. 구현 큐의 기능은 다음과 같다. push: 큐에 데이터를 넣는다. pop 또는 poll: 큐에서 가장 앞에 있는 데이터를 빼고 반환한다. size: 큐에 들어있는 데이터의 갯수를 반환한다. isEmpty: 큐가 비어있는지를 반환한다. front 또는 peek: 큐의 가장 앞에 있는 원소를 반환한다. back: 큐의 맨 뒤에 있는 값을 반환해준다. 자바에는 존재하지 않는 내장함수로, c++에 존재한다. clas.. 자료구조 2023. 9. 30.

• 

  [자료구조] 스택(Stack) 스택이란? 스택은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 자료구조이다. 스택은 위와 같은 형태이다. 위의 빈 공간으로 데이터가 들어오고 나갈 수 있다. 위의 사진에서 2라는 데이터를 stack에 넣고, 값을 빼내고자 할 때 2부터 값이 나오는 것을 알 수 있다. 즉, 마지막으로 들어간 값이 처음으로 나온다는 Last Input First Output(LIFO) 형태를 따른다. 구현 스택의 기능은 다음과 같다. push: 스택에 값을 넣는다. pop: 스택에서 가장 위에 있는 값을 빼내고 이를 출력한다. size: 스택에 들어있는 원소의 개수를 출력한다. empty: 스택이 비어있는지 아닌지 출력한다. peek 또는 top: 스택에서 가장 위에 있는 값을 출력한다. 아래 코드로 기능들을 어떻게 구현했는지.. 자료구조 2023. 9. 26.

• 

  [자료구조] 리스트(2).연결리스트(LinkedList) 연결리스트(LinkedList) 순차리스트가 배열로 구성된 리스트라면, 연결리스트는 노드로 구성된 리스트이다. 노드는 두 가지의 정보를 가지고 있다. 데이터 다음 노드를 가리키는 포인터 즉, 다음과 같은 형태를 갖게 된다. 이때 pointer는 다음 노드의 주소를 값으로 갖고 있게 된다. 코틀린에서의 LinkedList를 열어 Node를 보면 다음과 같다. private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } 위에서 Node는 데이터와 다음 노드를 가리키는 포인터로 이루어져있다.. 자료구조 2023. 9. 26.

• 

  [자료구조] 리스트(1).순차리스트(ArrayList) 리스트란? 일상 생활 속 "위시 리스트", "버킷 리스트" 등 리스트가 담긴 단어를 종종 사용한다. 위시리스트는 자신이 원하는 것을 목록으로 작성해둔 것이고, 버킷 리스트는 자신이 해보고자 하는 것들을 목록으로 작성해둔 것이다. 자료구조의 리스트 또한 데이트의 목록을 의미한다. 리스트는 순차리스트(ArrayList)와 연결리스트(LinkedList) 2가지로 나뉘게 된다. 순차리스트(ArrayList) 순차리스트는 데이터들이 순서대로 메모리에 저장되는 자료구조이다. 즉, 논리적인 순서와 물리적인 순서가 동일한 구현 방식을 갖는다. 배열을 이용해 리스트를 구현한 것으로, 접근이 빠르다는 장점이 있다. 하지만 값을 추가하고 삭제하는데 있어서는 느리다는 단점 또한 존재한다. 삽입(add) ArrayList의 .. 자료구조 2023. 9. 25.

• 

  [자료구조] 배열(Array) 배열 배열이란 동일한 자료형을 연속적으로 저장하는 자료구조이다. 주소값을 확인해보면 4씩 증가하는 것을 확인할 수 있다. 이는 int형 데이터를 저장하기에 int의 크기인 4바이트씩 증가하는 것이다. 주소값은 각 자료형의 크기만큼 일정하게 증가하게 된다. 즉, char형 배열이라면 주소값이 1씩 증가하고, double형이라면 8씩 증가하게 된다. 배열의 선언 언어마다 배열의 생성 방법은 다르다. 여기서는 c++을 이용해서 해보도록 하겠다. #include using namespace std; int main() { int arr[5]; for(int i=0; i 자료구조 2023. 9. 23.