본문 바로가기

백준 PS일지

 (101)
[백준/Swift] 144256: 접두사 찾기 | PS일지 문제 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 간단한 문제 요약 N개의 줄에 집합S에 포함된 문자열이 주어집니다. 그리고 다음 M개의 줄에는 검사해야 하는 문자열이 주어집니다. 검사해야 할 문자열 중에 S의 접두사에 적어도 한 개 이상 포함되는지 개수를 찾는 문제입니다. 예를들어 S = "codeplus", "cow"이고, M = "code", "co", "crud"일 때 code, co. 2개가 S의 접두사에 해당됩니..
[백준/Swift] 1245: 농장 관리 | PS일지 문제 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 간단한 문제 요약 농장에서 산봉우리마다 경비원을 배치하려고 합니다. 그래서 산봉우리의 개수를 구해야 합니다. 산봉우리란 같은 높이를 가지는 인접한 격자(x, y 좌표 차이가 1 이하인 경우)의 집합 이거나 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야 합니다. 고려해야 할 사항 산봉우리의 높이 차이는 예제 입력 1에서 1씩 차이가 날 수도 있고, 더 클 수 있습니다. ex) input: 3 1 1 3 1 ans: 1..
[백준/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] 24445: 알고리즘 수업 - 너비 우선 탐색 2 문제 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 간단한 문제 요약 시작 정점을 기준으로 주어진 정점을 탐색할 때 한 정점에서 갈 수 있는 여러개의 정점이 존재합니다. 이때 내림차순으로(큰 번호부터) 탐색을 이어나갑니다. 문제 풀이, 느낀점 var graph = Array(repeating: [Int](), count: n) _=(0..)} 또한 내림차순으로 탐색하기 위해서 문제에서 입력받은 노드의 크기를 내림차순으로 소팅해주면 됩니..
[백준/Swift] 12605: 단어순서 뒤집기 | PS일지 문제 12605번: 단어순서 뒤집기 스페이스로 띄어쓰기 된 단어들의 리스트가 주어질때, 단어들을 반대 순서로 뒤집어라. 각 라인은 w개의 영단어로 이루어져 있으며, 총 L개의 알파벳을 가진다. 각 행은 알파벳과 스페이스로만 www.acmicpc.net 간단한 문제 요약 Case별로 한 문장에서 space로 띄어쓰기 된 단어를 반대로 뒤집어라! 문제 풀이 LIFO(Last In First Out)의 특징을 지닌 stack으로 풀 수 있습니다. stack의 특성상 pop을 해야할 때 가장 최근에 stack의 list에 삽입된 top에 있는 원소가 pop됩니다. Swift 고차함수, reversed()를 통해서 아주 간단히 풀 수 있습니다. (1...Int(readLine()!)!).map{ print("Ca..
[백준/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..

티스토리툴바