알고리즘 (28) 썸네일형 리스트형 [백준] 로봇 조종하기_2169 cache[y][x] = 현재 위치에서 앞으로 더 얻을 수 있는 최대 가치 이렇게 두고 풀었는데, 저 테스트케이스를 통과하지 못해서 계속 틀렸다. cache를 방향까지 고려해서 3차원 배열로 해야한다는 것을 미처 생각하지 못했다. 7이 나와버림.. 4 4 1 1 1 1 -1 -1 -1 1 1 1 1 1 100 -10 1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 100 -10 1 1 최대 가치(101)를 얻으려면 이렇게 움직여야 한다. 현재 위치에서 앞으로 더 얻을 수 있는 가치는 그 전 방향에 따라 다르다. 따라서 위치 + 방향까지 고려해서 3차원 배열을 사용해야 한다. 왼쪽에서부터 왔다면 다시 왼쪽으로는 못 갈테니깐, 다른 방향으로 가서 최댓값을 저장하게 된다. 하지만 다른 방향에서 왔다면 .. [백준] 스도쿠_2580 처음에는 81개의 모든 숫자가 0일때의 경우를 맞추지 못해 틀렸다. 매개변수로 배열을 가져가면서, 다시 부모 노드로 돌아왔을 때 채워진 배열이 그대로 남아있어 다음 dfs에서 잘못된 예전 배열값을 가지고 검사하기 때문이었다. 예를 들어, (0,0)을 1로 채우면서 시작한뒤 어느정도 채워나가다가, 어느순간 잘못된걸 알아서 선택지가 없으면 다시 (0,0)으로 돌아올 것이다. 이 때 2로 채운 뒤 다음 dfs에서 검사하는 배열은 선택지가 없어 다시 돌아왔었던 그때의 배열이다. 깨끗한 상태의 배열이 아니라... 그 다음에는 코드가 맞는 것 같았는데, 모든 반례를 찾아서 넣어봤는데도 몇 퍼센트까지 가지도 않고 바로 틀려서 뭔가 크게 실수하는건가 싶었지만 찾기가 너무 힘들었다. 방황의 흔적...^^ 넣을 수 있는 .. [백준] N과 M (9)_15663, N과 M (10)_15664 N과 M (9) 같은 숫자가 있을 수 있다. 중복해서 뽑아서는 안 된다. 사전 순으로 출력해야 한다. input이 다음과 같은 경우 4 2 9 7 9 1 -> 1 7 9 9 로 정렬 if (prev == arr[i] || check[i]) continue; 중복해서 뽑으면 안되니까 check 배열을 이용해서 확인해야 한다. ex) 1 1 은 x 같은 숫자가 있을 수 있지만, 중복되는 수열이 여러 번 출력되면 안되므로 prev 변수와 현재 수를 비교해야 한다. 첫 번째 9는 dfs에 들어가서 1, 7, 9 를 마저 고르지만 두 번째 9는 prev와 같으므로 그냥 지나간다. ex) 9 9 두 번은 x 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 .. [백준] N과 M (7)_15656, N과 M (8)_15657 N과 M (7) N개 중에 M개를 고르는데, N개의 자연수는 모두 다른 수이고, 같은 수를 여러 번 골라도 된다. 사전 순으로 증가하는 순서로 출력해야 한다. 사전 순으로 출력하기 위해서 정렬을 해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #include using namespace std; int N, M; int arr[7], s[7]; void dfs(int cnt) { if (M == cnt) { for (int i = 0; i [백준] 연속합_1912 기초 dp 문제들 중에 안 푼게 꽤 있길래 다시 풀고 있다... 히히.. 숫자는 어차피 연속적으로 더해야 하므로 바로 전 숫자만 고려하면 된다. cache[i] = max(arr[i], arr[i] + cache[i - 1]); 지금 내 숫자(arr[i])에 그 전까지 연속적으로 더해왔던 숫자 합(cache[i-1]을 더해서 손해가 난다면 이 합을 더할 필요가 없다. 연속을 끊고 cache에는 지금 숫자만 저장하면 된다. **몰랐던 것 잘 가다가 틀려서 왜 틀렸을까 생각해봤는데 최댓값을 업데이트하는 for문 부분을 i=1 인덱스에서부터 시작하게 했기 때문에, 숫자가 하나만 들어오는 경우에는 최댓값을 업데이트하지 못해 틀린 것이었다. 그래서 숫자가 1개인 경우에는 그 숫자가 최댓값이 되도록 설정하고, 나머.. [백준] 최종 순위_3665 위상 정렬을 공부했었지만 다시 까먹어버렸다. 이 문제는 위상정렬 문제라는 것을 모르고 풀고 있었다. 주의해야 할 점은 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어진다는 것이다. 상대적인 순위가 바뀐 것이지 팀1 팀2 이렇게 주어졌을 때 팀1이 팀2보다 순위가 높다는 말은 아니다. 2 1 2 1 1 2 따라서 다음 테스트케이스에서 답은 2 1 이 나와야 한다. 기존 1 2 의 순위가 바뀌어서 2 1 이 되었으므로. 같은 순위를 가지는 팀은 없으므로 이긴 횟수(어떤 팀이 다른 팀보다 순위가 높다면 이겼다고 보고)와 등수는 직결된다. ex) 팀이 6개라면 1번 이겼으면 5등 5번 이겼으면 1등 하지만 이런 방법으로는 확실하지 않은 순위는 중복된 순위가 나올 것이므로 처리할 수 있겠지만, 데이터의 .. 벨만-포드 알고리즘 (+ 백준 11657 타임머신) 알고리즘을 보면서도... 문제를 풀면서도 이해가 잘 가지 않아 여러 블로그의 글들을 읽어보았다. 벨만-포드 알고리즘을 공부하면서 들었던 의문점을 정리해보았다. 벨만-포드 알고리즘은 다익스트라 알고리즘과 달리 간선의 가중치가 음수일때도 동작하는 SSP 알고리즘이다. 1. 왜 간선의 가중치가 음수일때도 잘 동작할까? 다익스트라 알고리즘은 그때그때의 상황에 최선의 선택을 하려는 그리디 알고리즘 기반이기 때문에 다음과 같은 상황에서는 통하지 않는다. 벨만-포드는 가능하다. 모든 경우의 수를 다 보기 때문. 2. 모든 경우의 수를 보려면 왜 V-1번 반복해야 할까 사실,방문 순서에 따라 우연히도(u, v)를 먼저 방문하고 dist[v]를 갱신하고 나서 (v, w)를 방문하면 한 번에 dist[w]까지 구해질 것이.. [백준] 알고스팟_1261 다익스트라 + BFS로 풀었던 문제. if (visited[y][x] > wall) visited[y][x] = wall; visited에는 벽을 부순 횟수(wall)이 저장되어 있다. 새로 방문할 곳이 값을 갱신해야 하는 상황이라면 더 작은 값의 wall로 바꿔준다. 우선순위 큐에서는 wall 값이 작은 순대로 값을 뽑아낸다. 이후 상하좌우 네방향으로 탐색하며 벽이 있는 상황이라면 wall+1한 값을 큐에 넣고, 아니라면 그냥 wall 값을 그대로 유지한채 새로운 좌표값을 큐에 넣는다. 저 값을 갱신하는 부분을 안 하고 제출했더니 불필요한 경우도 계속 큐에 들어가서 메모리 초과가 계속 떴었다... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23.. 이전 1 2 3 4 다음
