궤도

문제 풀이 myunji.tistory.com/251 [백준] 2630번 : 색종이 만들기 문제 풀이 전형적인 분할 정복 문제다. divide and conquer라고 부르는데 문제의 수를 쪼개가며 푸는 것이다. 문제를 쪼갤 때는 보통 재귀함수를 많이 사용한다. 이 문제도 색종이의 색이 모두 같을 myunji.tistory.com 이 문제와 유사한 문제이다. 분할을 하는 지점에서 괄호를 입력한다는 걸 깨달으면 문제 자체는 금방 풀린다. 소스코드 #include using namespace std; int video[64][64]; bool isSame(int size, int row, int col, int color) { for (int i = row; i < (size + row); i++) { for..

문제 풀이 전형적인 분할 정복 문제다. divide and conquer라고 부르는데 문제의 수를 쪼개가며 푸는 것이다. 문제를 쪼갤 때는 보통 재귀함수를 많이 사용한다. 이 문제도 색종이의 색이 모두 같을 때까지 색종이를 4등분하며 문제를 쪼개나가면 된다. 소스코드 #include using namespace std; int paper[128][128]; int colors[2]; //colors[0] = white, colors[1] = blue bool isSame(int size, int row, int col, int color) { for (int i = row; i < (size + row); i++) { for (int j = col; j < (size + col); j++) { if (p..

문제 풀이 문제 자체도 시간초과 때문에 아주 만만한 문제는 아닌데 입력이 아주 재미나게 들어와서 난이도를 더하는 문제다. 문제의 제목은 입력을 처리하다 나오는 말을 쓴 것 아닐까? 아무튼 시간초과를 보고 싶지 않다면, 이걸 생각하면 된다. R이 나왔을 때 꼭 배열을 뒤집을 필요는 없다. 한 수열에 대해 뒤에서부터 출력하면 reverse한 수열을 앞에서부터 출력하는 거랑 다를게 없다. 소스코드 #include #include #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); string p, arr; int T, n; cin >> T; for (int i = 0; i < T; i++) { ci..

문제 풀이 입력을 어떻게 처리할지만 구상하면 이 문제는 끝난거나 다름 없다. 이 문제에서 가장 신경써야 하는 것은 각각 다른 위치에 있는 숫자들을 정해진 순서로 뽑아야 하는 것이다. 그니까 입력에서 주어진 수들 말고는 신경 쓸 필요 없고, 입력값들도 그걸 그대로 저장하는 것이 아니라 입력된 위치에 순서 정보로 넣어주면 된다. 예제 입력 2에 대해 입력을 처리하면 0 1 0 0 3 0 0 0 2 0 이렇게 된다. 1, 2, 3의 순서로 숫자가 뽑히도록 할 것이니 2번, 9번, 5번에 위치한 수들이 순서대로 뽑힐 것이다. 소스코드 #include #include using namespace std; int left_move(deque dq, int index) { int cnt = 0; deque tmp =..

문제 풀이 덱(deque)을 풀어쓰면 double ended queue이다. 그니까 앞뒤로 접근 가능한 큐라는 건데 빨대라고 생각하면 되겠다. www.cplusplus.com/reference/deque/deque/?kw=deque deque - C++ Reference difference_typea signed integral type, identical to: iterator_traits ::difference_type usually the same as ptrdiff_t www.cplusplus.com 풀이 #include #include #include using namespace std; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false)..

문제 풀이 대충 상상을 해보자 지금 프린터를 하려는 문서 하나를 띄워놓고 있고(front) 프린트 버튼만 누르면 되는데 이 문서보다 우선 순위가 높은 문서가 있다면 그걸 먼저 출력해야 한다. 그래서 뒤에 대기 중인 문서를 하나하나 살펴보며 우선순위를 확인하는데, 만약 이 문서보다 더 높은 순위의 문서가 있다면 다시 대기줄의 맨 뒤로 보낸다.(pop->push) 이걸 반복하면 된다. 우리가 목표로 하는 문서가 출력될 때까지. 소스코드 #include #include using namespace std; struct paper { //우선순위와 체크여부 저장 int pri; bool checked; }; bool endLoop(queue q) { //타겟 데이터가 빠지면 루프 종료 queue tmp = q;..

문제 풀이 TMI지만 고등학교 수학선생님께선 원순열을 가르치실 때 약간 과격한 비유를 사용하셨다. 뭐...총으로 쏜다거나...기절을 시킨다거나 아무튼 그 덕에 그 파트를 제대로 배우고 지금까지 기억하니 나쁘지 않았던 것 같다. 아무튼 원을 일자로 펴보고 제일 앞에 총을 든 괴한이 있다고 하자. 너무 잔인하니까 마취총이라고 하자. 이 괴한은 3(=K)번째 사람만 공격한다. 1~8(=N)명의 사람들은 두려움에 떨며 그 괴한 앞에 줄서있다. 괴한은 3번째 사람만 공격하니 1번 사람을 다시 줄 뒤로 보낼 것이다.(pop->push) 2번 사람도 다시 줄 뒤로 보내고, 3번 사람을 만났을 때 마취총을 쏠 것이다.(pop) 모든 사람이 마취총에 맞을 때까지(size=0) 진행하면 되겠다. 소스코드 #include ..

문제 풀이 1~N까지의 카드가 순서대로 있다고 한다. 제일 위에 있는 카드를 버리고(pop) 그 다음에 있는 제일 위의 카드를 제일 아래로 옮긴다.(pop->push) 이걸 카드가 1장 남을 때까지 반복한다고 한다.(size가 1이면 반복문 종료) 이대로 작성하면 된다. 소스코드 #include #include using namespace std; int main() { queue q; int N; cin >> N; for (int i = 1; i