→ Problems

🏁 문제 소개💡 문제 풀이가장 먼저 문제를 보고 생각난건 트리구조였다. 결국 -1, +1 두개의 자식노드로 numbers의 크기의 깊이만큼 들어가는 트리구조로 생각했다. [4, 1, 2, 1] 같은 경우는 아래 상태로 나타낼 수 있을 것 같다.DFS재귀함수를 활용하여 깊이우선탐색을 구현했다.func solution(_ numbers: [Int], _ target: Int) -> Int { dfs(numbers, target, 0, 0)}func dfs(_ numbers: [Int], _ target: Int, _ sum: Int, _ depth: Int) -> Int { if depth == numbers.count { return sum == target ? 1 : 0 ..

🥸 문제 소개오랜만에 코딩테스트 연습을 해보려고 아래의 문제를 간단하게 풀어보기로 했다.🤔 문제 풀이오랜만에 행렬을 마주하니 생각보다 시간이 조금 걸렸던듯... 행렬이 가물가물 했었다. 아래의 식을 활용하여 간단하게 코드를 작성할 수 있었다.func solution(_ a: [[Int]], _ b:[[Int]]) -> [[Int]] { let m = a.count let n = a[0].count let p = b[0].count var ans = Array(repeating: Array(repeating: 0, count: p), count: m) for i in 0..🔥 추가 학습아니 행렬은 너무너무너무나도 유용하고 유명한 수학 연산인데 Swift에서 기..

문제 소개난이도가 어려워질수록 문제 자체는 간단해지는 느낌이 든다. 히스토그램이 주어지고 넓이가 가장 큰 직사각형을 구하는 프로그램을 작성하는 문제이다.문제 풀이나는 스택을 활용하여 풀었다. 아래와 같은 히스토그램이 있다고 생각해보자.아래와 같이 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], ..