전체 글

문제 소개풀이 과정모든 도시를 순회하게 된다면 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.. 첫번째 풀이아래와 같이 문제를 풀었지만... 시간초과..

Segment Tree 란?세그먼트 트리는 범위 데이터의 조회, 업데이트에 효과적인 자료구조이다. 이진트리의 형태로 바로 O(logN)의 시간복잡도를 가지게 된다. 가장 많이 쓰이는 것은 특정 범위 내의 요소들에 대한 합계, 최솟값, 최댓값을 검색하고 처리할 수 있다. Segment Tree 만들기만약 [1, 2, 3, 4, 5] 와 같은 배열이 있다고 해보자. 이것을 Segment Tree 자료에 넣어 합계를 쉽게 검색하고 싶다. 어떻게 해야 할까? 이진트리의 기본 개념처럼 계속 반으로 쪼개서 저장해 주면 된다. 하지만 우리가 원하는 것은 합계 뿐... 아래처럼 저장해 주면 Segment Tree 끝!이다. 참 쉽죠? 이것을 코드로 구현해 보자. Segment Tree를 만들기 위한 고민Tree의 크기..

문제 소개https://www.acmicpc.net/problem/11689 풀이 과정자연수의 범위가 10^12이다. 절대로 1부터 순회해서 서로소를 구할 수 없다. 물론 소수를 구하게 된다면 좀 더 수월해지겠지만 순회하는 방식으로는 도저히 구할 수가 없다는 것을 알게 되었고, 결국 오일러의 피 함수를 찾아보게 되었다. 소인수를 통해 서로소의 개수를 구할 수 있는 함수이다.  오일러 피 함수 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 오일러 파이 함수의 그래프. ϕ(1)부터 ϕ(1000)까지의 값들을 나타낸다. 수론에서 오일러 파이 함수(-函數, 영어: Euler’s phi (totient) function)는 정수환의 몫환의 가ko.wikipedia.org 공식을 알고나니 구현..

Solver 2차 배포를 완료했다. 수정사항은 오류 수정과 UI 업데이트가 있다. 오류 수정SwiftData 가 업데이트 되면서 Data race 오류를 수정했다. [Project-Solver] Data race 오류 기록문제 상황앱에서 fetch를 연속적으로 하게 되면 위와 같이 data race가 발생하는 것을 확인했습니다. 해결 과정문제 파악간단한 Top100Store 부터 살펴보니 fetch() 함수 부분에서 top100 = fetchedTop100 이 fetswift-library.tistory.com UI 업데이트1. 기존 문제점- 스크롤 위치를 추적하면서 바뀌는 요소들이 너무 많아 UI 업데이트가 버벅거리는 현상이 발생했다. - 계정 탭에 이름 바꾸기 항목밖에 없어 필요가 없었다. - 티어 ..

문제 소개https://www.acmicpc.net/problem/16565 해결과정접근 방법완전 수학문제이다. 경우의 수를 구하는 문제이다. 포카드 4장을 뽑아야 이기는 경우의 수니까 만약 5장의 카드를 뽑는다면 무조건 포카드를 뽑아야 하므로 4장은 포카드, 나머지 1장을 (52장 - 4장)에서 고를 수 있는 경우의 수이다. 그렇다면 8장을 뽑는다면 어떻게 될까? 우선 이기려면 4장은 포카드 나머지 4장을 (52장 - 4장)에서 고르는 경우의 수가 있는데 여기서 하나를 더 고려해야 한다. 포카드를 2세트를 뽑았을 때는 경우의 수가 중복이 된다는 것을 알 수 있다. 왜냐하면 포카드 1세트를 고르고 나머지 4장으로 경우의 수를 돌렸는데 4장이 포카 들어가 나올 경우가 생긴다. 이 경우가 중복이 된다. 따라..

문제 소개해결 과정첫 번째 풀이 (50점)최대, 최솟값을 결정하고 나머지는 2^n으로 최대 최소일 경우 몇 번의 경우가 있는지를 구하면 되는 문제였다. 문제는 모듈러 연산... 처음에 2의 n제곱을 구하는데 모듈러 연산을 안 해줘서 자꾸 런타임 오류가 났었다. let fileIO = FileIO()let n = fileIO.readInt()let mod = 1_000_000_007var answer = 0var sco = [Int]()for _ in 0..하지만 이 풀이의 문제점은 2중 반복문이 들어가기 때문에 n = 300,000 일때 90000,000,000의 연산을 하기 때문에 시간초과가 발생한다.정답 (250점)생각해보면 단순했다. 굳이 최대 최소를 결정할 필요 없이 하나의 메뉴가 있다면 최대일 ..

문제 소개https://www.acmicpc.net/problem/13334문제 풀이가장 간단한 풀이방법은 철로를 계속 한 칸씩 옮겨가면서 확인해 보기. 하지만 이 방법은 철로를 옮길 때마다 새롭게 그곳에 포함되는 선을 찾아야 한다는 점이다. 그렇다면 이 문제는 포함되는 선을 최대한 가져가면서 갱신해 주는 방식으로 사용하면 된다! 1. 철로를 어떻게 옮겨야 효율적으로 옮길까?주어진 것은 집의 x좌표와 오피스의 x좌표이다. 이것을 기준으로 철로를 옮겨가면 되겠다는 생각을 했다. 어자피 철로의 길이는 마지막에 주어진 d보다만 작으면 최대로 포함만 한다면 길이는 상관없다. 그렇다면 집의 좌표, 오피스의 좌표로 옮겨가면서 철로의 길이가 d 이내인 두 점으로 순서대로 옮겨보면 되겠다고 생각했다. 2. 어떠한 식으..

문제 상황앱에서 fetch를 연속적으로 하게 되면 위와 같이 data race가 발생하는 것을 확인했습니다. 해결 과정문제 파악간단한 Top100Store 부터 살펴보니 fetch() 함수 부분에서 top100 = fetchedTop100 이 fetch 마다 호출이 되기 때문에 발생하는 문제였습니다. 비동기적으로 top100 이 여러 번 업데이트되면서 동시성 문제가 발생하기 때문입니다.@Observablefinal class Top100Store { let useCase = FetchUseCase() var top100: Top100Entity? @ObservationIgnored @AppStorage("userId") var userId = "" init..