알고리즘

[알고리즘] 구간 합, 누적 합(Prefix Sum)

목차 누적 합이란? 언제 사용할까? 예시 및 코드 누적 합이란? 누적 합이란 수열 An에 대해서 각 인덱스까지의 구간의 합을 구하는 것을 누적 합이라고 합니다. 예를 들어 [1, 2, 3, 4, 5] 라는 배열이 있을 때, 각 구간까지의 합을 구하는 배열인 [ 1, 3, 6, 10, 15] 을 구한다고 가정해보면 아래와 같이 2가지로 구할 수 있습니다. [ 첫번째 방법 ] 1 1+2 1+2+3 1+2+3+4 1+2+3+4+5 매번 현재 인덱스까지의 값을 반복하며 더해주기 [ 두번째 방법 ] 1 1+2 3+3 6+4 10+5 이전 인덱스까지의 누적합에 현재 값을 더해주기 어떤게 더 효율적일까요? 배열의 갯수인 n을 늘려 [1, 2, ..., 99999, 10000]로 비교해보겠습니다. [ 첫번째 방법 ] ..

[백준] BOJ-14889 스타트와 링크

문제 문제 풀이 알고리즘 스터디 1주차 문제로, DFS, 백트래킹 알고리즘으로 접근하며 문제풀이를 시작했다. 백트래킹은 "DFS를 기반으로 하며, 어느 정도의 Depth 에 도달하면 탐색을 중단 하는 알고리즘" 정도로 이해하고 접근했다. n이 무조건 짝수로 제공되고, 절반 씩 팀을 나누기 때문에 dfs로 순차 탐색을 진행하다가 n / 2 일 경우 탐색을 중단하고 팀원을 구성하도록 했다. 두 팀간의 능력치 차이가 가장 적은 경우의 능력치 차이를 출력하는 문제이기에 result 변수의 초기값을 Int.max 로 설정해둔 후, min() 과 abs() 함수를 사용해 두 팀 간의 능력치 차이를 구하고 result 와 비교해 더 적은 값으로 업데이트 하도록 했다. import Foundation let n = I..

[프로그래머스] PRG-JadenCase 문자열 만들기

# PRG-JadenCase 문자열 만들기 문제 정리 풀이 func solution(_ s:String) -> String { let s = s.components(separatedBy: " ") var words: [[Character]] = [] var upperWords: [[Character]] = [] var upperSentences = "" // 전체 소문자로 변경 // [String] -> [[Character]] 로 변경 s.map { $0.lowercased() }.forEach { words.append(Array($0)) } // 첫 글자만 대문자로 변경 words.forEach { word in var upperWord: [Character] = [] for i in 0.. [[C..

[백준 BOJ] BOJ -2309 일곱 난쟁이

#2309 일곱 난쟁이 문제 정리 9개의 Int 배열에서 2개를 뺐을 때 합이 100이 되는 경우를 찾는 문제입니다. 풀이 import Foundation var heights: [Int] = [] var output: [Int] = [] var sum: Int = 0 // 일곱 난쟁이가 아닌 사람들의 키 var a: Int = 0 var b: Int = 0 // 엔터로 입력 받기 for _ in 0..

[백준 BOJ] BOJ-1018 체스판 다시 칠하기

#1018 체스판 다시 칠하기 문제 정리 풀이 import Foundation // 정답 체스판 경우의 수 var correctBoard1: [[Character]] = [] var correctBoard2: [[Character]] = [] for _ in 0..

[백준 BOJ] BOJ-8393 합

#8393 합 문제 정리 풀이 import Foundation let n = readLine()!.split(separator: " ").map { Int($0)! } var sum = 0 for i in 1...n[0] { sum += i } print(sum) 1 부터 n까지 for문으로 sum 구하기 풀고나서 알게된 것 reduce 쓰면 숏코딩도 가능할 것 같은데 아직 실력이 모자라다ㅜㅜ

[백준 BOJ] BOJ-7568 덩치

#7568 덩치 문제 정리 풀이 import Foundation let n = Int(readLine()!)! var persons = [(weight: Int, height: Int)]() // 입력 받기 for _ in 0..

[백준 BOJ] BOJ-1920 수 찾기

#1920 수 찾기 문제 정리 풀이 import Foundation let n: Int = Int(readLine()!)! let numList: Set = Set(readLine()!.split(separator: " ").map { Int($0)! }) let m: Int = Int(readLine()!)! let findList: [Int] = readLine()!.split(separator: " ").map { Int($0)! } findList.forEach { print(numList.contains($0) ? 1 : 0) } set.contains() 를 활용하여 값이 numList에 들어있는지 비교 시간복잡도는 O(n) 풀고나서 알게된 것

[백준 BOJ] BOJ-1059 좋은 구간

#1059 좋은 구간 문제 정리 풀이 import Foundation let l = Int(readLine()!)! let s = Set(readLine()!.split(separator: " ").map { Int($0)! }) let n = Int(readLine()!)! var min = 1 var max = 1000 // 0. n이 집합 S에 속하는 경우 if s.contains(n) { min = n max = n } else { // 0. n-1 방향으로 진행하면서 집합 S와 일치하는 값이 있으면 직후의 값을 min에 저장 for i in stride(from: n, through: 1, by: -1) { if s.contains(i) { min = i+1 break } } // 0. n+1 ..