본문 바로가기

분류 전체보기

 (115)
[C++] 백준 2565: 전깃줄 https://www.acmicpc.net/problem/2565 풀이입력을 받을 때 두 개의 전깃줄을 동시에 받으므로 vector 자료형의 pair를 통해 받은 뒤,정렬을 해주면 될 것 같았다.  정렬을 하고 ,dp[i] = i번째 전깃줄이 교차하지 않고 연결되어 있기위한 없애야 하는 전깃줄의 최소 개수로 가정하고 풀이를 떠올려봤는데 도저히 감이 안 잡혔다.  인터넷 검색을 통해 풀이를 슬쩍 봤는데,가장 긴 증가하는 부분수열을 활용하는 문제라고 나와있었다.그걸 보자마자 무릎을 탁 쳤다!!https://www.acmicpc.net/problem/11053  dp[i] = i번째까지 중 가장 긴 증가하는 부분수열의 길이로 하면이미 좌측 배열의 값은 정렬이 되어있는 상태이기에, dp[i] = i번째까지의 전..
[C++] 백준 2133: 타일 채우기 https://www.acmicpc.net/problem/2133 문제의 설명이 매우 단순하니만큼 시뮬레이션을 돌려봐야 할 거 같다는 생각이 들었다.dp[i] = 3 * i 크기의 벽을 타일로 채우는 경우의 수로 가정하고, 차근차근 N = 1부터 진행해보자. 풀이N = 12 * 1과 1 * 2의 타일로는 3 * 1을 채울 수 없다.즉 dp[1] = 0  N = 2 로 총 3가지의 모양이 나온다.즉 dp[2] = 3  N = 3역시 타일을 채울 수 없었다.여기까지 했으면 N에 홀수가 들어갈경우 dp배열의 값이 0이라는 걸 추측이 가능하다.  N = 4중앙을 기준으로 나눴을 때, dp[2] * dp[2] = 9라는 걸 알 수 있다.그럼 dp[4] = 9인걸까??? 답은 아니다이다.문제의 힌트를 유심히 보면4..
[C++] 백준 2225: 합분해 https://www.acmicpc.net/problem/2225 합이 N이 될 수 있는 경우의 수를 구하는 문제이다! 이 문제를 어렵게 하는 건 다음의 사항이었다.1. 0도 더할 수 있다.2. 한 개의 수를 여러 번 쓸 수 있다.   풀이일단 dp를 사용하면 될 것 같았다.1차원 dp를 n에 따라 사용해볼까 했지만,k라는 변수도 사용하려면 2차원 배열을 사용해야 될 것 같았다. 그래서 dp[i][j] = i개의 숫자를 사용해서 j가 되게 하는 경우의 수로 가정했다.  수학 아이디어가 좋아 점화식이 파바박 나오면 좋겠지만 그렇지는 않았다.그렇기에 일단 시뮬레이션을 돌려보기로 했다.N = 4, K = 4로 하고 시뮬레이션을 돌려봤다. K\N12341111122345336101544102035 무언가 규칙이..
[C++] 백준 2294: 동전 2 https://www.acmicpc.net/problem/2294 2293. 동전 1과 굉장히 유사한 문제이다.다른 점은 경우의 수를 구하는 것이 아니라 사용된 동전의 개수의 최솟값을 구하는 점 정도이다.  풀이도 굉장히 유사한 편이다.dp 배열의 값을 그 가치를 만드는 데 필요한 동전의 최소 개수로 지정해주면 매우 쉽게 풀 수 있다. 점화식은 다음과 같다dp[j] = min(dp[j-coin[i]] + 1, dp[j]);'원래 동전의 최소 개수'와 'i번째 코인을 사용했을 때의 개수 + 1'을 비교해서최솟값을 넣어주는 느낌이다.가치가 6일때를 비교해보면1원의 동전까지만 사용했을 경우 dp배열에 6이 들어가있다.5원의 동전까지 사용할 경우 min(dp[6-5] + 1, 6) = min(dp[1]+1, 6..
2024 UCPC 예선 후기 서론군인의 신분이지만 외출을 나가 UCPC 대회를 진행하고 왔다!부대 안에서의 알고리즘 대회는 나가봤지만, 이렇게 전국적인 알고리즘 대회는 처음 나가는 거라 걱정을 많이했다. 같이 나간 사람들은 학과 동기(znfnfns0365)와 비슷한 학과를 다니는 지인(jnary)과 나갔다.다들 최근에 알고리즘을 많이 하지 않았기에 진짜 경험만을 목적으로 나갔다. 과거 문제 유형을 살펴보니 평균 골드 상위에 다이아까지 난이도가 분포해있었다.문제 유형도 DFS, BFS, 이분 탐색 이쪽보다는 수학, 애드혹, 기하 등이 더 자주 나오는 것 같았다.세 명의 목표는 모두 1문제만 풀어보자였다.   대회중jnary가 앞쪽znfnfns0365가 가운데내가 뒤쪽을 푸는 걸로 정하고 대회에 들어갔다.  난이도가 높은 문제들이 가득..
[C++] 백준 1520: 내리막 길 https://www.acmicpc.net/problem/1520 지도가 주어졌고 끝 지점까지 탐색하는 문제이기에 DFS를 사용해야 됨을 인지했습니다. 다 탐색할경우 4^(500 * 500)이였기에 시간복잡도를 줄일 방법이 필요했고, 그에 따라 DP를 사용해야 되는 것까지는 인지를 했는데 어떤 식으로 접근할 지 고민이 됐습니다.  처음 접근은 'dp 배열의 값 =  이 지점까지 올 수 있는 경로의 개수'로 지정했습니다.dp[m][n]에 정답이 나오도록 한 것이죠. 하지만 DFS를 통해 끝지점에 도착한 뒤, 재귀를 통해 이전 배열의 값을 하나씩 구해가야 하는데,마지막 점에 도착했을 때 리턴 값을 뭐로 해야할 지가 참 난감했습니다. 마지막 값에서 이전 방향의 값들을 모두 더한다?근데 그럼 거기서 또 dfs를..
[C++] 백준 11504: 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 이 문제는 '11053. 가장 긴 증가하는 부분 수열 문제' or '11722. 가장 긴 감소하는 부분 수열 문제'를 풀어봤을 경우 매우 간단하게 풀 수 있다.  바이토닉 수열은 문제의 설명을 읽어봤을 때 증가하는 부분수열 + 감소하는 부분수열이다.그렇다면 가장 긴 증가하는 바이토닉 수열도 마찬가지라는 뜻이다.여기서 주의할 점은 가장 긴 증가하는 부분 수열의 길이와 가장 긴 감소하는 부분 수열의 길이를 더해서는 안된다는 것이다. 두 수열이 가장 길 때의 시점이 같지 않을 수 있기에,두 시점의 길이를 저장하는 배열을 따로따로 만들어줘야 한다.  숫자가 1개 존재할 때도 자기자신으로만 이루어진 수열이므로 모든 dp값의 초기값은 1로 설정한다..
[C++] 백준 2293: 동전 1 https://www.acmicpc.net/problem/2293 조건을 보면 시간 제한과 메모리 제한이 빠듯한 문제이다.그 점을 유의하지 않으면 몇 번이나 틀릴 수 있다 ㅠㅠㅠ   문제를 보면 n가지 종류의 동전으로 가치의 합이 k가 되도록 하는 경우의 수를 구하는 문제이다. 배열의 한 축을 가치의 합으로 두면 문제가 풀릴 거 같아 그대로 진행해봤다!처음에는 동전의 종류도 배열의 한 축으로 둬서 2차원으로 생각해봤는데 풀이가 영 생각이 나지 않아서,1차원으로 바꾸어서 진행했다.  먼저 예제를 통해 시뮬레이션을 돌려보자.1원이 되는 경우: 12원이 되는 경우: 1 1  / 23원이 되는 경우: 1 1 1 / 1 24원이 되는 경우: 1 1 1 1 / 1 1 2 / 2 25원이 되는 경우: 1 1 1 1 ..

티스토리툴바