c++60

• 

  백준-2468 안전영역 1. 안전영역(DFS) 이 문제 또한 DFS를 활용하여 깊이 탐색을 하는 문제였다. 앞서 문제와 한 가지 다른점은 앞서 유기농 배추 문제는 모든 배열의 값이 0아니면 1이 들어가서 바로 dfs를 탐색할 수 있었던 반면에 이 문제에서는 각 배열마다 다른 높이가 존재해서 높이를 비교하면서 가야한다는 점이 있었다. 하지만 메모리 적으로 여유가 있어 나는 먼저 침수 높이d와 비교해 더 낮은 지대를 1의 값으로 갖는 비교 배열을 만들어준 후 앞선 유기농 배추 문제와 같이 dfs를 실행해주었다. dfs함수에서는 우선적으로 방문 배열을 1로 표시해주어야 하는 것이 중요하다는 것을 명심하자. 다음은 내가 문제를 푼 코드이다. #include #include #include using namespace std; int .. c++/알고리즘 2022. 3. 29.

• 

  백준-1012번 - 유기농 배추 내가 백준 문제를 풀면서 느낀 점은 채점을 할 때 맞게 하고 싶다면 문제에서 변수들을 잘 파악해야한다는 것이다. 우선 문제를 살펴보면 테스트 케이스를 의미하는 변수 T가 존재한다. 또한 배추를 심은 배추밭의 가로길이 M, 세로 길이 N, 배추를 심은 개수 K가 존재한다. 또한 그 후 배추의 위치를 나타내는 변수론느 x, y가 존재한다. 그럼 일단 6개의 변수가 존재하는 것이다. 그 후 반복문 안에서 다음 배열 인덱스를 담아 줄 ny, nx변수와 최종 개수를 ret할 ret 변수까지 9개가 존재한다. 또한 이 문제는 깊이 탐색 문제이므로 배추의 위치를 표현할 map과 그 배열과 같은 크기의 방문 여부 배열이 필요하다. #include #include #include using namespace std; i.. c++/알고리즘 2022. 3. 29.

• 

  백준2178번-미로BFS 이 문제는 가중치가 같은 맵 안에서의 최단 경로를 찾는 문제이다. 이는 자료구조 queue를 사용하며 풀면 되는데 나의 코드는 다음과 같다. #include #include #include #include using namespace std; int n, m, y,x; int max = 104; int a[104][104]; int visited[104][104]; // 입력 배열과 방문 배열 int dy[4] = {-1,0,1,0}; int dx[4] = {0,1,0,-1}; int main() { cin >> n; cin >> m; for(int i = 0; i >a[i][j]; } }//입력 만들기 queue q; // q.. c++/알고리즘 2022. 3. 28.

• 

  shell sort c++ #include #include #include #define MAX 30 #define MAX1 100000 #define MAX2 500000 #define MAX3 1000000 #define MAX4 5000000 #define MAX5 10000000 using namespace std; void shell_sort3h1(int a[], int n) { /* h = 3*h + 1 이용 */ int i, j, k, h, v; for (h = 1; h 0; h /= 3)// h의 값을 줄여가면서 계산 { for (i = h; i = h && a[j - h] > v) { a[j] = a[j-h]; j.. c++/알고리즘 2022. 3. 23.

• 

  백준 9996 #include #include #include using namespace std; int n; string pattern; string filename; string pre; string back; int main() { cin >> n; cin >> pattern; for(int i = 0; i > filename; if(filename.substr(0, pre.size()) .. c++/알고리즘 2022. 3. 19.

• 

  백준 1159 //백준 1159번 #include #include using namespace std; int cnt[26]; int n; string player; string ret; int main() { cout n; for(int i= 0; i = 5) { ret += i+ 'a'; } } if(ret.size()) cout c++/알고리즘 2022. 3. 18.

• c++ vector 1. 벡터란? 코딩테스트를 준비하면서 나는 c++를 사용하기로 했다. 이 때 가장 중요하게 생각했던 것이 데이터를 담는 라이브러리 및 자료형인데 배열은 처리하는 속도가 빠른 반면 크기가 한정되어 있어 처음부터 크기가 정해져있지 않은 문제에서는 문제가 발생할 수 있다. 벡터를 선언하는 것은 간단하다. 우선 vector 라이브러리를 추가해준다. #include 벡터를 사용할 때 크기 변경 가능 o 중간 삽입, 삭제 용이 X 순차 접근 가능 o 랜덤 접근 가능 o 2. 벡터의 생성 및 초기화 //1차원 벡터 vector vec1; vector vec2; vector vec3; //1차원 사용자 정의형 벡터 struct user { int id; string name; }; // 사용자 정의형 vector ve.. c++ 2022. 3. 16.

