Miscellaneous

https://www.acmicpc.net/problem/2098 해당 문제는 이전에 풀었던 문제였음에도 불구하고, 최근 기업 코테에서 이와 비슷한 유형의 문제를 풀지 못했습니다. 아쉬운 마음에 복습하고자 해당 문제의 풀이를 작성합니다. 해당 문제는 백트래킹으로 구현할 시 O(16!)으로 시간초과가 발생합니다. 이 문제는 외판원 순회라는 well-known 유형입니다. 문제의 조건과 같이 n이 16이하일 때에는 비트마스킹 dp로 해결할 수 있습니다. dp 상태는 아래와 같이 정의합니다.dp[i][j] : 현재 위치가 i이고, 지금까지 j 도시를 방문했을 때의 최단거리n 2^16 = 65536이기 때문에 배열로 충분히 선언할 수 있는 크기입니다. 풀이 코드는 전형적인 비트마스킹 탑다운 dp 코드입..

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조로 마찬가..