본문 바로가기

programming

 (9)
[문제해결기법] 11. 동적 계획법 동적 계획법 (DP) 최적화 문제, 분할 정복 한 문제를 똑같은 문제이면서 크기만 작은 것으로 바꿀 수 있을지 생각해본다. 금화 모으기 문제 D[i][j] : (i, j)까지 오는 동안 모을 수 있는 금화의 최댓값 D[i][j] = max( D[i-1],[j] , D[i][j-1] ) + map[i][j]; 최대 공백 정사각형 (흰색으로만 이루어진 가장 큰 정사각형) mm 크기의 정사각형이 있다면, 4개의 (m-1)(m-1) 크기 정사각형이 있어야 한다는 점에서 착안한다. D[x][y]는 (x,y)가 가장 오른쪽 아래 꼭지점인 정사각형의 최대 크기라고 가정한다. (x,y)가 검은색이면, D[x][y] = 0 흰색이면, x==1 && y==1 : D[x][y] = 1 else : D[x][y] = min(..
[알고리즘] DP - 계단 오르기(cpp) N단의 계단이 있고, 한번에 계단을 한 단 또는 두 단을 올라갈 수 있다고 하자. 최대 두 군데의 계단에는 장애물이 있어서 올라갈 수 없다. 이 때 N단까지 올라가는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오. 입력 표준입력으로 세 정수 N A B가 주어진다. N은 계단의 단수로, 1 이상 30 이하이다. A와 B는 장애물이 있는 계단의 위치이다. A와 B는 0 이상 N 이하인 수이며, A와 B가 같을 수 있다. A, B 값이 0이라면, 이는 장애물이 없다는 뜻이다. 예를 들어 N, A, B가 3, 0, 1이라고 주어지면 총 3단의 계단이 있고, 장애물은 1단에만 있다. 조금 더 생각해보면 N, A, B가 3, 1, 0으로 주어져도 같다는 것을 알 수 있다. 출력 표준출력으로 하나의 정수를 출력..
[C++/BOJ] 10942 : 팰린드롬? (DP) https://www.acmicpc.net/problem/10942 문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자. S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다. S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다. S = 3, E = 3인 경우 1은 팰린드롬이다. S = 5, E = 7..
[C++/BOJ] 12865 : 평범한 배낭 (DP) / 테스트케이스 포함 https://www.acmicpc.net/problem/12865 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 100..
[C++/BOJ] 1890 : 점프 (DP) https://www.acmicpc.net/problem/1890 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 게임 판의 크기 N..
[C++/BOJ] 9251 : LCS (DP) https://www.acmicpc.net/problem/9251 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 백준 골드5티어. 처음에 시간제한이 0.1초길래 완탐으로는 못풀겠구나 했는데 역시 틀림 그래서 얌전히 DP로 해결했습니다.. 점화식을 떠올리기 힘들었는데, 한 블로거의 잘 정리된 글을 읽고 이차원..
[C++/BOJ] 9465 : 스티커 (DP) https://www.acmicpc.net/problem/9465 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작..
[DB] SQL Programming⌨️ (1) Database Programming 목표 : 대화형 인터페이스가 아닌 응용프로그램에서 DB에 접근 왜? : 편리하지만 불충분하고, 대부분이 응용 프로그램에서 만들어짐 DB programming Approaches (접근방법) 임베디드 함수 라이브러리 (API) 새 언어 : DBPL (Database Programming Language) → 불일치를 최소화할 수 있음 Impedance Mismatch : 임피던스 불일치 호스트 언어와 DB모델 사이의 비호환성 Typical sequence of interaction in DB Programming 클라이언트 프로그램이 DB서버와의 연결을 open 클라이언트 프로그램이 질의어를 보냄 DB접근이 필요없어지면 접속 종료 Embedded SQL COBOL, C..
728x90

티스토리툴바