본문 바로가기

프로그래밍116

[백준/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.
[OpenCV/악보인식] 광학 음악 인식 기반 자동 편곡 시스템 - 5 인식 과정 3 - 객체 인식 객체에 대한 인식 과정은 앞서 말했듯 완전 주먹구구식으로 객체가 가진 구조적 특징을 하나 하나 분석해 알고리즘을 짜 맞추었습니다. 예를 들면, 4분음표는 하나의 기둥을 가지고 있고 머리가 검은색으로 채워져 있다는 특징이 있습니다. 객체에서 기둥, 머리, 꼬리, 점에 해당하는 요소를 탐색한 후 4가지 요소를 조합하면 모든 음표를 구분할 수 있습니다. 기둥 머리 꼬리 점 온음표 X X X X 점온음표 X X X O 2분음표 O X X X 점2분음표 O X X O 4분음표 O O X X 점4분음표 O O X O 8분음표 O O 1 X 점8분음표 O O 1 O 16분음표 O O 2 X 점16분음표 O O 2 O 해당 객체가 무슨 음표인지 구분하는 것으로 박자에 대한 정보를 알 수 있.. 2021. 5. 27.

티스토리툴바