문제 링크 16139번: 인간-컴퓨터 상호작용 풀이 각 알파벳마다 누적합을 구하는 문제 개행할 때 \n을 써주어야 하고, 누적합 구할 때 난 현재 인덱스부터 문자열 끝까지를 갱신해줬는데, 이렇게 하면 시간 초과가 나는 듯 하다. 입력받은 문자열 s를 하나씩 돌면서 각 알파벳의 누적합을 구해준다. 현재 인덱스의 a~z의 누적합을 갱신해주고, 현재 알파벳은 +1해준다. 질문을 입력 받으면서, stt-1이 0보다 작다면 alpha[c-'a'][end]를, 아니라면 alph[c-'a'][end] - alpha[c-'a'][stt-1]을 출력한다. 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); ..
문제 링크 14889번: 스타트와 링크 풀이 백트래킹 문제 먼저 팀은 두 개로 나누어지기 때문에 한 쪽 팀을 구하면 자동으로 다른 팀이 만들어진다. 그래서 n명의 사람 중에 n/2의 사람만 뽑으면 됨. 또한 순열이 아닌 조합이기 때문에 해당 팀에 그 사람이 있는지 확인하는 작업이 필요없이 바로 curIdx+1부터 뽑으면 된다.(왜냐면 그 전에 뽑힌 조합일 것이기 때문) 그렇게 func 함수로 team의 사이즈가 n/2가 될 때까지 뽑고, 다 뽑히면 각 팀의 능력치를 계산한다.(calculate) calculate 함수에서는, 0~n-1의 사람을 한 명씩 체크하면서, 다른 사람들을 체크한다. 해당하는 사람이 team에 있다면, 다른 선수도 그 team에 있어야 능력치를 더해주기 때문에 찾아주는 작업을 해준..
문제 링크 14888번: 연산자 끼워넣기 풀이 백트래킹문제 먼저 숫자가 담긴 arr와 연산자 oper를 입력받는다. func함수에서 DFS를 한다. 현재 인덱스인 curIdx가 arr.size()와 같다면 연산이 끝난 것이기 때문에 최댓값과 최솟값을 갱신한 후 return한다. 연산자를 하나씩 보면서 0보다 큰 경우 연산자를 사용(oper[i] -= 1)하고 재귀호출한다. 재귀호출시, 현재 인덱스는 +1해주고, 현재까지 연산값 curSum을 갱신해주어 넣는다. 해당 함수 호출이 끝나면 연산자는 원래대로 돌려놓아야 제대로 작동한다. 최댓값과 최솟값을 출력한다. 코드 #include #include #define INF 1000000001 using namespace std; int minAns = INF;..
문제 링크 1992번: 쿼드트리 풀이 분할 정복 문제 먼저 모두 같은지 확인하는 check함수로 해당 영역이 모두 같은 숫자라면 true, 아니라면 false를 return한다. 영역이 모두 같으면 answer에 해당 숫자를 추가한다. 아니라면 영역을 나눠주는데, (괄호를 먼저 추가하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 재귀호출한다. 이 때 size는 반으로 줄여준다. 모든 호출이 끝나면 answer에 )괄호를 추가해준다. 코드 #include #include #include using namespace std; string answer = ""; bool check(vector &v, int size, int y, int x) { char c = v[y][x]; for (int ..
문제 링크 2580번: 스도쿠 풀이 백트래킹 문제 먼저 arr 배열에 입력을 받으면서 0이라면 zero 벡터에 넣어준다. DFS를 시작하는데, zero를 다 채울 때까지(idx가 zero의 사이즈) 반복한다. 0위치에 1~9의 숫자를 모두 넣어봐서 규칙에 맞는지 체크(check)한다. check함수는 각 세로줄, 가로줄, 네모박스를 체크해서 규칙에 맞으면 true, 아니면 false를 return한다. true라면 해당 위치에 그 숫자를 넣을 수 있는 것이므로 arr[y][x]에 넣고, idx+1를 해서 다시 재귀호출한다. 정답이 여러 개인 경우 하나의 보드만 출력할 수 있도록, 보드가 완성되면 flag = true한다. 코드 #include #include #include using namespace ..
문제 링크 10989번: 수 정렬하기 3 풀이 정렬 문제. 입력을 다 받아서 sort하려고 하면 메모리 초과가 난다.. 입력 길이는 최대 10,000,000라서 int형으로 만들어줘도 4B * 10000000니까 40MB로 메모리 초과가 난다. 대신 각 값은 10,000으로 엄청 작은 편이라 계수 정렬을 사용하면 된다. 계수 정렬의 시간 복잡도는 O(n) 배열을 초기화해준다. 입력의 최대값은 10000이므로 10001 사이즈로 만들어줘야 한다. 처음에 이것때문에 틀림 입력을 받으면서 배열을 갱신해준다. 각 인덱스의 값은 인덱스의 숫자가 몇 개 들어있는지가 들어가게 된다. 배열이 완성됐으면 인덱스의 값만큼 인덱스를 출력해준다. 5 1 3 1 4 2 3 5 1 7 이게 입력 값이라면, 완성된 배열은 0 1 ..