• 

  c++ 행렬 곱셈 1. 문제 - n^3(Cubic complexity)를 만족하는 3중 for루프 곱(2차 행렬 a, b, c 곱셈) - Cubic complextiy 알고리즘의 경우 n=10, 50, 100, 150, 200 을 사용하여 결과 출력 입력 행렬의 크기가 달라져야하기 때문에 크기가 가변적인 벡터를 사용해서 할 것임 int SIZE = 200; vector solution(vector arr1, vector arr2) { vector ans(arr1.size(), vector(arr2[0].size(), 0));//2차원 배열 선언, 0으로 초기화 // arr1의 i행, arr2의 j열을 곱한다 // 인덱스 이동은 k for (int i = 0; i < SIZE; i++) { for (int j = 0; j .. c++/알고리즘 2022. 3. 16.

• 피보나치 수열 #include #include #include using namespace std; int Fibonacci(int num) { if (num == 0) return 0; else if (num == 1)return 1; else return (Fibonacci(num - 1) + Fibonacci(num - 2)); } int SIZE = 30; void main() { // IO 속도 향상 ios_base::sync_with_stdio(false); cin.tie(NULL); clock_t start, finish; double duration; start = clock(); Fibonacci(SIZE); finish = clock(); duration = (double)(finish - start.. c++/알고리즘 2022. 3. 16.

• 

  heap sort 1. heap sort heap sort는 완전 이진 트리의 형태를 만족한다. 완전 이진트리란 tree의 leaf node들의 층수가 모두 같은 트리를 의미한다. 위의 그림에서 볼 수 있듯이 같은 층이 완전히 차기 전까지는 leaf node가 새로운 층으로 내려가지 않는다. 나는 최대 힙을 구현해볼 것이다. 언어는 c++를 사용하였다. 2. 구현을 위해 생각해야 하는 것 1. 노드가 가질 정보 각 노드들은 데이터를 가질 부분, 노드의 왼쪽 아래 층의 인덱스에 대한 정보, 노드의 오른쪽 아래 층의 인덱스에 대한 정보 총 3가지의 정보를 가져야한다. struct node // 데이터를 입력받을 노드 { int data; // 데이터 struct node* left; // 왼쪽 노드 struct node* r.. c++ 2022. 3. 15.

• DoubleLinkedList 예전 자료구조 시간에 했던 과제들을 복기하며 다시 자료구조와 알고리즘에 대한 이해를 남겨보기로 했다. 그 중 자료구조에서는 Double Linked List라는 구조가 존재한다. Double Linked List란 양방향으로 연결 되어 있는 리스트로써 각 노드들이 양 방향으로 이어지는 구조를 가진다. 그러면 우리는 이 구조에서 몇 가지의 데이터를 신경써야할까 내가 프로그래밍을 하면서 느낀 점은 프로그래밍은 결국 데이터의 관리, 엔터티의 속성의 관리를 하는 일이다. 노드들이 양방향으로 연결되어 있으니 우리는 우선 노드라는 타입을 만들어야한다. #ifndef DLINKEDLIST_H #define DLINKEDLiST_H #include using namespace std; // 12171800 심정호 ty.. c++ 2022. 3. 13.

• 자료구조 stack을 이용한 문제 풀이 1(postfix) 우리는 후위표기식에 대해 알아볼 것이다. 후위 표기식이란 컴퓨터가 알아보기 쉽게 하는 표기 방식으로 우리가 흔히 연산을 표시하는 표시 방법인 중위 표기식과는 사뭇 다르게 생겼다. 예를 들어 중위 표기식에서 3+5 와 같은 식을 후위 표기식으로 표시하게 되면 3,5+와 같이 표기된다. 좀 더 복잡한 중위 표기식 예를 들면 A+B-C*D와 같은 경우에서는 연산 우선 순위가 *가 가장 높으므로 이것부터 처리해준다. A+B-CD* -> AB+-CD*>AB+CD*- 와 같이 변하게 된다. 이것이 후위 표기법이다. 몇 가지의 예시를 더 살펴보겠다. 1. A+B*C -> A+BC* 2. A*B-C -> AB*-C -> AB*C- 이와 같이 컴퓨터는 순서대로 읽으므로 컴퓨터가 읽기 쉽도록 표기법을 수정하는 것이다. ​.. c++ 2021. 6. 18.