→ Problems

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

문제 소개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. 어떠한 식으..

문제 소개문제 자체는 아주 간단하지만 N이 10억이하의 자연수라는 조건이 있기 때문에 1부터 숫자를 늘려가며 판별하면 무조건 시간 초과가 걸린다. 문제 풀이let input = readLine()! let a = Array(input.reversed()).map { Int(String($0))! } let n = Int(input)! var ans = Array(repeating: 0, count: 10) for (i, e) in a.enumerated() { let p = Int(pow(10.0, Double(i))) for j in 0...9 { ans[j] += n / (p * 10) * p } if e > 0 { for j in 1..

문제 소개도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프들이 있습니다. 이 그래프들은 1개 이상의 정점과, 정점들을 연결하는 단방향 간선으로 이루어져 있습니다. 크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다. 도넛 모양 그래프의 아무 한 정점에서 출발해 이용한 적 없는 간선을 계속 따라가면 나머지 n-1개의 정점들을 한 번씩 방문한 뒤 원래 출발했던 정점으로 돌아오게 됩니다. 도넛 모양 그래프의 형태는 다음과 같습니다.크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다. 막대 모양 그래프는 임의의 한 정점에서 출발해 간선을 계속 따라가면 나머지 n-1개의 정점을 한 번씩 방문하게 되는 정점이 단 하나 존재합니다. 막대 모양 그래프의 형태는 다음과 같습..

문제소개문제 자체는 아주 간단하다. 문제 풀이Set으로 풀이우선 Set 자료구조를 사용하여 풀어봤지만 역시 M

문제 소개https://www.acmicpc.net/problem/14891 엄청난 구현문제... (?) 문제 풀이톱니바퀴 돌리기큐로 구현하는것이 일반적이지만 여기서는 배열의 갯수와 성분들이 작아서 간단하게 removeLast, removeFirst 메서드로 구현했다.func rotateGear(_ i: Int, _ isClockwise: Bool) { if isClockwise { gears[i].insert(gears[i].removeLast(), at: gears[i].startIndex) } else { gears[i].append(gears[i].removeFirst()) } } 같이 돌아가는 톱니바퀴 그룹화union, find 알고리즘을 사용했다. 결국 같은 그룹안에 있어야 톱니바퀴가 돌아가는..