→ Problems

문제 소개https://www.acmicpc.net/problem/11724연결 요소의 갯수를 출력하는 문제이다. 문제 풀이아래와 같이 그래프를 만들어서 dfs로 순회하는 식으로 문제를 풀었다.import Foundation let nm = readLine()!.split(separator: " ").map{ Int(String($0))! } let (n, m) = (nm[0], nm[1]) var graph = Array(repeating: Array(repeating: 0, count: n+1), count: n+1) var visited = Array(repeating: false, count: n+1) visited[0] = true for _ in 0..

문제 소개https://www.acmicpc.net/problem/1260문제에서 아예 솔직하게 DFS, BFS로 탐색해봐라 라는 문제이다. 문제 풀이BFS가 익숙하지 않아서 조금 어려움을 겪었다. 큐를 사용하여 BFS를 구현하였다.import Foundation let nmv = readLine()!.split(separator: " ").map{Int(String($0))!} let (n, m, v) = (nmv[0], nmv[1], nmv[2]) var graph = Array(repeating: Array(repeating: 0, count: n+1), count: n+1) for _ in 0..

문제 소개https://www.acmicpc.net/problem/13023 문제풀이문제를 보고 가장 먼저 연결리스트가 떠올랐다. 연결리스트로 쭉 따라가서 depth가 5가 되면 1을 출력하면 된다는 것을 생각했다.import Foundation let nm = readLine()!.split(separator: " ").map{Int(String($0))!} let (n, m) = (nm[0], nm[1]) var people = [Int: [Int]]() for i in 0..

문제 소개나무를 어떻게 잘라야 하는지 결정해야하는 이진탐색 문제이다.  문제풀이이 문제를 보고 이진탐색을 바로 생각할 수 있는 이유는 어떠한 값을 넣게 되면 true, false로 나오게 되고, 어떠한 값들의 집합이 오름차순으로 되어있는 것을 볼 수 있다. 예를 들면 [1, 2, 3, 4, 5] 의 경우가 있을 때, 어떠한 로직에 의해서 [True, True, False, False, False] 로 바꿔줄 수 있다면 이진탐색으로 풀수있는 문제이다.import Foundationlet nm = readLine()!.split(separator: " ").map { Int($0)! }let (n, m) = (nm[0], nm[1])let trees = readLine()!.split(separator: "..

문제 소개 6064번: 카잉 달력입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다.www.acmicpc.net진법과 아주 비슷한 개념인데 진법은 위로 쌓아가지만 위의 카잉 달력은 해당 숫자가 넘으면 다시 1로 시작한다는 차이점이 있다. 풀이 방법m, n, x, y가 주어지는데 아래와 같이 볼 수 있다. 결국 a와 b를 구하라는 뜻인데, 단순하게 a를 0부터 차례로 대입해나가면 된다. 그리고 최대 연도(종말 연도)는 m과 n의 최소공배수로 볼 수 있다.year % m = xyear % n = yyear = ma + xyear = nb + y 내가 작성한 코드는 아래와 ..

문제 소개포도주 잔을 2잔 연속해서 마실수있고, 주어진 n개의 포도주의 양중에 최대로 마실수 있는 포도주의 양을 출력하는 문제이다. 문제 풀이와인을 마실경우를 O라고 생각하고 마시지 않을 경우를 X라고 생각하면 앞을 고려하지 않는다면 다음과 같은 경우가 최대가 될 것이다.하지만 여기서 문제가 있다. 1번 2번 케이스일 경우 앞에서 어떠한 케이스인지 모르기 때문에 함부로 2번 연속해서 마시거나 1번 마실수가 없다. 이미 앞에서 마셨을수도 있기 때문이다. 그렇다면 1번 2번 케이스의 X의 앞을 살펴보면 가장 최선의 선택을 했을 경우라는 것을 볼 수 있다. 그렇다면 이렇게 생각해보면 어떨까? 내가 생각하기에 다이나믹 프로그래밍은 "내가 계산한 값에 대한 믿음" 이다. 내가 앞에서 계산한 값이 무조건 최선이라고..

문제 소개 1929번: 소수 구하기첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.www.acmicpc.net첫째 줄에 m, n이 주어지면 m이상 n이하의 자연수를 출력하는 문제이다. 문제 풀이2부터 시작해서 배수를 소거해나가는 "에라토스테네스의 체" 알고리즘을 사용했다. 배열을 편하게 index와 숫자를 동일시해서 Array(0...n)으로 배열을 초기화 해주었다. 그리고 어떠한 수의 배수가 된다면 1로 변경하였다. Int(sqrt(Double(n))) + 1 이 부분은 어떤 의미이냐면 2부터 n까지의 모든 숫자의 배수를 하나하나 대조해보는 것이 아니라 100인 경우 10까지만 생각하면 된다는..

문제소개 1918번: 후위 표기식첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net우리가 주로 사용하는 중위표기식을 후위표기식으로 바꾸는 문제이다. 문제 풀이후위표기식 규칙과 stack을 통해 후위 표기식을 만들 수 있다.후위표기식 규칙1. 연산자가 아닌 경우 postfix에 추가한다. 2. 스택이 비어있는 경우 연산자를 스택에 넣어준다. 3. 스택이 비어있지 않은 경우 스택의 마지막 연산자가 "(" 이거나 우선순위가 낮을 때까지 스택의 마지막 요소를 postfix에 추가한다. 4. ")" 가 나왔을 경우 "(" 가 나올 때까지 스택..