개발자 퉁이리

그래프 그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료구조다. 📈 정의 그래프는 정점과 간선들의 유한 집합으로 G = (V, E)로 표시할 수 있다. 여기서 정점은 노드라고도 불리고, 간선은 링크라고도 불린다. 여러 그래프가 존재하지만 오늘은 인접 행렬 C++ 구현에 대해 집중적으로 다뤄보려고 한다. 구현 (C++) getVertex(int i) getEdge(int i, int j) setEdge(int i, int j, int val) insertVertex(char name) void insertEdge(int u, int v) void display() isEmpty() isFull() 클래스 생성 class AdjMatGraph { private: int size; // 정점의 개수 ch..

트리 트리는 한 개 이상의 노드로 이루어진, 나무를 거꾸로 엎어놓은 듯한 모양의 비선형 자료구조다. 🎄 트리의 종류 트리의 종류는 여러 가지가 있을 수 있다. 그중에서 가장 일반적인 트리로 일반 트리와 이진트리가 있다. 🎆 일반 트리 일반 트리는 위 사진과 같이 생겼다. 일반 트리에서 노드는 0개부터 최대 N개의 노드를 가질 수 있다. (N은 제한이 없다) 🎆 이진트리 이진트리는 위 사진과 같이 생겼다. 이진트리에서 이진은 0과 1을 나타내고, 부모 노드가 자식 노드를 최대 2개까지만 가질 수 있다. 구현 (C++) insert() search() print() 클래스 생성 class BSTNode { public: int Key; BSTNode *Left; BSTNode *Right; BSTNode *..

https://www.acmicpc.net/problem/17608 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 자료 구조 스택 ⊙ 문제 접근 과정 크기 비교만 해주면 된다. 역으로 해서 나보다 크기가 크면 갱신해주고, count를 세주자. count의 초기값은 1이다. 맨 앞에 있는 건 무조건 보이기 때문이다. ⊙ 문제 풀이 import sys input = sys.stdin.readline N = int(input()) stack = [] fo..

큐 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조로 선입선출 특성을 가진다. 구조상으로 큐가 스택과 다른 점이 있다. 스택의 경우, 삽입과 삭제가 같은 쪽에서만 일어난다. 그렇지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다. ✅ 큐에서 삽입이 일어나는 곳을 후단(rear)이라 하고 삭제가 일어나는 곳을 전단(front)이라고 한다. 📌 큐 연산 enQueue(int value) : 큐 후단(rear)에 값을 추가 deQueue() : 큐 전단(front)의 값을 제거 isFull() : 큐가 가득 찼는지 확인 isEmpty() : 큐가 비어있는지 확인 displayQueue() : 큐에 있는 요소들 출력 클래스 생성 #define MAX_SIZE 5 class Queue {..

스택 스택은 컴퓨터에서 믿을 수 없을 정도로 많이 사용되는 자료구조이다. 후입선출(LIFO : Last In First Out) 형태로 나중에 들어온 것이 가장 먼저 나가는 형태를 띈다. 직역 그대로 데이터를 순서대로 쌓는 자료구조라고 생각하면 된다. 스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. 📌 스택 상단 : 스택에서 입출력이 이루어지는 부분 스택 하단 : 반대쪽인 바닥 부분 요소 : 스택에 저장되는 것 공백 스택 : 스택에 요소가 하나도 없을 때 스택의 연산 push() : 스택 맨 위에 item을 추가 pop() : 스택의 맨 위에 원소를 제거해서 반환 peek() : 스택의 맨 위의 요소를 제거하지 않고 반환 isFull() : 스택이 꽉 찼는지 확인 i..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 스택 ⊙ 문제 접근 과정 힌트를 보고 이해했다. 만약 문제가 이해하기 힘들면 힌트를 바로 보자. 힌트: 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, pu..

연결 리스트 연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 연결 리스트 구조 연결 리스트는 노드들의 집합이다. 노드는 데이터 필드와 링크 필드로 구성되어 있다. 📊 데이터 필드 데이터 필드에는 저장하고 싶은 데이터가 들어간다. 위 그림에서 하얀색 배경인 부분이 데이터 필드이다. 📎 링크 필드 링크 필드에는 다른 노드를 가리키는 포인터가 저장된다. 위 그림에서는 노란색 배경인 부분이 링크 필드이다. 연결 리스트에서는 연결 리스트의 첫 번째 노드를 알아야 만이 전체 노드에 접근할 수 있다. 따라서 연결 리스트마다 첫 번째 노드를 가리키고 있는 변수가 필요한데 이것을 헤드 포인터라 한다. 그리고 마지막 노드의 링크 필드는 NULL로 설정되는..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 스택 ⊙ 문제 접근 과정 stack pair를 이용하여 index와 value를 동시에 push 해주었다. 가장 위에 있는 값의 value는 st.top().second이고 그것에 대한 index는 st.top().first이다. 현재 입력 값이랑 기존에 stack에 저장되어 있는 값이랑 비교 후, 신호 수신 가능( 기존에 ..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 그리디 알고리즘 우선순위 큐 ⊙ 문제 접근 과정 결론부터 말하면 가장 작은 두 값을 더하고 두 장 모두에 덮어쓴 값이 최솟값이다. 4 2 3 1, 총 4장의 카드가 있다. 우선 크기 순으로 정렬해보자. 1 2 3 4 덮어썼을 때 가장 적게 값이 증가해야 한다. 그러려면 두 값 모두 작아야 ..

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 그리디 알고리즘 분리 집합 ⊙ 문제 접근 과정 문제 이해가 너무 안 되었다. 진짜; 간단하게 정리하자면 게이트 수 G, 비행기 수 P가 있다. 그리고 G개의 게이트에 비행기가 한 대씩 도킹할 수 있고 꽉 차면 공항 폐쇄. g의 값을 비교하여 채운다. 채운다면 cnt 값을 올려주고 공항 폐쇄 o..