문제 링크 10986번: 나머지 합 풀이 누적합 문제인데, 모듈러 연산도 곁들인 .. 참고로 합 모듈러 연산은 (a+b)%m = ((a%m)+(b%m))%m이다. 합이 M으로 나누어 떨어지는 구간을 구하면 되므로, 누적합의 모듈러를 구하는 것. 이 것은 위에 설명한 합 모듈러 연산으로 바꾸어 생각하면 된다. 값을 입력 받으면서 누적합의 모듈러를 구한다. 그렇게 나온 값의 총 개수를 구하기 위해 cnt 벡터에 넣어준다. 각 결과값의 개수가 구해질 것이다.(cnt) 누적합의 모듈러 값이 0인 것은 해당하는 인덱스까지 누적합이 m으로 나누어 떨어진다는 것이고, 다른 두 개의 인덱스가 같은 모듈러 값을 가지면, 해당 인덱스부터 인덱스까지의 누적합이 m으로 나누어 떨어진다는 것이다. 그래서 개수를 구한 것이고, ..
문제 링크 1707번: 이분 그래프 풀이 이분 그래프란 두 집합이 있을 때 하나의 정점은 하나의 집합에 속해야 하는데, 인접한 정점은 같은 집합에 포함되면 안된다는 그래프이다. 주의할 점은 시작 정점에서 연결되지 않은 정점도 체크를 해줘야한다는 것. 테스트 케이스의 수만큼 입력을 받고, 각 테스트 케이스마다 인접 리스트를 초기화해준다. 무방향 그래프이기 때문에 입력 받은 두 정점을 양쪽에 다 넣어줘야한다. BFS를 시작할텐데 정점을 돌며 visit이 0인 (방문하지 않은 정점)일 경우 BFS를 시작해준다. 연결되지 않은 정점 체크를 위함이다. 다른 BFS문제와 같이 queue를 이용하는데, 현재 정점을 q에 넣고, visit도 집합 1로 설정해주며 q가 빌 때까지 반복한다. 다음 정점의 visit이 0이..
문제 링크 16928번: 뱀과 사다리 게임 풀이 BFS 문제 뱀과 사다리 입력을 받으며 인접리스트 adj를 초기화해준다. BFS를 시작한다. 주사위 횟수가 담기는 dist 배열을 INF로 초기화해준다. 이 때 INF는 주사위를 1로 돌려 100칸까지 가는 경우가 최대이기 때문에 101로 정의했다. 첫번째 칸부터 시작해서 queue가 빌 때까지 반복한다. adj[cur].size()가 0보다 큰 경우는 뱀이나 사다리를 타야하고, 아닌 경우는 주사위를 돌려야하기 때문에 경우를 나누어준다. 뱀이나 사다리가 있다면 인접 리스트를 확인해 다음 칸의 dist가 현재 칸의 dist보다 클 경우, 다음 칸을 작은 값으로 갱신해준 뒤 q에 넣어준다. 주사위를 돌릴 경우 1~6까지 주사위를 돌릴 수 있으므로 dist[ne..
문제 링크 11401번: 이항 계수 3 풀이 이항 계수의 식과, 페르마의 소정리, 모듈러 연산을 알아야 풀 수 있는 문제 보통 이항 계수 문제는 DP나 재귀로 풀 수 있는데 입력값이 너무 크기 때문에 시간 초과가 난다. 이런 경우 공식을 이용해 풀어야한다. 우리가 구해야 할 것은 이항 계수를 1000000007 (이하 mod)로 나눈 값이다. 해당 값을 바로 구할 수 있다면 좋겠지만 분수의 나머지 구하기는 힘들기 때문에 페르마의 소정리를 이용해야 한다. 페르마의 소정리란 p가 소수일 때, a^p를 p로 나눈 나머지가 a를 p로 나눈 나머지와 같다는 정리이다. 해당 식을 변형해서 맨 마지막 식까지 만들 수 있고 저 식을 우리가 구해야 하는 값의 공식에 적용할 것이다. 이항계수의 분자를 A, 분모를 B, 나..
문제 링크 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 ..
