본문 바로가기

알고리즘100

[백준/C,C++] 10942번: 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 1, 2, 1, 3, 1, 2, 1로 예를 들어보겠습니다. S = 1, E = 7일 경우 1과 1이 같고 그 중간 범위인 2, 1, 3, 1, 2가 팰린드롬이면 팰린드롬입니다. S = 2, E = 6일 경우 2와 2가 같고 그 중간 범위인 1, 3, 1이 팰린드롬이면 팰린드롬입니다. S = 3, E = 5일 경우 1과 1이 같고 그 중간 범위인 3이 팰린드롬이면 팰린드롬입니다. 수가 하나일 경우 무조건 팰린드롬이므로 S = 1, .. 2021. 7. 5.
[백준/C,C++] 1520번: 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 해당 문제를 보고 DFS, BFS문제구나 생각을 했습니다. 관건은 동적계획법을 사용해 어떻게 연산 수를 줄이는 것인가인데 다른 고수분들의 풀이를 보고 참고해 풀었습니다. DP[y][x] = 현재 지점의 좌표가 y, x일 때, 끝지점에 도달할 수 있는 경로의 개수로 가정하고 이를 사용한다면 탐색의 횟수를 줄일 수 있습니다. 예제를 통해 적용해보겠습니다. 최초 출발 지점인 50에서 10으로 갈 수 있.. 2021. 7. 4.
[백준/C,C++] 11049번: 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 개인적으로 11066번: 파일 합치기와 비슷한 문제라 느꼈습.. 2021. 7. 4.
[백준/C,C++] 11066번: 파일 합치기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 문제 예제인 40, 30, 30, 50을 보겠습니다. DP[start][end]를 start부터 end까지 합치는 최소비용이라 하고, psum[i]를 0부터 i까지의 파일을 합치는 데 드는 비용이라 했을 때 40, 30, 30, 50의 최소 비용은 다음과 같이 나타낼 수 있습니다. DP[1][4] = min(DP[1][1] + DP[2][4], DP[1][2] + DP[3][4], .. 2021. 7. 4.

티스토리툴바