→ Problems

문제 소개난이도가 어려워질수록 문제 자체는 간단해지는 느낌이 든다. 히스토그램이 주어지고 넓이가 가장 큰 직사각형을 구하는 프로그램을 작성하는 문제이다.문제 풀이나는 스택을 활용하여 풀었다. 아래와 같은 히스토그램이 있다고 생각해보자.아래와 같이 stack의 마지막 요소의 높이가 추가하려는 높이보다 작다면 stack에 append해준다.마지막은 이제 4번째 인덱스가 3번째 인덱스의 높이 4보다 낮은 상황이다. 이제 이 상황에서 로직을 사용하게 된다. 넣으려는 요소의 -1을 하면 앞에 쌓인 블록들의 width가 나온다. 이것을 현재 블록의 높이, 블록의 인덱스의 차이를 이용하여 넓이의 최댓값을 갱신해준다. 만약 pop하고 마지막 값이 없다면 그냥 width를 곱해주면 된다.pop하는 값의 높이가 추가하려는..

문제 소개유명한 다이나믹 프로그래밍 문제인 LCS(Longest Common Subsequence) 문제를 풀어보았다.문제 풀이 [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common SubsequenceLCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.velog.io이 블로그... 너무 설명을 잘해주셨다. 아래와 같이 Subsequence를 탐색하면 된다.1. LCS 2차원 배열 선언2차원 배열을 선언해준다. first와 second의 첫글자를 가져와서 변수명을 지었다.let f = Array(readLin..

문제 소개피보나치를 구하는 방법은 재귀, dp등 다양하지만 이 문제는 n의 범위가 10^18 인 무시무시한 문제다. 당연 O(n)으로 문제를 푼다면 틀리게 된다.문제 풀이이 문제는 좀더 수학적으로 접근해야 한다. 우선 너무나도 유명한 피보나치 수열의 일반항은 아래와 같다.이것을 행렬로 나타낸다면 아래와 같이 나타낼 수 있다.오른쪽을 쭈우우우욱 풀어준다면... 아래와 같이 결국 표현된다. 이제 우리는 행렬의 n-1 제곱만 구해주면 된다!2x2 행렬의 곱은 아래와 같이 구할 수 있다.func multiply(_ a: [[Int]], _ b: [[Int]]) -> [[Int]] { let x = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod let y = (a[0][0] *..

문제 소개사실 문제를 처음보고 이해를 못했는데 🥲 예시를 보고 이해가 되었다.과정은 다음과 같다.좌표를 오름차순으로 정렬하고, 중복되는 값을 제거해준다.원래 배열에 1번에서 만든 정렬된 배열의 인덱스로 바꾼뒤 출력해준다.문제 풀이아래처럼 nums를 Set으로 만들어 준 뒤, 정렬했다.// Set로 만들어주는 부분!let arr = Set(nums).sorted()아래와 같이 딕셔너리를 만든다// 인덱스를 value, 배열의 값을 key로 딕셔너리 자료구조로 만들기let dic = Dictionary(uniqueKeysWithValues: arr.enumerated().map { ($1, $0) })정답 코드import Foundationlet n = Int(readLine()!)!var nums = r..

문제 소개문제 풀이사실... 이 문제는 의외로 간단하게 풀렸다. 😇하위 팀들 조건 판별우선 점수들을 오름차순으로 정리하고, 하위 팀들끼리 경기를 한다고 가정해보자. 하위 팀들끼리 경기를 한다고 가정한다면 최소한의 가져가야 하는 점수가 있다. 총 k개의 팀이 있다면 (k - 1) * k / 2 의 점수는 최소한 있어야 한다. 그 조건을 만족하지 않으면 -1을 출력하고 프로세스를 종료했다.for k in 1..총 점수 합 판별마지막 n개의 팀에서는 n * (n - 1) / 2 가 총합이여야 한다.if scores.reduce(0, +) != n * (n - 1) / 2 { print(-1) exit(0)}이 두개의 조건을 만족해주면 주어진 점수들은 유효한 점수이다.정답 코드import Found..

문제 소개월요일을 기념하며... 약간은 풀만한 문제(?)에 도전했다..! 문제에 친절하게도 재귀적으로 방문한다는 힌트가 있다! 🥸문제 풀이재귀적으로 어떻게 구할 수 있을까? 고민해봤다. 아래와 같은 형태가 반복되지 않을까? 함수로 치면 어느 사분면에 있는지 판단 한 후 그것을 계속 잘게 잘게 쪼개서 구하는 방식으로 재귀적으로 구하면 될 것 같았다.그림으로 이해가 될지는 모르겠지만... (x, y)를 구했다면 x의 경우 (블록 * 2), y의 경우 (블록 * 1)을 곱해줘서 몇번째 순서인지 계속 쌓아나가면 된다!import Foundationlet nrc = readLine()!.components(separatedBy: " ").map { Int($0)! }let (n, r, c) = (nrc[0], ..

문제 소개풀이 과정아주아주 단순하게 문제에 접근하면 아래와 같이 할 수 있을 것이다. 단순히 table을 만든 후 아래처럼 입력값에 따라서 성실하게(?) 답변을 구현한다. 물론 이렇게 풀게된다면 M 100,000이고, N 1,024일때 최악의 경우 1,024 x 1,024 x 100,000번 연산을 해야하기 때문에 시간초과다. ☠️import Foundationlet nm = readLine()!.components(separatedBy: " ").map { Int($0)! }let (n, m) = (nm[0], nm[1])var table = [[Int]]()for _ in 0..어떻게 이문제를 해결 할 수 있을까? 아래와 같은 개념을 사용하면 된다. dp로 [1][1]부터 [i][j]의 누적합을 구하..

문제 소개풀이 과정모든 도시를 순회하게 된다면 n!의 경우의 수가 있으므로 16! = 20조 정도의 경우의 수가 나오니 모든 경우의 수를 순회하는 것은 불가능하다. dp와 비트마스킹을 통해서 방문한 곳을 확인해야 한다. 또한 기존의 순회의 개념을 그대로 가져와서 dfs를 활용하기로 했다.  아래 부분이 메인 로직이라고 할 수 있는데, var dp = Array(repeating: Array(repeating: 16_000_000, count: 1 이러한 식으로 dp를 선언해주고 만약 4개의 노드가 있는 그래프라면 dp[0][0001]을 생각해보면  dp[2][0101]에서의 최솟값 + 0 → 2 로 가는 비용이 될 것이다. for i in 0.. 첫번째 풀이아래와 같이 문제를 풀었지만... 시간초과..