https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io Spanning Tree : 그래프 내의 모든 정점을 포함하는 트리 최소 연결 부분 그래프이므로 간선의 수가 가장 적다. DFS와 BFS를 사용해서 정점들을 찾기 위해 사용된 간선을 모은다. 위 그림처럼, n 개의 정점이 존재할 때 (n-1)개의 간선이 연결되어있다. 최소 신장 트리(MST : Minimum Spanning Tree)란, 간선의 가중치가 다를 때 최소 비용의 Spanni..
한 주간 BFS와 DFS문제를 풀어봤었는데, 개념 자체가 어렵다기 보단 문제에 맞게 응용하는 것이 너무너무 어려웠다. 개념을 한번 더 정리하고 코드를 분석해보려 한다! BFS Breadth First Search (너비 우선 탐색) : 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 #include #include #include using namespace std; int number = 9; bool visit[9]; vector a[10]; // vector 자료형이 열 개, 즉 이차원 배열이라고 보면 됨 void bfs(int start) { queue q; q.push(start); // 시작 노드 push visit[start] = true; while (!q.empty()) { in..
학생회 행사 참여 인원을 조사하다가, 위와 같이 복수 응답으로 날짜를 투표 받았고 이렇게 50개가 넘는 응답을 받아 손수 정리하는 것의 한계를 느꼈다. 프로그램 개발해서 \n을 기준으로 응답자별로 응답한 날짜 객체를 분류해 배열에 넣고, 문자열 슬라이싱으로 날짜 정보를 추출해 해당 날짜를 선택한 사람의 정보를 입력하여, Map으로 번호와 이름을 매칭시켜 이름을 출력하는 프로그램을 개발하였다. 이렇게 해서 손쉽게 정리를 할 수 있었다. 아래는 소스코드이다. #include #include #include #include #include #define MAX_LENGTH 45 #define _CRT_SECURE_NO_WARNINGS #pragma warning 4996 #define n 35 // 참여한 학..
그리디 알고리즘(Greedy Algorithm)이란? 매 단계에서 '가장 좋아보이는' 해답을 선택하는 알고리즘이다. 지역적인 최적의 해결 방법을 통해 전역적인 최적의 해결 방법을 찾는 것이다. 아래는 그리디 알고리즘으로 해결할 수 있는 대표적인 두 문제이다. 1) 최단 작업 우선 스케일링 예제를 통해 알아보자. 1. 은행 창구에 줄을 서서 사람들이 차례를 기다리고 있다. 각자의 업무를 보는 데 걸리는 시간은 각자 다르다. 2. 대기열에 기다리고 있는 사람들은 평균 대기 시간이 최소화 되도록 순서를 재배치하는 것에 동의했다. 3. 평균 대기 시간이 최소가 되는 순서 배치를 구하시오. #include #include #include #include using namespace std; template aut..
백준 9934번 : 완전 이진 트리 재귀 호출을 사용해서 left와 right값을 업데이트 해 center값을 정하는 과정으로 생각. //9934 완전 이진 트리 #include #include using namespace std; void findCenter(int * arr, int left, int right) { int center = (left + right) / 2; if (left == right) { cout k; int size_k = pow(2, k) - 1; int* arr = new int[size_k]; for (int i = 0; i > arr[i]; } // 1 6 4 3 5 2 7 findCenter(arr, 0, size_k - 1);..
정답률 높은 문제라 쉽게 생각했는데 생각보다 복잡한 문제였다 ;-; 처음에는 0이 나온 인덱스의 앞의 것만 0으로 바꿔주면 된다고 생각했는데, 0이 나온 갯수만큼 최근의 나온 숫자(0과 인접하지 않더라도)를 모두 없애줘야 했고 #include using namespace std; // 3 0 4 0 // 0 // 1 3 5 4 0 0 7 0 0 6 // 7 int current = -1; void pop(int *arr, int cur) { if (current == -1) { } else { arr[current] = 0; } } void sol(int *arr) { int length = _msize(arr) / sizeof(arr[0]); for (int i = 0; i < length; i++) ..
문제 해결은 간단하다. 인덱스를 신경쓰지 말고 Pi배열을 정렬해 새 배열에다 밑의 주석과 같이 값을 정해주면 된다. C++문제 해결 코드이다. #include #include using namespace std; /* * i는 인덱스, Pi는 해당 인덱스의 value이다 * ! 사실상 '누구' 즉 인덱스는 상관이 없다 * 정렬해서 * 새 배열 만들어서 * 맨 처음 인덱스는 그대로 * 두번째는 처음 + 두번째 * 세번쟤는 처음 + 두번째 + 세번째 */ int main() { int N; cin >> N; //사람 수를 담을 배열 int list[1000] = { NULL }; for (int i = 0; i > list[i]; } // list[1000] = { 3, 1, ..
처음엔 테이프를 이어붙이는 동작을 어떻게 프로그램에서 표현할 수 있을까를 고민했다. '0.5'를 표현해야 한다는 고정관념에 사로잡혀 한참을 고민했다. 그러다 배열의 한 메모리를 '구멍' 자체로 생각하니 0.5 같은 건 생각할 필요가 없어졌고, 배열과 파이프를 동일시하여 생각하기로 하였다. 구현 알고리즘과 의사코드는 다음과 같다. 1. 파이프 배열을 생성해 구멍이 생긴 부분의 값을 true로 바꾸어준다. 2. for문을 배열의 처음부터 순차적으로 돌며 맨 처음 true인 부분을 만나면 먼저 false처리 해주고, 그 부분에서 테이프의 길이만큼의 범위에서 true 인 부분이 있는지 이중 for문을 통해 관찰한다. 3. 만약 이중 for문에서 물이 새는 부분이 또 있으면 그 부분을 false 처리하여 중복 동..
역시 '최소한' 즉 최적의 답을 찾는 그리디 알고리즘 문제, 반례를 찾지 못하는 틀린 코드만 계속 만들어 내었던 문제인 것 같다. 먼저 생각한 알고리즘은 다음과 같다. // 레벨 점수를 list에 '반대로' 담아 레벨이 높은 순대로 정렬한다. while(비교할 하위 레벨이 NULL이 아닌 경우 if(list[i] > list[i+1]) 넘어가 else count+=(list[i + 1] - list[i] + 1) list[i+1] = list[i] - 1; i++; 이런 의사 코드로 만들어진 코드는 다음과 같다. int main() { int count = 0; int list[100] = { NULL }; int N; cin >> N; //4 for (int i = 0; i < N;i++) { cin ..
