⭐️ 난이도 Silver 2 ⭐️ 문제 https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net ⭐️ Idea flow 문제를 간단하게 정리해보자. 1. 징검다리는 1번부터 n번까지 있다. 2. 현재 칸에서 각 징검 다리에 쓰여 있는 숫자의 배수만큼 떨어진 곳에만 갈 수 있다. 3. a번 다리에서 b번 다리로 이동하려고 할 때, 최소 이동 횟수는 몇 번인지 구하시오. 시작점과 도착점이 주어지고, 시작점에서 도착점까지 이동하는 최소 이동 횟수..
Baekjoon
⭐️ 난이도 Silver 2 ⭐️ 문제 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net ⭐️ Idea flow 문제를 간단하게 정리해보자. 자연수 x가 주어졌을 때, x의 약수들을 모두 더한 값을 f(x)라고 하자. 자연수 n이 주어졌을 때, n보다 작거나 같은 모든 자연수들의 f(n)의 합을 g(n)이라고 하자. g(n)을 구하라. [시간 초과난 알고리즘] 처음에는 1부터 n까지 fo..
⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net ⭐️ Idea flow 이 문제의 내용을 정리해보자. 사칙연산만을 최소한으로 이용해서 s를 t로 바꾸려고 한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력하라. (사칙연산의 사전 순은 다음과 같다. * + - /) s == t라면 0을, s를 t로 바꿀 수 없다면 -1을 출력하라. 연산할 수 있는 방법이 4가지로 정해져 있는데, 이를 최..
⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net ⭐️ Idea flow 이 문제는 GCD와 LCM의 특징을 이용하여 풀 수 있는 문제였다. 문제에서 어떤 두 자연수 A와 B의 최소 공배수(LCM)과 최대 공약수(GCD)가 주어지는데, 이 때, 두 자연수를 구해야 하는 문제였다. 처음에 떠올린 식은 A * B = GCD(A, B) * LCM(A, B) 였다. 문제에서 lcm과 gcd가 주어지기 때문에 두 수를 ..
⭐️ BFS : Breadth-First Search (너비 우선 탐색) 이란? 출처 : 위키백과 BFS - 그래프 전체를 탐색하는 하나의 방법으로써, 현재 정점으로부터 가까운 정점들을 먼저 방문한다. - DFS와 다르게 깊게 파고 드는 것이 아니라, 인접한 정점부터 넓게 탐색한다. - queue(큐)를 이용해서 구현할 수 있다. ⭐️ BFS의 특징 - 정점 방문 시, 반드시 방문 여부(isVisited)를 검사하고, 방문 시 isVisited를 true로 표시한다. - 시간 복잡도(Time complexity) : 인접 리스트로 구현 시 O(V+E) // 인접 행렬로 구현 시 O(V^2) - queue에 다음에 탐색할 정점들을 push하고 pop하는 과정을 거치기 때문에 DFS에 비해서 메모리가 더 필..
⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net ⭐️ Idea flow 이분 그래프 기본 문제였다. 각 테스트 케이스마다 주어진 그래프에 대해서, 해당 그래프의 이분 그래프 여부를 구하는 문제이다. 따라서 이분 그래프에 대해서 알고 있으면 풀 수 있는 문제였다. 이분 그래프란 인접한 정점끼리 서로 다른 색으로 칠하여 모든 정점을 두 그룹으로 나누고, 서로 다른 그룹의 정점을 간선으로 연결한 그래프를 말한다. ..
