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

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..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 0

https://www.acmicpc.net/problem/1890 1890번: 점프첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 포인터를 쓰거나 했다면 더 메모리를 적게 썼을지도 모르지만, 파이썬에 더 익숙해서 그런지 어떻게 풀어야 좋은 건지 잘 모르겠다.. 처음에는 반복문으로 풀었는데 (1, 1)에서 시작하는 경로의 개수만 셀 수가 없어서 결국 dfs처럼 풀었다. 근데 중간에 중복 처리를 안해서 시간 초과가 발생했다. 중복 처리를 안할 경우 답은 나오지만 지수 시간이 걸리기 때문에, 재방문을 하지 않도록 꼭 처리..

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 드디어 https://plzrun.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4PS-%EC%8B%9C%EC%9E%91%ED%95%98%EA%B8%B0 이 글에 나왔던 백준 문제들을 (거의) 다 풀었다.. 플레만 빼고ㅋㅋ 거의 한 세달은 걸린 것 같다.. 이제 뭐할까 ..

https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 누적합을 구하는 방법을 잘 모르겠어서 그 부분만 풀이를 참고하고, 누적합 벡터를 구하고 나서 정렬한 후, 두 포인터 알고리즘을 이용해서 풀었다. A피자 또는 B피자만 선택하는 경우를 고려하지 않아서 좀 오래걸렸다ㅠㅠ HTML 삽입 미리보기할 수 없는 소스 참고 2632번 풀이: https://blogshine.tistory.com/588

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 당연한거지만 모든 순서쌍 조합을 for문으로 만들려고 하면 시간복잡도가 O(n^4)가 되기 때문에 최대 4000 ^ 4번 연산을 해야하므로 시간 초과가 발생할 것이 뻔하다... 두 포인터 알고리즘을 사용하면 O(n^2)으로 줄일 수 있따. 풀이) A, B, C, D 리스트를 입력받는다. 가능한 A[a], B[b]의 합을 모두 구해 AB 리스트에 저장하고, AB 리스트를 정렬한다...

https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 처음에는 부분수열의 합을 모두 구해서 개수를 세야 하나 했는데, n이 최대 40까지여서 계산을 최대 2^40번 해야하기 때문에 절대 아니구나 싶어서 고전하다가 내가 골1문제를 풀 수 있을리가 없다는 생각도 들고 해서 풀이를 봤다. 수열을 반으로 나누고 각각의 합을 구한 다음 정렬하고 왼쪽은 작은 값에서 큰 값으로 포인터를 증가시키고, 오른쪽은 포인터를 큰 값..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 벽을 최대한 적게 부수려면 빈 방 탐색의 우선순위가 벽 탐색의 우선순위보다 높아야 한다. 빈 방일 경우 append(), 벽일 경우 appendleft()를 해서 벽일 경우 최대한 늦게 방문하도록 구현하면 된다. 이걸 몰라서 backtracking처럼 계속해서 가지치기를 해야하나 고민했다. HTML 삽입 미리보기할 수 없는 소스 참고 1261번 풀이: https://velog..