벨로그로 바꿀까 고민하는 블로그

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 최대 안전 지대의 개수를 찾는 문제이다. 어떤 높이일 때 안전 지대가 최대가 되는지 알려주지 않기 때문에 높이 범위(1~100) 안의 모든 높이를 다 대입해서 풀었다. 그런데 모든 주어진 땅의 높이보다 더 높은 높이부터는 다 물에 잠겨 안전지대 개수가 0일 것이므로 break문으로 for문을 빠져나올 수 있도록 했다. 높이를 갱신할 때 마다 visited배열이랑 안전지대 개수를 초기화를 해야 한다! HT..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 몇 번 탐색해야 한 노드(사람)에서 다른 노드까지 도달할 수 있는지를 묻는 것 같다. dfs로 풀었는데, 목표 노드에 도달하면 재귀함수를 빠져나온다. visited 배열에는 몇번째에 해당 노드를 방문했는지를 저장함으로써 방문처리를 했다. HTML 삽입 미리보기할 수 없는 소스 갑자기 backtracking과 dfs의 차이점이 헷갈려서 ChatGPT한테 물어봤다.

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 한 번에 갈 수 있는 노드의 개수를 어떻게 세야하는지 까먹어서 chat gpt 한테 물어봤는데 이렇게 하는 거였다. 그래프 문제를 하도 안풀다보니 다 까먹은 것 같다ㅋㅋㅠㅠㅠ 그리고 dfs(0) 을 출력했어야 하는데 dfs(1)을 출력해서 계속 틀렸다. 근데 dfs(1)을 출력하는 코드로 게시판에 올려져있는 반례 거의 다 돌려봤는데 다 맞게 나온건 뭐지ㅋㅋㅋㅋ 의문이다.. HTML 삽입 미리보기할 수 ..

https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 점화식은 다음과 같다. dp[i + 1] = min(dp[i + 1], dp[i] + 1) ... dp[i + arr[i] - 1] = min(dp[i + arr[i], dp[i] + 1) dp[i + arr[i]] = min(dp[i +arr[i]], dp[i] + 1) dp배열은 1001으로 초기화 해주었다. 아무리 점프를 많이 해봤자 1001번 넘게 점프할 수는 없기 때문이다. H..

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 처음에는 이렇게 구현했는데 주어진 테스트케이스에서 첫번째 테스트케이스만 통과를 못했다. #include using namespace std; int main(void) { int n; int arr[3][1001]; int dp[3][1001]; int lastColor[3] = {0, 1, 2}; cin >> n; for (int i = 0; i < n; i++) {..

https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp 배열을 이차원배열로 만들어서 연속합을 이루는 원소 중 하나가 없는 경우랑 그냥 연속합을 이루는 경우랑 나눠서 구하면 되는구나ㅠㅠㅠ 풀이를 보고 풀었는데 풀이랑 거의 똑같이 써서 제출했다ㅋㅋㅠㅠㅠ 참고 13398번 풀이: https://junbastick.tistory.com/8

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net solved.ac 잔디에 구멍 뚫렸길래 그냥 마음 편하게 시험공부나 하자 싶어서 며칠 안풀고 놀았더니 되게 오랜만에 푼 것 같다..ㅋㅋㅋㅋ 증가하는 부분 수열을 구하는 방법은 쉽게 떠올렸지만, 이걸 어떻게 역추적해서 출력해야할지 잘 감이 오지 않아서 풀이를 찾아봤다. HTML 삽입 미리보기할 수 없는 소스 dp[k]..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 요즘 보안 과제 하느라고 백준 문제는 푸는 둥 마는 둥 하고 있다.. 잔디 비는게 싫어서 어떻게든 A+B 같은 쉬운 문제라도 매일 풀려고 하고 있긴한데 이게 무슨 의미가 있는건지 싶기도 하지만.. 왠지 한 번 해이해지면 그나마 하고 있던 알고리즘 공부조차 놓아버릴 것만 같은 생각이 들어서 시험기간이든 과제가 어렵든 상관없이 매일 한 문제라도 풀어야겠다는 고집을 부리고 있다... 이제 그래프스러운..? 문제를 보면 항상 재귀로 풀게 되는 것 같다. 알고리즘 교수님께서 재..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 처음에는 이렇게 점화식을 세웠는데 dp[i] += dp[i - coins[j]] 중복이 아주 많이 나오기 때문에 계속 고민했다. 아무리 생각해봐도 점화식을 못세우겠어서 결국 풀이를 찾아봤다. 풀이를 이해한 바로는, 동전이 0원짜리 1개 있는 경우 동전이 0원짜리, 1원짜리 2개 있는 경우 ... 이렇게 동전의 개수를 늘려가면서 dp배열을 갱신해야 하는 것 같다. i == 6일 때 예를 들어보면 0원..

https://www.acmicpc.net/problem/2294 2294번: 동전 2첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어www.acmicpc.net시간이 c++치고 엄청 오래걸린다. 배열을 안쓰고 벡터로 풀어서 그런건가?? 동전 문제는 그리디 알고리즘으로 최적해를 구할 수 있는 경우가 있고 없는 경우가 있다고 배웠는데, 까먹어서 Chat GPT한테 물어봤다. 동전 거스름돈 문제에서 동전의 단위가 서로 배수 관계가 아닐 경우 그리디 알고리즘은 최적해를 보장하지 못한다. *최적 부분 구조(optimal substruc..