결국 오고야 마는 것들

두 문제는 출력 형식만 다른 같은 문제다. 심지어 이름도 같다. 하나를 풀고 까먹을때쯤 다른 하나를 풀었어야 하는데, 눈앞에 꽁짜 경험치를 참지 못했다... 문제를 딱 읽었을 때 방법이 떠오르지 않아서 시간초과가 분명함에도 모든 정점에서 bfs를 돌렸다. 물론 시간초과. 도저히 떠오르지 않아서 좀 찾아보니 구사과님의 블로그에 트리의 지름을 구하는 잡기술이 있었다. 1. 트리에서 임의의 정점 u에서 가장 먼 정점 v를 찾는다. 2. 정점 v에서 가장 먼 정점 w를 찾는다. 정점 v와 w를 찾았다면 트리의 지름은 v와 w의 거리이다. 남은 부분을 뚝딱하면 문제 해결. #include #include #include using namespace std; vector adj[100001]; //vertex di..

혼내주기 2021. 8. 2. 00:02

트리 문제를 많이 안풀어봐서 양방향 그래프라는걸 까먹고 삽질했다. 방문하지 않은 모든 정점에 대해서 bfs를 돌면서 트리인지 아닌지를 구별한다. 한 번의 bfs로 발견한 정점이 n개 일 때, 간선이 n-1개 라면 트리이다. 출력에서 Case 뒤에 붙는 번호는 테스트 케이스 번호이다. 그리고 출력 형식에 'Case #: ~~' 이런식으로 숫자와 : 사이에 띄어쓰기가 없다는 걸 유의하자... 혹시 삽질하고 있다면 이 두가지를 참고해보길. #include #include #include using namespace std; vector visited; vector adj[500]; int b(int src){ int nodes = 0, vertices = 0; queue q; q.push(src); visit..

혼내주기 2021. 8. 2. 00:00

위상정렬 문제. 종만북에서 위상정렬을 dfs를 돌린다음 방문 순서의 역순을 출력함으로 해결했던 기억이 있었는데, 이번에는 모든 정점에서 자신에게 들어오는 정점들을 따로 벡터에 저장해서 해결했다. target 정점을 시작으로, 자신에게 들어오는 정점 중 가장 시간이 오래 걸리는 정점을 재귀적으로 선택해서 건설 시간을 다 더하면 된다. #include #include #include #include using namespace std; int buildTime[1000], cache[1000]; vector adj[1000]; vector innode[1000]; int build(int target){ int& ret = cache[target]; if(ret != -1) return ret; if(inn..

혼내주기 2021. 8. 2. 00:00

스코페 3번 문제와 유사한데 크기가 1000이다. 무식하게 풀면 시간 초과에 걸린다. 주어진 위치에서 가장 큰 정사각형의 한 변 길이를 저장하는 dp table을 만들면 된다. 아래의 그림에서 파랑색 점의 현재 위치를 [x][y]라고 할 때, [x-1][y-1], [x-1][y], [x][y-1]의 최솟값 + 1이 [x][y]의 값이 된다. 만약 이 문제가 스코페에 나왔다면 풀지 못했을 것 같다... 갈 길이 멀다..... #include #include #include using namespace std; int map[1001][1001]; int main(){ ios::sync_with_stdio(0); cin.tie(0); string s; int n, m; cin >> n >> m; for(in..

혼내주기 2021. 8. 1. 23:26

삽질 1. dp인 줄 알았는데 설명하기도 어려운 방법으로 구현하려다 포기. 삽질 2. 도저히 안떠올라서 구글링을 통해 dp table에 현재 위치에서 뻗은 개수를 저장해야 함을 발견. 삽질 3. 최대 크기부터 유효한 범위에서 다이아몬드를 발견하면 바로 종료하도록 구현했는데, 시간 초과. 결국 크기를 dp table의 범위 내에서 정하고, 군데군데 가지치기를 넣어서 해결했다. 너무 삽질을 오래해서 풀었는데도 기분이 꿀꿀하다. 아직도 갈 길이 멀다... #include #include #include using namespace std; int map[751][751]; int bl[751][751], br[751][751]; int main(){ ios::sync_with_stdio(0); cin.tie(..

혼내주기 2021. 8. 1. 23:25

완전탐색 + dp 문제. 시작점에서는 모든 방향으로 움직일 수 있기 때문에 이중 for문으로 출발점을 일일이 찍어주면 방향 때문에 dp 배열 크기를 4로 하지 않아도 된다. 이 문제를 풀면 17484 진우의 달 여행 (Small) 문제를 날로 먹을 수 있다. #include #include #include using namespace std; int dy[3] = {-1, 0, 1}; int map[1000][1000], cache[1000][1000][3]; int n, m; int d(int x, int y, int dir){ if(x == n) return 0; int& ret = cache[x][y][dir]; if(ret != -1) return ret; ret = 1e9; for(int i =..

혼내주기 2021. 8. 1. 23:24

백준 1915 가장 큰 정사각형 문제와 여러개의 테스트 케이스가 있다는 점만 빼면 동일한 문제. #include #include #include using namespace std; int map[1001][1001]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, m; while(cin >> n >> m){ if(!n && !m) return 0; int ans = 0; memset(map, 0, sizeof(map)); for(int i = 1; i map[i][j]; } } for(int i = 1; i

혼내주기 2021. 8. 1. 23:22

제 1회 류호석배 알고리즘 코딩 테스트 문제. 실시간으로 제 2회 류호석배 알고리즘 코딩 테스트 진행중이다. 실전 느낌으로 도전했는데, 1솔에 1문제는 일부분만 맞고 (사실상 틀린것) 나머지는 생각해봐도 방법이 떠오르지 않아서 깔끔하게 포기하고 1회 문제들을 풀고 있다. (오답주의) #include #include using namespace std; int ie[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; int countOdd(int n){ int ret = 0; while(n >= 10){ if(n%2 == 1) ret++; n /= 10; } if(n%2 == 1) ret++; return re..

혼내주기 2021. 8. 1. 23:21