이지코딩

학부생 수업의 조교를 맡게 되었다. 일거리가 늘어났지만 나 또한 학부생때 들었던 수업이라 열심히 하려고 한다. 매주 학부생들은 한 챕터가 끝날때마다 수업에 대한 퀴즈를 풀고, 조교에게 메일로 퀴즈결과를 전송한다. 조교의 업무 중 하나는 매주 메일을 확인하여 제출을 완료 한 학생을 엑셀에 표시하는 것. 매우 단순한 일이다. 다만 문제는 매주 174개의 메일이 온다는것.... 메일 내용에 있는 챕터 번호와 학번을 일일히 확인하고 엑셀에 해당 학번을 검색해서 "o"를 표시하면 되는데.... 20개쯤 하다보니 현타가 왔다. ... 내가 지금 뭘 하는거지 .... 공부할 것도 산더미 인데... 이렇게 시간낭비를 할수는 없다. 사실 귀찮다... 인터넷에서 이런말을 봤다. 파이썬과 구글만 있으면 못할게 없다고. 나는..

중복을 허용하게 되므로 N과 M(1) 에서 중복방지를 위해 존재했던 chk를 제거하여 방문 표시를 하지 않으면 된다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include #include #include #include #include #include #include using namespace std; void DFS(vector v, vector arr, int cnt, int n, int m, int x) { arr.push_back(v[x]); // 값 넣어줌 cnt++; // 갯수 계산 if (cnt == m)..

이 전 문제에서 오름차순 조건이 추가되었다. 이런 저런 조건 필요 없이 이미 벡터에 들어있는 마지막 값보다 큰 값만 추가하면 자연히 오름차순이 만족된다. 또한, 처음 DFS 시작시 벡터의 마지막 값을 참조할 수 없으므로 그것 또한 예외처리를 해주면 된다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #include #include #include #include #include #include #include using namespace std; void DFS(vector v, vector arr,..

기본적인 백트래킹 문제이다. c++의 endl 때문에 한번 시간초과가 나긴 했다..... 백트래킹의 경우 트리로 생각하면 간단하게 해결 할 수 있다. (4,2)가 입력일때, 루트노드가 1이라면 자식노드는 1을 제외한 2,3,4 가 되고, 트리의 계층이 2층 이므로 모두 탐색을 완료한 것이다. DFS를 사용하여 계층만 계산해주면 쉽게 풀 수 있다. 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include #include #include #include #include #include using names..

문제를 읽어보면 알겠지만 논리적으로는 굉장히 쉬운 문제이다. 다만 입력을 문자열로 받기에 그 부분을 처리하는데 있어 조금 귀찮을 뿐이다. 예를들어 55-50+40 이 주어질 경우, 가장 작은 값을 만들기 위한 괄호는 55-(50+40) 이다. 즉, 55-50-40 으로 만들면 된다는 것이다. 이를 위해 음수 이후의 덧셈을 모두 뺄셈 처리를 해주면 해결된다. 위 처럼 계산을 해주기 위해 문자열을 적절히 처리하여 배열에 {55, -50, 40} 으로 넣어주었다. 위 배열처럼 만들기 위해 아스키 코드 값을 기준으로 숫자를 분류하였고, atoi() 를 사용하여 정수값으로 변환 시켰다. 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..

문제를 읽자마자 그냥 오름차순으로 정렬한 후에 더하는 것만 하면 된다고 생각했다. 하지만 실버3인데 이렇게 그냥 가는 거라고...? 라는 생각을 하면 그냥 제출 해버렸고..... 맞아 버렸다... 이 문제는 그리디알고리즘 보다는 그냥 정렬 알고리즘 여러개 공부할때 사용하는 문제 인것 같다. 단순히 생각하면 내 앞사람까지 걸린 시간이 제일 적으면 된다. 그러기 위해서는 내 앞사람이 나보다 인출하는 시간이 적으면 된다. 그러므로 오름차순 정렬을 한 후, 각 인덱스 별로 더하기를 진행하면 끝! 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 #include #include #include #include #include #i..

그리디 알고리즘을 사용하는 문제였다. 처음에는 무작정 회의 시간이 가장 짧은것 순으로 붙이면 되겠다 라고 생각 했다. 하지만, 순서가 정해져야 하므로 말도 안되는 방법이다. 이 문제의 가장 중요한 부분은 "가장 먼저 끝나는 회의"의 순서를 찾아야 한다는 것이다. 먼저 끝나는 회의를 찾고, 끝나는 시간 이후에 가장 먼저 시작하는 회의를 찾는 것을 반복하면 이 문제를 해결할 수 있다. 만약 먼저 끝나는 회의의 정렬을 위해 퀵소트를 사용한다면, 워스트 케이스의 경우 O(N^2)의 시간 복잡도를 가지게 되므로 시간이 부족하게 된다. 이때문에 C++ 라이브러리에 있는 sort()를 사용하였다. 개인적으로 틀린 부분은 회의의 시작시간과 끝나는 시간이 같은 경우의 예외 사항때문에 많이 틀렸다. (5,8) (8,8) ..

BFS를 처음 배웠을때는 무작정 돌리면 끝나는 건줄 알았는데... 이걸 또 응용하는 문제들이 생겨버릴줄을 몰랐다. 문제의 핵심은 "외부 공기와 첩촉한 부분"만 시간이 지날수록 없어진다는 것이다. 위 처럼 중간에 구멍이 있을 경우에는 외부공기와 차단되어있기에 구멍과 맞닿아 있는 부분은 녹아내리지 않는다. 그냥 [0][0] 위치부터 외부 공기를 계속 BFS를 통해 점령해가면서 접촉하는 치즈를 시간별로 녹이는 방법이 정석적일 수도 있으나, 치즈의 모양이 복잡할 경우 시간 초과가 날 수도 있을것 같아 새로운 방식으로 접근하였다. 먼저, [0][0]을 시작으로 BFS를 시작하여 외부 공기와 맞닿는 치즈의 테두리를 찾아낸다. 이후에는 찾아낸 테두리를 외부 공기라고 생각하고, BFS를 통해 또 맞닿아 있는 치즈를 찾..