문제 링크18808 스티커 붙이기접근최대한 문제에서 제시한 대로 구현하려고 노력했다. 그러나 답은 맞았지만 머릿속에서 꼬여버린 탓에 코드를 덕지덕지 짠 것 같다. 그래서 시간복잡도가 그렇게 좋지 못한 결과가 나왔다. 그래서 바킹독님 블로그에 제시된 간결한 코드로 다시 복습해 보려 한다. 앞으로는 먼저 계획을 세우고 코드를 짜는 습관을 길러야겠다. 알고리즘노트북에 스티커를 붙일 수 있는지 확인한다.만약, 스티커를 붙일 수 있다면 스티커를 붙인다.만약, 스티커를 붙일 수 없다면 스티커를 회전한다.모든 방향으로 회전하여도 스티커를 붙일 수 없다면 그 스티커를 버린다.이를 스티커를 다 쓸 때까지 반복한다.코드#include using namespace std;int n, m, k;int note[42][42];..
문제 링크15686 감시접근(1)int cctvCases[5][4] ={ { 0, 0, 0, 1 }, { 0, 0, 1, 1 }, { 0, 0, 1, 1 }, { 0, 1, 1, 1 }, { 1, 1, 1, 1 },}; {위, 아래, 왼, 오른}순(바라보는 방향)으로 boolean 배열 규칙을 임의로 지정하고 CCTV의 모든 방향을 손으로 적어 봤더니 규칙을 찾을 수 있었다. 예를 들면 CCTV 1은 {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}으로 4C1의 경우의 수와 같다고 생각했다.마찬가지로 CCTV2, CCTV3, CCTV4, CCTV5도 4Cn이라고 가정하고 문제를 풀이하였다.이 과정에 next_permutation..
문제 링크16987 계란으로 계란치기 접근 및 알고리즘문제를 이해하는 것만 해도 시간이 들었다. 나의 집중력 이슈 ㅜㅜ문제 내용을 요약하자면 다음과 같다.1. 입력으로 받은 계란 중 첫번째 계란을 손에 쥔다.2. 남은 계란 중에 하나를 손에 쥔 계란으로 친다. (손에 든 계란이 깨졌거나, 현재 계란 말고 다른 계란이 전부 깨져 있으면 치지 않는다.)3. 이때, 손에 있는 계란이 깨질 수도 있고, 다른 계란이 깨질 수도 있고, 둘 다 깨질 수도 있다.4. 아무튼 손에 있는 계란이 깨졌든 말든 한번 쳤으면 손에 있는 계란을 다시 제자리에 놓는다.5. 그 다음에, 손에 있었던 계란의 다음 차례 계란을 손에 쥔다.6. 2 - 5를 반복하고, 만약 방금 손에 쥐었던 계란이 마지막 위치의 계란이면 종료한다. 첫번째..
문제 링크1941 소문난 칠공주 접근 문제를 풀다가 어떻게 풀어야 할지 긴가민가해서 알고리즘 분류 항목을 열어 훔쳐보았다...열심히 생각해 본 결과는 아래와 같다.25C7을 구한다.7명이 접해 있는지 확인한다.7명이 접해 있다면, 이다솜파의 수가 4 이상일 때, ans를 카운트한다.하지만 구현에는 실패하였다. 바킹독 님의 답안에는 next_permutation를 사용한 풀이가 있었지만, 나는 next_permutation에 대한 이해가 부족했다.next_permutation에 대한 공부를 더 하고 이 문제를 이해해 보려 한다. 전체 코드#include #include #include using namespace std;// 1. 25C7을 구함.// 2. 7명이 접해있는지 확인// 3. 이다솜파의 수 확..
1. next_permutation 함수란?현재 순열(permutation)에서 다음 사전순 순열을 생성하는 함수이다. 이때, 순열 자체를 반환하는 것이 아니라, 원본 데이터를 직접 변경한다.next_permutation을 호출할 때마다 컨테이너(vector, string, array 등)의 요소가 다음 사전순 순열로 변경된다.모든 순열을 생성할 수 있다. next_permutation의 반환값은 bool 값이다.다음으로 생성할 순열이 존재하면 true를 반환하며, 다음으로 생성할 순열이 없다면 false를 반환한다.do-while문을 이용해 깔끔하게 사용할 수 있다. C++의 next_permutation은 algorithm 헤더에 포함되어 있다. 2. 기본 사용 예제 (순열)#include #inc..
문제 링크1759 암호 만들기접근조건을 만족하는 모든 경우의 수를 찾는 문제이므로 백트래킹을 사용하여 풀이하였다. 알고리즘k번째 문자를 뽑기 위해 다음과 같은 절차를 거친다. 만약 지금 뽑을 문자가 이미 사용되었다면, continue만약 지금 뽑을 문자가 이전에 뽑은 문자보다 사전순으로 앞에 있다면, continue (증가하는 순서로 배열되어야 하기 때문) 문자를 뽑는다. 만약 이 문자가 모음이라면, 모음 개수를 +만약 이 문자가 자음이라면, 자음 개수를 + 여기까지 왔다면, 문자가 사용된 것도 아니고, 사전순에 위반하는 문자도 아니므로 문자를 확정해 준다.이후 사용했다고 중복 배열에 표시. 다음, k + 1 번째 문자를 뽑기 위해 재귀함수를 실행한다. 이렇게 진행하다가 필요한 모든 문자를 다 뽑았다면,..
문제 링크15666 N과 M (12)풀이N과 M (11) 문제 풀이에서 비내림차 수열만 방지하면 되는 문제이다. 따라서 조건문에 비내림차 수열을 방지하는 조건을 추가하여 문제를 풀이하였다. 코드#include #include using namespace std;// N개 중에서, M개 뽑음int N, M;// n번째로 뽑은 수를 저장int picked[10];// 숫자 모음int numbers[10];// k 번째로 저장할 수를 탐색 void Solve(int k){ if (k == M) { for (int i = 0; i 0 && picked[k - 1] > numbers[i])) continue; picked[k] = numbers[i]; tmp = p..
문제 링크15663 N과 M (9)접근N개의 수 중 M개의 수를 뽑아 수열을 만든다. 이때, 중복되는 수열은 없어야 하며, 사전순으로 출력해야 한다.예를 들어, 4개의 수(1, 7, 9(A), 9(B)) 중 2개를 뽑아 만들 수 있는 수열은 다음과 같다.1 71 97 17 99 19 79 9 (1, 7), (7, 1)은 되지만 (1, 9(A)), (1, 9(B))는 안 된다. 즉 사전순으로 중복되면 안 된다. 기존 백트래킹 방식에서 조금 응용하여 풀었다. 배열은 정렬되어 있다고 가정한다. N개의 수(1, 7, ... ,9(A), 9(B)) 중 M개를 뽑아 만들 수 있는 수열을 만든다고 가정해 보자. 기존 백트래킹 방식에서는 k번째 수를 뽑은 다음, k+1번째 수를 뽑기 위해 재귀 함수를 실행한다. 이때,..
