결국 오고야 마는 것들

위상정렬 문제. 종만북에서 위상정렬을 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

제 1회 류호석배 알고리즘 코딩 테스트 문제. 구현 문제. 도미노가 쓰러질 때 연달아 쓰러지는 경우 앞으로 쓰러질 여지?가 가장 많은 도미노의 개수를 계속 업데이트 하면서 쓰러지면 된다. 통과 후 질문을 확인해보니 내 코드가 통과하지 않는 반례가 있었다. 공격수가 처음 공격하는 도미노가 넘어진 상태면 아무일도 일어나야 하지 않는데, 이 예외에 대한 처리가 안되있어서 수정해서 제출했다. 나는 아직 문제를 풀 때 반례를 떠올리는 능력이 부족한데, 이렇게 반례를 찾아내는 사람들을 보면 참 부럽다. 노력으로 극복할 수 있을까? #include using namespace std; int map[101][101]; bool res[101][101]; // 0 S 1 F int main(){ int n, m, r;..

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

제 1회 류호석배 알고리즘 코딩 테스트 문제. dfs + dp인데 범위를 벗어나면 반대쪽에서 이어지도록 하면 된다. dp에는 위치정보(x, y)와 문자의 index값을 넣으면 된다. #include #include #include using namespace std; int dx[8] = {1, 1, 1, 0, -1, -1, -1, 0}; int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1}; int cache[10][10][5]; // x y idx char map[10][10]; int n, m; string s; int d(int x, int y, int idx, int len){ if(idx == len) return 1; int& ret = cache[x][y][idx]; if..

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