그래프 그래프는 객체 사이의 연결 관계를 표현할 수 있는 자료구조다. 📈 정의 그래프는 정점과 간선들의 유한 집합으로 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/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://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 수열의 중복을 막기 위해 set을 사용했다. vector에 수열의 값을 저장을 M개만큼 저장하고 그 값들을 set에 저장한다. 이번 문제의 point! 이번 9탄에서는 방문처리인 visited을 사용하지 않으면 시간 초과가 발생한다. N과 M 9탄에서 드디어 방문 표시를 해야 하는 이유를 몸소 확인할 수 있..
https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 백트래킹 ⊙ 문제 접근 과정 18번째 줄만 계속 수정해주면 N과 M 시리즈가 풀린다! 다음 문제가 그렇다. 해당 줄을 코드에 주석으로 ★ 표시해놨다. 값을 입력받고 정렬한다. 그 값을 새로운 배열에 저장하고, dfs를 반복한다. 그러다가 M값에 도착하면 새로운 배열에 넣은 값을 출력해준다. 자세한 건 코드를 통해 확인하자!! ⊙..
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/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 플로이드-와샬 ⊙ 문제 접근 과정 입력받을 때, 해당 경로에 대해 1이라는 값을 표시해준다. 플로이드 와샬로 검사하여 만약 거쳐갈 수 있다면 또다시 1 표시 1 표시가 둘 다 안 되어 있다면 count up! N까지 다 돌고 count 출력 해준 뒤, count를 다시 0으로 초기화 다음 번호, 마지..
https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 같은 거리의 집을 다 탐색하고도 탐색할 집이 남아있다면 거리를 1 늘리고 다시 탐색한다. set을 이용하여 방문을 했는지 안 했는지 판별했다. ⊙ 문제 풀이 #include #include #include using namespace std; ty..
https://www.acmicpc.net/problem/10817 10817번: 세 수 첫째 줄에 세 정수 A, B, C가 공백으로 구분되어 주어진다. (1 ≤ A, B, C ≤ 100) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 구현 ⊙ 문제 접근 과정 배열에 값을 입력받는다. 배열 오름차순 정렬 뒤에서 2번째 값 출력(여기서는 index 0, 1, 2 총 3개이니 index 1 출력) ⊙ 문제 풀이 #include #include using namespace std; int arr[3]; int main() { for(int i=0;i> arr[i]; sort(arr,arr+3); //오름차순 정렬 cout
https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 수학 구현 ⊙ 문제 접근 과정 크기 순으로 정렬 후, 가장 맨 앞의 작은 값과 가장 마지막의 큰 값을 출력해주었다. ⊙ 문제 풀이 #include #include #include using namespace std; int N; vector v; int main() { cin >> N; for(int ..
- Total
- Today
- Yesterday
- Web
- Python
- C++
- 연습문제
- 구현
- 정리
- java
- 해답
- 운영체제
- 문자열
- 쉽게 배우는 자바 프로그래밍
- 쉽게배우는자바프로그래밍
- 답
- 자바
- 풀이
- 프로그래머스
- 정렬
- CPP
- 쉽게배우는
- 알고리즘
- JS
- 우종정
- BFS
- 파이썬
- 그리디
- py
- 자바스크립트
- OS
- 정답
- 백준
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |