본문 바로가기

분류 전체보기411

[C++] 백준 11051번 : 이항 계수 2 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 풀이 배열 DP에 이항 계수를 저장하면 된다. 이때 이항 계수의 값은 파스칼의 법칙을 이용하면 쉽다! 느낀 점 고등학교 때 배웠던 파스칼의 법칙을 이렇게 쓸 줄은 몰랐다. 처음에는 파스칼의 법칙을 기억하지 못해서 없는 코드로 구현했는데 틀려서 약간의 구글링으로 해결했다.. ^.^ 코드 #include using namespace std; int n, k; long long dp[1002][1002] = { 0, }; void solution() { for (in.. 2021. 7. 11.
[C++] 백준 3036번 : 링 https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 문제 풀이 기약 분수 형태로 출력하는 것만 신경 쓰면 되는 문제이다. 기약 분수로 만들기 위해서는 최대공약수로 나눠주면 된다! 결국 최대공약수를 구하는 문제이다! 함수 Solution 첫 번째 원이 기준이니 2번째 원부터 따진다. 만약에 최대공약수가 없다면 있는 그대로 출력한다. 느낀 점 유클리드 알고리즘만 알고 있다면 쉽게 해결할 문제이다! 코드 #include using namespace std; int n; int radiu.. 2021. 7. 3.
[C++] 백준 2981번 : 검문 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 문제 풀이 수학적인 사고를 요구하는 문제이다!! 문제에서 찾아야 하는 M은 같은 나머지(이하 R)를 만드는 숫자이다. 어떤 값 arr[i]를 M으로 나눴을 때 나머지가 R이 나오면 식은 다음과 같을 것이다. arr[i] = M × (arr[i] / M) + R 그렇다면 다음 값들은 arr[i+1] = M × (arr[i+1] / M) + R 이런식으로 이어진다. 여기서 R을 없애주기만 한다면 M을 구하기가 더 쉬.. 2021. 7. 3.
[알고리즘] 유클리드 알고리즘(최대공약수, 최소공배수 구하기) 일반적으로 최대공약수(Greatest Common Factor)와 최소공배수(Lowest Common Multiple)를 구할 때 소인수분해를 해서 구한다. 하지만 프로그래밍을 통해서 구할 때는 특정한 알고리즘 없이 직접적으로 구하기 까다롭다. 여기서 유클리드 알고리즘은 최대공약수를 구하는 특별한 알고리즘이다! ※ 유클리드 알고리즘이란? 주어진 두 수 사이에 최대공약수(GCD)를 구하는 알고리즘 유클리드 알고리즘은 "두 수 A, B가 주어졌을 때(단 A > B) A를 B로 나눈 나머지 r에 대해서 GCD(A, B) = GCD(B, r)이고, 여기서 나머지 r이 0이면 B가 두 수의 최대공약수이다!"라는 원리를 이용한 알고리즘이다. 알고리즘을 구현하는 방법은 재귀를 이용하는 방법과 반복문을 이용하는 방법 .. 2021. 7. 3.
[C++] 백준 13305번 : 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 풀이 값들을 입력받고 최솟값을 최신화해서 두 도시 사이의 거리와 최솟값을 곱해서 결과에 더해주면 된다. 여기서 최솟값임을 따지는 것이 그리디 알고리즘의 핵심이다! 함수 Solution i번째 값이 최솟값보다 작으면 최솟값을 최신화한다. 이후 최솟값과 i번째 거리와 곱해서 ans에 더한다. 느낀 점 처음에 프로그래머답지 못하게 문제를 너무 1차원적으로 접근했다. 각 거리 값을 더.. 2021. 7. 1.
[C++] 백준 1541번 : 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 풀이 식이 주어졌을 때 최솟값을 만드는 문제이다. 단순하게 -가 등장하면 괄호를 열거나 닫아서 식을 최소로 만들 수 있다. 따로 괄호가 들어간 식을 보일 필요가 없으므로 -가 등장한 순간부터 이후의 모든 숫자들을 빼면 최솟값이 만들어진다! 변수 string str : 입력받은 식을 저장 string num : str에서 숫자 부분만 저장 int ans : 계산되는 값을 저장 bool i.. 2021. 7. 1.

티스토리툴바