Miscellaneous

https://www.acmicpc.net/problem/1034 해당 문제는 흔한 브루트포스 문제랑은 살짝 결이 다른 느낌을 받았습니다. 처음 생각했던 풀이는 2^m가지 경우를 다 돌리는 풀이였습니다.하지만, 스위치를 누르는 횟수 k에 대해서 m 한 스위치를 두번 누르는 것은 안누른 것과 동치이기 때문에 이런 경우에 대해서 따로 예외처리를 해주려고 했으나, 생각해주어야 할 것들이 너무 많아지더라구요. 결국 기존 풀이는 폐기하고, 다른 풀이를 생각해보았습니다. 관찰한 내용은 아래와 같습니다. 1. 만약 두 개의 행 A,B가 동일한 형태를 띈다면, A행이 켜진다면 반드시 B형도 켜질 것입니다. 반대로, A,B가 하나라도 다른 부분이 있다면, 해당 행은 반드시 동시에 켜질 수 없습니다. 2. 한 행에서 켜야..

https://www.acmicpc.net/problem/6525 n*n 행렬에서 각각의 칸들이 서로 다른 행과 열에 속해있도록 n개의 칸을 선택합니다. 이렇게 선택하는 경우의 수는 총 n!개입니다. n!개의 경우의 수에 대해서 n개 원소의 총 합이 모두 같은 지를 판단하는 문제였습니다. 규칙이 있을 것 같은데, 고민해봐도 찾지 못하겠더라구요.그래서 저의 경우에는 랜덤화를 이용하여 해결했습니다. 무작위로 1만개의 수열을 생성한 뒤, 합이 일정한지를 확인했습니다. 문제해결을 하면서 랜덤화를 처음 사용하게 됐는데, 주요 함수는 아래와 같습니다.// 시드값 (time(NULL))에 대한 난수 생성mt19937 rng((unsigned int)time(NULL));// 난수 생성기를 기반으로 배열 셔플su..

https://www.acmicpc.net/problem/5569 모든 경우에 대해서 탐색하려고 하면,최대 200C100의 경우의 수가 만들어지므로 시간 안에 해결할 수 없습니다.  해당 문제는 dp로 해결할 수 있습니다.현재칸에 위/왼쪽에서 왔고, 방향을 바꿀 수 있는지에 대한 여부를 기록하기 위해 dp[i][j][k][l]로 표현할 수 있습니다. i, j : 현재 칸의 인덱스k : 0이라면 왼쪽에서, 1이라면 위에서 접근l : 0이라면 방향을 바꿀 수 없고, 1이라면 방향을 바꿀 수 있음    점화식은 위 그림처럼 나타낼 수 있습니다. (파란색, 연두색)빨간색은 {i,j}에 접근하는 모든 경우입니다.이전 칸에서 한번 꺾은(방향을 바꾼) 경우엔 {i,j}에서는 방향을 바꿔선 안되고,반대로 꺾지 않은 경..

https://www.acmicpc.net/problem/24508  나도리를 옮기는 횟수를 최소화하려면, 일단 나도리 수가 작은 바구니부터 나도리를 옮겨 비워야 합니다. (greedy)이를 위해서는 정렬은 불가피함을 쉽게 파악할 수 있었습니다. 여기서 1. 투포인터를 쓰는 풀이와 2. 수학적으로 간단하게 푸는 풀이를 소개합니다.   1. 투포인터 풀이 나도리가 가장 많이 들어있는 바구니부터 채워줍니다. 나도리의 수를 기준으로 오름차순 정렬하여, 가장 앞에 있는 나도리부터 차례대로 가장 뒤에 있는 바구니에 넣습니다. 즉, 현재까지 나도리가 가장 적게 들어있는 바구니에 있는 나도리를 나도리가 가장 많이 들어있는 바구니에 채워넣습니다. 동시에 나도리의 이동 횟수를 기록해줍시다. 나도리를 k개 다 채웠다면, ..

https://www.acmicpc.net/problem/2716      수학 잼병인 작성자인지라... 증명이 옳은지는 모르겠습니다.. 결국 트리의 높이(최대 깊이)를 구하는 것이 문제의 key이므로,입력 string을 읽으면서 트리의 최대 깊이를 구해주기만 하면 되는 문제였습니다.   코드#includeusing namespace std;#define X first#define Y second#define rep(i,x,y) for(int i=x;i pii;typedef pair pll;typedef tuple tiii;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };/*----------------------*/void solve(){ string s; ..

https://www.acmicpc.net/problem/17353레이지 프로파게이션 공부하다가 만난 문제입니다.그래서 "레이지를 쓰긴 하겠구나"는 알았지만, 어떻게 레이지를 써야될 지가 막막했습니다.도저히 고민해도 풀이가 떠오르지 않았기에, 결국 답을 봤던 문제입니다.. 일단 Lazy Propagation은 기본적으로 두가지 연산을 지원합니다.1. 구간에 대한 단일값 업데이트 쿼리2. 구간에 대한 쿼리 하지만 문제에서 주어지는쿼리는 다음과 같습니다.1. 구간에 대한 다중값(등차수열) 업데이트 쿼리2. 점에 대한 쿼리  우선 구간 업데이트입니다. 문제를 위해 구간에 대해 1,2,3,...,R-L+1씩 업데이트 해야합니다.하지만 가지고있는 연산은 단일 값으로만 업데이트가 가능합니다. 그래서 처음 생각해봤던..

https://www.acmicpc.net/problem/16624  팀원들과 ICPC 골랜디 연습 중에 찾은 문제였습니다.   n개의 5*5 빙고판이 있고, 무승부 즉, 동시에 빙고가 되는 판의 쌍이 존재하는 지 찾는 문제입니다. 여기서, 빙고는 대각선, 세로를 제외한 가로줄만 인정합니다.  가장 먼저 떠올린 풀이는, 빙고판의 숫자가 최대 3000이기 때문에, 가능한 모든 빙고 조합에 대해서 완전탐색하고자 하였습니다. 그렇게 되면, 모든 조합은 3000C5 = 약 2000조...이기때문에 시간 안에 돌기에는 무리가 있습니다. 여기서 n이 100이고, 빙고판은 5*5이므로 모든 빙고판에 중복없이 작성한다면 총 100*5*5 = 2500 가지의 숫자가 적히므로, 줄여도 2500C5 = 약 800조로 마찬가..

https://www.acmicpc.net/problem/18405문제는 간단합니다. n*n 시험관에 바이러스 번호에 번호가 매겨져있고, 번호 순서대로 주변 한칸씩 퍼뜨리는 연산을 s번 돌리는 문제입니다.예를 들어 바이러스가 1,2,3번이 있고, s=3이라면1,2,3, 1,2,3, 1,2,3 순서대로 바이러스를 퍼뜨립니다. 되게 간단한 문제라 이번 포스팅에서는 문제를 푸는 방법보다는 코드를 최적화 하는 방법에 초점을 맞춰서 작성하고자 합니다. 총 9단계를 거쳐서 코드를 개선해나가보겠습니다! 우선 첫번째 코드입니다.#includeusing namespace std;int dx[] = {0,0,1,-1};int dy[] = {1,-1,0,0};int board[202][202];int vis[202][202..