Coding test/Baekjoon

⭐️ 난이도 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번 다리로 이동하려고 할 때, 최소 이동 횟수는 몇 번인지 구하시오. 시작점과 도착점이 주어지고, 시작점에서 도착점까지 이동하는 최소 이동 횟수..

⭐️ 난이도 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가 주어지기 때문에 두 수를 ..

⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net ⭐️ Idea flow 이분 그래프 기본 문제였다. 각 테스트 케이스마다 주어진 그래프에 대해서, 해당 그래프의 이분 그래프 여부를 구하는 문제이다. 따라서 이분 그래프에 대해서 알고 있으면 풀 수 있는 문제였다. 이분 그래프란 인접한 정점끼리 서로 다른 색으로 칠하여 모든 정점을 두 그룹으로 나누고, 서로 다른 그룹의 정점을 간선으로 연결한 그래프를 말한다. ..

⭐️ 난이도 Gold 3 ⭐️ 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net ⭐️ Idea flow 위상 정렬에 대해 이해하고 있고, 언제 이용해야 하는지 알고 있으면 해결할 수 있는 문제였다. 왜 위상 정렬을 이용하여 해결해야 하는가? 이 문제는 일부 학생들의 키 순서가 주어졌을 때, 전체 학생을 키 순서대로 줄을 세운 결과를 반환해야 한다. 방법이 여러 가지인 경우 아무거나 출력하면 되므로,..