728x90 분류 전체보기307 백준 11053번 가장 긴 증가하는 부분 수열 C++ 1. 문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성해라10 20 10 30 20 50인 경우 부분 수열은 10 20 30 50으로 나타낼 수 있으며 길이는 4이다.첫쨰 줄에는 수열 A의 크기가 주어지고둘째 줄에는 수열 A를 이루고 있는 집합이 주어진다.첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제이다. DP알고리즘의 바텀업 방식으로 해당 문제를 풀이할 수 있다.for문 i번째 값을 수열의 가장 큰값으로 기준으로 하고다음 for문으로 j번째 값과 비교해 i번째 값보다 작은 경우 dp 벡터의 i번째 값을 + 1을 하여준다.dp 벡터는 A의 크기로 모든 값을 1로 초기화하여 선언한다.(첫번 째 값은 무조건 들어갈 수있으니 최소 길이가 1이기.. 2025. 4. 22. 백준 1904번 01타일 C++ 1. 문제 설명각각의 타일에 0 또는 1이 쓰여 있는 낱장의 타일이 있다.0이 쓰여진 낱장의 타일을 붙여 한쌍으로 이루어진 00타일을 만들어1하나만 쓰여있는 타일과 00으로 이루어진 한쌍의 타일만이 남았다.타일을 이용해 길이가 N인 모든 2진 수열을 만들 수 없게 되었다.N = 1일때는 1만 만들 수 있고, N = 2일 떄는 00, 11 을 만들 수 있다.N이 주어졌을 때 만들 수 있는 모든 가짓수를 세는 문제로, 타일의 개수를 무제한이다. 길이N이 주어졌을 때 00, 1 타일을 조합하여 만들 수 있는 최대 가짓수를 구하는 문제이다.00은 두칸으로 계산한다. N = 1 1개N = 2 2개N = 3 3개N = 4 5개N = 5 8개로점화식은 N = (N - 1) + (N - 2)로 계산이 가능하게 된다.하.. 2025. 4. 21. 백준 15684번 사다리 조작 C++ 1. 문제 설명사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다.인접한 세로선 사이에는 가로선을 그을 수 있는데각각의 세로선 마다 가로선을 그을 수 있는 위치의 개수를 H이고모든 세로선이 같은 위치를 갖는다. 가로선은 연속하거나 서로 접하게 그을 수는 없다.주어진 사라디에 가로선을 추가하여 사다리 게임의 결과를 조작하려고 하는데 i번 세로선에서 출발하면 i번 세로선으로 도착하도록 할려고 한다.그렇게 사다리를 조작하였을 때 추가해야 하는 가로선의 최솟값을 구하는 프로그램을 작성해라단 그을 수 있는 가로선은 4개 이상 나올 수 없으며 4개 이상 나온다면 -1을 출력해라 첫째 줄에 세로선 N, 가로선의 개수 M, 그을 수 있는 가로선 위치 개수 H가 주어진다.가로선의 정보는 두 정수 a와 b로 나.. 2025. 4. 19. 백준 1941번 칠공주 C++ 1. 문제 설명총 25명의 여학생으로 이루어진 반은 5x5의 정사각형 격자 형태로 자리가 배치된다.얼마 지나지 않아 Y와 S파로 갈라지게 되었고,S파가 세력을 확장하며 Y파를 탄압하기 시작했다. 위기 의식을 느껴 현재의 체제를 포기하고, 두 파가 서로 협의하에 소문난 칠공주를 결성하여 관리하기로 하였다.칠공주는7명의 여학생으로 구성되어지며,강한 결속력을 위해 가로,세로로 서로 인접한 자리를 유지한다.화합과 번영을 위한 공동 관리로 들어올 수 있는 사람의 파는 중요하지 않지만, S파가 Y파보다 반드시 더 많아야 된다 즉 4명 이상 포함 되어야 한다 자리 배치도가 주어졌을 때, 소문난 칠공주를 결성할 수 있는 모든 경우의 수를 구하는 문제이다.. 해당 문제는 dfs와 백트래킹을 이용해 25명중 7개의 .. 2025. 4. 19. 이전 1 2 3 4 ··· 77 다음 728x90
