⭐️ Computer Science/PS

[PS] DP - LIS 11053 가장 긴 증가하는 부분수열

// LIS DP 공식 let n = Int(readLine()!)! let aList = readLine()!.split(separator: " ").map { Int($0)! } var dp = Array(repeating: 1, count: n) // 배열을 순회하면서 각각의 인덱스를 비교해서 어떤 기준값보다 큰 값이 있으면 기준값을 수정해주는 과정 for i in 1..

[PS] 백트래킹 - n과m(9) 15663 어려움 시간초과 이슈 악

15663 (9) 시간초과 이슈 8개 중 8개를 고를 수 있어서 8^8 시간복잡도인데 내가 푼 방식은 contains 부분에서 시간복잡도가 추가로 증가하게 된다. 그래서 시간초과 이슈가 생긴다.import Foundation let nm = readLine()!.split(separator: " ").map { Int(String($0))! } let n = nm[0] let m = nm[1] var array = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted(by:

[PS] 백트래킹 20문제 풀기 - 0. 개념, 1. n과m(1) ~ (4)

앞으로 4/17~23 이번주는 백트레킹 문제만 조지기로 다짐했다. 이번주 20문제를 풀고 익혀보자. 이번주 헤치울 문제들 https://www.acmicpc.net/step/34 백트레킹 개념 정리 모든 경우의 수를 전부 고려하는 알고리즘으로 답이 될 수 없는 후보는 더이상 탐색하지 않고 다시 돌아가는 알고리즘 모든 경우의 수를 전부 다 고려하는 브루트포스 (완전탐색)보다 더 시간을 절약할 수 있다. 완전탐색의 대표적인 방법 중 하나가 DFS로, 재귀를 이용해서 현재시점에서 방문할 곳을 탐색하고 방문한다. 반면, 백트래킹은 비효율적인 경로를 차단하고 목표지점에 도달할 수 있는 가능성이 존재하는 곳만 탐색해서 가지치기라고 부른다. 백트레킹은 BFS나 DFS와 함께 구현한다. 그러나 해당 노드가 조건에 부합..

[PS] BOJ - 7576 토마토 골드5

처음에 파이썬으로 풀었던 문제라 swift로 바꾸는 것은 쉽지 않았는데 시간초과 문제가 발생했다. 파이썬은 큐 라이브러리를 제공해주는 점과 다르게 swift는 큐가 제공되지 않는데 그 과정에서 removeFirst를 쓰는 부분이 문제였다. 맨 앞 요소를 삭제하면 각 요소들이 하나씩 앞으로 이동하는데 그러면 시간복잡도가 O(n)으로 시간초과가 발생하게 된다. 그러면 어떻게 해야 하냐? 기존에 removeFirst를 통해서 가장 맨 앞 요소를 삭제하고 -> 인덱스가 하나씩 당겨졌을 것이다. 이 대신에 index를 통해서 큐의 원소에 접근하는 방법을 사용하면 된다. index는 0부터 시작이고, queue.count는 1부터 개수를 센다. 그래서 index가 더 커지는 while문을 벗어나는 방식으로 구현해주..

[PS] 3/2 - BOJ 2644 촌수계산 - DFS

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 나는 촌수계산하려면 각각 노드 간 깊이를 계산해줘야 되니까 DFS가 먼저 떠올랐는데 다른 사람들은 BFS로 풀었다고 한다. 왜 BFS라고 생각을 했을까? DFS랑 풀이법은 비슷한데 큐에 튜플을 통해서 (시작노드, cnt)를 넣어준 것이 BFS 특징 이렇게도 풀 수 있다는 걸 익혀야겠다. 우선, 하나씩 x = 7인 경우부터 노트에 다 그려보면서 이해를 했다. depth의 경우, ..