문제https://www.acmicpc.net/problem/16916 입력s: String = 문자열pattern: String = S의 부분 문자열인지 확인해야할 pattern1 결과ans: Int = 부분문자열이 맡다면 1 아니면 0해석문자열과 패턴이 최대 100만가까이 되는걸 보니 브루투스 포스 brute-force  방식으로는 해결이 불가능해보인다.이 문제는 문자열에서 특정 패턴을 찾아내는 전형적인 kmp 문제  1) lps 배열을 구한 후 2) kmp 를 진행한다. 코드import Foundationfunc computeLPS(_ pattern: [Character]) -> [Int] { let n = pattern.count var lps: [Int] = [Int](rep..

문제https://www.acmicpc.net/problem/11724 입력n: Int = 정점의 개수m: Int = 간선의 개수u: 간선의 정점1v: 간선의 점점21 결과ans: Int = 그래프에 존재하는 연결 컴포넌트 개수해석제공된 간선 정보를 이용해서 인접 행렬을 채운다.이후 dfs를 통해 방문여부를 갱신하여 중복하여 방문하는 문제를 해결한다.코드import Foundationlet nm = readLine()!.split{$0 == " "}.map{Int($0)!}let (n, m) = (nm[0], nm[1])var adj: [[Int]] = [[Int]](repeating: [], count: n+1)for _ in 0..

문제https://www.acmicpc.net/problem/2667입력n = 지도의 크기 (가로 세로 크기)board: [[Character]] = [] , "0"과 "1"로 구성됨 board[i] = "0" = 집이 없는 곳board[i] = "1" = 집이 있는 곳5결과ans: Int = 단지 수 단진 내 집의 수를 오름차순으로 정렬 후 한줄 씩 출력해석2중 반복문을 돌며 집이 존재하고, 아직 방문한 적이 없다면 새로운 단지 이 때 dfs로 들어가면서 연결된 모든 집을 하나의 단지로 인식하고 방문하며 count하자. 코드import Foundationlet n = Int(readLine()!)!var board: [[Character]] = []for _ in 0.. Int { visited[..

문제https://www.acmicpc.net/problem/1450입력n: Int = 물건의 개수c: Int = 가방의 용량arr: [Int] = 물건의 무게들1 결과ans: Int = 가방에 넣는 방법의 수해석n이 크지 않아 조합으로 도전하려 했지만  ({{30}C_1} ~ {{30}C_{30}}) 까지 구한다고 하면 너무 많은 시간이 걸릴 것같아 실패했다. 여기서 비슷하게 느꼇던 문제가 생각났는데 바로 아래 문제다. 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 이 문제는 두 플레이어가 주사위들을 나눠가진 후 그 주사위 눈들의 합을 합쳐 승/무/패를 계..

문제https://www.acmicpc.net/problem/1806 입력n: Int = 수열의 길이s: Int = 부분합 기준arr: [Int] = 수열10 결과ans: Int = 부분합이 s이상이 되는 것 중 가장 짧은 길이해석왼쪽부터 오른쪽으로 한칸씩 전진하며 sum이 s이상이 되었을 때 길이를 저장하고왼쪽 포인터를 하나 움직여 sum을 다시 낮춰준다.코드import Foundationlet ns = readLine()!.split{$0 == " "}.map{Int($0)!}let (n,s) = (ns[0], ns[1])let arr = readLine()!.split{$0 == " "}.map{Int($0)!}var dist: Int = Int.maxvar left: Int = 0var right..

문제https://www.acmicpc.net/problem/2470입력n: Int = 전체 용액 수 arr: [Int] = 용액 특성 값2 결과ans: (Int,Int) = 두 용액의 합이 0에 가까운 조합해석두 용액이라는 말과 n의 길이가 십만 정도인 걸 보면 정렬 후 투포인터로 찾아가면 될 것 같다 두 용액의 합이 현재 gap보다 작으면 업데이트두 용액의 합이 음수일 경우 left를 오른쪽으로 두 용액의 합이 양수일 경우 right를 왼쪽으로 이동시키면 될 듯하다.코드import Foundationlet n = Int(readLine()!)!let arr = readLine()!.split{$0 == " "}.map{Int($0)!}.sorted()var left = 0var right = n-1..