코젤브

https://www.acmicpc.net/problem/10951 전체 코드// class1// 백준 10951번 : A+B-4#include using namespace std;int main(){ int A, B; // 방법 1 : scanf와 EOF 활용 while (scanf("%d %d", &A, &B) != EOF) { printf("%d\n", A + B); } // 방법 2 : scanf함수의 리턴값 활용 while (scanf("%d %d", &A, &B) == 2) // 읽어드린 입력 개수 반환 printf("%d\n", A + B); // 방법 3 : cin과 eof() 사용 while (!(cin >> A >> B..

동적계획법(Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 접근하는 방법이다. 부분 문제가 반복되고 최적의 원칙을 만족하는 문제를 일반적인 방법에 비해 적은 시간 내에 풀 때 사용한다. ex) 피보나치, 정수삼각형, 이항 계수 상향식 해결법(Bottom-Up 방식) 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식 최적의 원칙 : 어떤 문제의 입력에 대한 최적해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 적용된다고 한다. 백준 2579번: 계단 오르기 #include #define MAX 301 using namespace std; int main() { int n; int DP[301];..

Backtracking : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. (최적화 문제와 결정 문제를 푸는 방법) : 모든 경우가 아닌 제약 조건에 맞는 후보해에 대해서만 탐색한다. 즉, 불필요한 탐색을 하지 않고 이전 단계로 돌아와 다른 후보해를 탐색한다. 해를 찾다가, 지금의 경로가 해가 될 것 같지 않으면, 그 경로로 가지 않고 바로 되돌아간다. (즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적) 이를 가지치기라고 하는데, 불필요한 부분은 빼고 최대한 올바른 쪽으로 간다는 의미이다. 일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 ..

백준 11047번 그리디 알고리즘을 통해 해결할 수 있는 간단한 문제이다. 특히 동전의 단위가 배수이므로, 큰 단위의 동전부터 나눠주고, 차례로 진행하면 된다. #include using namespace std; int main() { int n, k; int sum = 0; int a[11]; cin >> n >> k; for (int i = 0; i > a[i]; for (int i = n - 1; i >= 0; i--) { sum += k / a[i]; k = k % a[i]; } cout

백준 2750번 문제를 합병 정렬과 퀵 정렬로 각각 풀어보자. * 재귀 알고리즘: 큰 문제를 작은 문제로 쪼개고 작은 문제의 해답을 return하면서 큰 문제의 답에 접근하는 알고리즘 백준 2750번: 수 정렬하기 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1. 합병 정렬 : 리스트를 분할하여 정렬하고 합병 // 합병 정렬 알고리즘 코드 void merge(int list[], int left, int mid, int right) { int i, ..

백준 1991번 문제: 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 3주차 트리 자료구조 교육에서 배운 것처럼, 구조체를 통해 이진 트리를 구현하고 각 정의에 맞게 코드를 구성하면 된다. 전위 순위 : 루트 노드 방문 -> 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문 중위 순위 : 왼쪽 서브트리 방문 -> 루트 노드 방문 -> 오른쪽 서브트리 방문 후위 순위 : 왼쪽 서브트리 방문 -> 오른쪽 서브트리 방문 -> 루트..

그래프 "정점(V, Vertex node)과 그 정점을 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조" 그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다. 정점(V): 어떤 자료나 개념을 표현하는 정점(노드) 간선(E): 정점을 연결 그래프 G(V, E): 정점들의 집합 V와 간선들의 집합 E로 구성된 그래프 경로: 한 정점인 시작점에서 다른 정점인 도착점으로 가는 간선이 연속되게 연결된 것 순환: 경로의 시작점과 도착점이 동일 인접(Adjacent): 간선 (U, V)에서, 두 정점 U와 V는 인접한다. 부속(Incident): 간선 (U, V)는 정점 U, 정점 V에 부속된다. 그래프의 종류 방향과 가중치에 따라 그래프의 종류를 구분할 수 있다. 그래프: 구현방법 ..

스택(stack) 후입선출(LIFO: Last-In First-Out) :가장 최근에 들어온 데이터가 가장 위에 있게 되고, 또 가장 먼저 나간다. 연산 create(size) : 크기가 size인 스택을 생성함 push(element) : 스택에 새로운 원소를 삽입함 top을 먼저 증가시키고 그 위치에 원소를 삽입함 is_full() : 스택이 가득 채워져 있는지 검사함 가득 채워져 있으면 true, 하나라도 비어 있다면 false를 return pop() : 스택에서 원소 하나를 없앰 top이 가리키는 원소를 가져오고 top을 하나 감소시킴 is_empty() : 스택이 비어 있는지 검사함 스택이 비어 있으면 true, 비어 있지 않으면 false를 return 배열로 구현한 소스코드 #include..