본문 바로가기

백준 PS일지/DynamicProgramming

 (15)
[백준/Swift] 1890: 점프 | PS일지 문제 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 간단한 문제 요약 n*n의 게임판 가장 왼쪽 위에서부터 시작해서 게임판의 숫자만큼 오른쪽 또는 아래칸으로 점프할 수 있다. 점프할 때 방향 바꿀 순 없다. (0,0)에서 출발해서 (n-1,n-1)까지 가는 모든 경우의 수를 구하시오!! 문제 풀이, 느낀점 typealias Point = (x:Int, y:Int) let direction = [(0,1),(1,0)] var n = Int(readLine()!)! var ans = 0 var gra..
[백준/Swift] 14728: 벼락치기 | PS일지 문제 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 간단한 문제 요약 일정 시간 이상을 들이면 해당 단원의 시험을 맞을 수 있다고 가정했을 때(대박,,일정 시간 투자만 하면 된다니) 시험의 단원 개수와 시험까지 공부할 수 있는 총 시간이 주어졌을 때, 특정 단원을 공부할 수 있는 시간과 그 단원을 공부했을 때 배점이 최대가 되는 경우를 구하시오! 문제 풀이 시험까지 공부할 수 있는 총 시간이 10000 밖에 안되서 2차원 dp로 풀었습니다. 주어진 최대 시간까지!!..
[백준/Swift] 9252: LCS2 | PS일지 문제 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 간단한 문제 요약 LCS(Longest Common Subsequence). 최장 공통 부분 수열은 두 문자열 간 가장 긴 공통된 문자열을 찾는 것이다. 문제 풀이 문자열1: ABTD 문자열2: ABCD 두 문자열이 있다면 LCSubsequence는 ABD입니다. 하지만 LCSubstring의 경우 AB(연속적인 부분 문자열)입니다. Longest Common Substring의 경우 (관련 문제 포스트가 있..
[백준/Swift] 5582: 공통 부분 문자열, LongestCommonSubsequence, LongestCommonSubstring차이 | PS일지 문제 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 간단한 문제 요약 두 문자열이 주어졌을 때 공통으로 가장 긴 부분 문자열의 길이를 출력하시오. 고려해야 할 사항 Longest Common Subsequence VS Longest Common Substring 의 개념을 알면 좋은 것 같습니다. 전자의 경우 공통으로 있는 문자열들의 가장 긴 수열을 의미합니다. 후자의 경우 공통으로 있는 연속된 문자열들 중 가장 긴 문자열을 의미합니다. 예를들어 문자열1: ABACD 문자열2: ABTCD LCSu..
[백준/Swift] 7579: 앱. 문제 뿌수기!! | PS일지 문제 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 간단한 문제 요약 스마트폰에서 화면은 작다. 보이는 화면에서 '실행중'인 앱은 한 개 이지만, 더 많은 앱이 '활성화' 되어있다. 활성화 된 앱은 system resource memory를 사용한다. 한 번이라도 실행됬던 앱들을 종료하지 않는 이상, 이미 활성화 된 앱으로 분류된다. 새로운 앱을 실행시켜야 하는데 이미 활성화 된 앱은 각각의 메모리를 점유하고 있다. 활성화 상태의 앱을 비활성화 시키면 특정 앱이 소유하고 있던 메모리가 반환되어 사용할 수 있다. 하..
[백준/Swift] 3067: Coins | PS일지 문제 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net 간단한 문제 요약 동전의 종류(1원, 5원, 10원, 50원 ...)가 주어질 때 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오! 문제 풀이 1,2,3원으로 6원 만드는 모든 경우의 수 구하는 방법 주어진 동전: 1,2,3 6원을 만드는 모든 방법을 구하는 방법을 어떻게 구할 수 있을까요? 1 + 1 + 1 + 3 1 + 2 + 3 3 + 3 ... 6원보다 작은 3원 먼저 만들기 우선 문제를 쪼개 6이 아닌 3을 구하는..
[백준/Swift] 2096: 내려가기 | PS일지 문제 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 간단한 문제 요약 첫 줄에서 마지막 줄로 내려가는 게임이다. 맨 첫 줄의 시작은 별표의 위치이다. 그리고 각각의 칸에는 숫자가 있다. 위 층(별표)에서 아래층으로 내려갈 수 있는 경우는 각각의 별표 아래 동그라미 친 경우 이다. 마지막 줄로 내려갔을 때 얻을 수 있는 (방문한 칸 숫자 누적 합산)최대, 최소 점수를 구하시오!! 문제 풀이, 했갈렸던 점 어떻게 하면 문제를 풀 수 있을까? 고민했습니다. 그래프 형식의 input만 보면 dfs, bfs가 자꾸 생각나네요. d..
[백준/Swift] 11048 : 이동하기 문제 뿌수기!! + dp테이블 구하기!! BOJ_11048.swift 11048 : 이동하기/ 문제 소개 풀이 과정 코드 구현 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 11048 : 이동하기 / 문제 소개 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방(1,1) //준규가 있는 위치 미로의 가장 오른쪽 아랫 방 (N,M) // 준규가 이동해야 할 위치 각 방은 사탕이 있다. 준규는 (r,c)에 있다면, (r+1,c), (r,c+1),(r+1,c+1)로 이..

티스토리툴바