개발자 퉁이리

그래프 그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료구조다. 📈 정의 그래프는 정점과 간선들의 유한 집합으로 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 *..

해시 해싱 (hashing) 해시 함수 (hash function) 해시 테이블 (hash table) 구현 (C++) 🧐 해싱 (hashing) 해싱은 유사한 개체 그룹에서 특정 개체를 고유하게 식별하는 데 사용되는 기술로, 키(key)에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항복에 접근한다. 위 그림은 키(key)를 이용하여 해시 함수를 통해 항목에 접근하는 과정을 나타낸 것이다. 위와 같은 탐색 과정을 해싱(hashing)이라고 한다. 🧐 해시 함수 (hash function) 해시 함수는 임의의 데이터를 고정된 길이로 매핑하는 함수를 말한다. 데이터에 해싱 작업이 적용되면 원래 데이터를 다시 가져올 수 없으므로 단방향 프로세스라고도 한다. 또한 모든 해시 출력은 ..

큐 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조로 선입선출 특성을 가진다. 구조상으로 큐가 스택과 다른 점이 있다. 스택의 경우, 삽입과 삭제가 같은 쪽에서만 일어난다. 그렇지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다. ✅ 큐에서 삽입이 일어나는 곳을 후단(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..

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

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 브루트포스 알고리즘 백트래킹 ⊙ 문제 접근 과정 백트래킹 문제였는데 재미있었다. 반복문 i는 4번 돌린다. 범위는 0부터 3으로 각각 0,1,2,3은 순서대로 +, -, *, /이다. 사칙 연산에 대해 값을 모두 탐색하였을 때, 그 값이랑 현재 값이랑 비교하여 큰 값은 maxValu..

https://programmers.co.kr/learn/courses/30/lessons/83201 코딩테스트 연습 - 2주차 [[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD" programmers.co.kr ⊙ 문제 ⊙ 제한사항 ⊙ 입출력 예 ⊙ 입출력 예 설명 ⊙ 문제 접근 과정 먼저 자기 자신을 채점한 점수를 빼고 push 해준다. 그리고 받은 점수 중에서 가장 큰 값과 가장 작은 값을 자기 자신이 채점한 점수와 비교한다. 만약 유일한 최고점, 유일한 최저점이 아니면 push 하고 유일한 최고점과 유일..

https://www.acmicpc.net/problem/2490 2490번: 윷놀이 우리나라 고유의 윷놀이는 네 개의 윷짝을 던져서 배(0)와 등(1)이 나오는 숫자를 세어 도, 개, 걸, 윷, 모를 결정한다. 네 개 윷짝을 던져서 나온 각 윷짝의 배 혹은 등 정보가 주어질 때 도(배 한 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 ⊙ 문제 접근 과정 윷 한번 던질 때마다 초기화다. 즉, 독립이란 소리! 입력받은 숫자들을 다 더해 각자의 케이스(도, 개, 걸, 윷, 모) 별로 정리한다면 쉽게 풀 수 있다. 정말 오랜만에 switch문을 사용해 풀어봤다. if문을 사용해도 상관없다. ⊙ 문제 풀이 #include using namespace std; in..

https://www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M> N >> M >> J; int cnt=0; int start=1, end = M; while(J--) { int x; cin >> x; bool flag=true; while(flag) { if(start