Scat

yongmin's dev blog

[BOJ] 9375번 패션왕 신해빈 - C++

"정수론 및 조합론"

문제 패션왕 신해빈 풀이 category 별로 갯수를 어레이에 정리한 뒤, 카테고리 안의 물건 수 + 그 카테고리 물건을 안 끼는 경우들, 즉 카테고리마다 +1(안끼는 경우의 수)를 하여, 그것들의 조합을 구하기 위해 각자 곱한다. 그러면 총 경우의 수가 나오는데, 이 때 알몸인 경우, 즉 모두 안 끼는 경우를 하나 빼주면 원하는 답의 결과가 도출된...

Posted by Yongmin on June 16, 2021

[BOJ] 3036번 링 - C++

"정수론 및 조합론"

문제 링 풀이 톱니바퀴 문제로, 단순히 나눗셈을 해주면 되는 문제이다. 기약분수로 나타내기 위해 분자 분모를 각각 최대공약수로 나누어 주었다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <iostream> #include &l...

Posted by Yongmin on June 16, 2021

[BOJ] 1934번 최소공배수 - C++

"정수론 및 조합론"

문제 최소공배수 풀이 시간 초과를 피하기 위해 유클리드 호제법을 이용해서 풀이되는 문제이다. 유클리드 호제법에서 최대공약수는 두 수 중 큰 수를 작은 수로 나누고, 또 나누었던 수와 나머지 수를 또 서로 나누는 것을 반복해 나머지가 0이 될 때 나눈 수가 최대공약수가 된다는 것이다. 이 최대공약수를 이용하여 최소공배수는 기존의 두 수를 곱한 뒤 최대...

Posted by Yongmin on June 15, 2021

[BOJ] 13305번 주유소 - C++

"그리디 알고리즘"

문제 주유소 풀이 지나치는 주유소 마다 기존의 최솟값보다 크다면, 최솟값으로 다음 도시로 이동하는 만큼 주유를 하고, 최솟값보다 작으면 그 값으로 최솟값을 갱신하여 다음 도시로 이동하는 식으로 최솟값을 찾아냈다. 물론 현실적으로 도시를 지나쳤음에도 불구하고 최솟값 도시의 주유소에서 주유를 할 수 있다는 것이 말이 안되긴하다. 소스 코드 1 2 3 4...

Posted by Yongmin on June 14, 2021

[BOJ] 1541번 잃어버린 괄호 - C++

"그리디 알고리즘"

문제 잃어버린 괄호 풀이 적절한 괄호를 넣어서 최솟값을 만드는 것인데, 예를 들어 30-50+40이 있으면, 30-(50+40)으로 괄호를 넣어 최솟값으로 만드는 것이다. 이는 결국 (-) 연산자 뒤의 숫자들을 다음 (-)연산자가 나올 때 까지 묶으면 되는데, 결국 최솟값을 만드는 방법은 (-)가 나온 순간부터 그 이후 연산자를 모두 -로 대체 하는...

Posted by Yongmin on June 14, 2021

[BOJ] 11399번 ATM - C++

"그리디 알고리즘"

문제 ATM 풀이 i번째에 해당하는 사람이 총 걸리는 시간은 i-1까지의 시간 + 본인이 걸리는 시간이다. 그러므로 최솟값은 서있는 사람들을 걸리는 시간이 작은 순서대로 줄을 서게 하는 것이 최솟값이 될 것이다. 이는 결국 최솟값은 첫번째 사람은 N번만큼 연산, 두번째 사람은 N-1번만큼 … N번째 사람은 1번만큼 연산되는 것으로 결과 도출이 가능...

Posted by Yongmin on June 14, 2021

[BOJ] 1913번 회의실 배정 - C++

"그리디 알고리즘"

문제 회의실 배정 풀이 끝나는 시간이 빠른 순으로 정렬한 뒤, iteration을 돌면서 끝나는 시간 뒤에 시작하는 가장 빠른 끝나는 시간을 갖는 회의를 진행하게 하며 count를 세는 것으로 정답을 도출할 수 있다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2...

Posted by Yongmin on June 14, 2021

[BOJ] 9251번 LCS - C++

"다이나믹 프로그래밍"

문제 LCS 풀이 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. Longest Common Substring = 최장 공통 부분 문자열, Longest Common Subsequence = 최장 공통 부분 수열가 있는데...

Posted by Yongmin on June 10, 2021

[BOJ] 2565번 전깃줄 - C++

"다이나믹 프로그래밍"

문제 전깃줄 풀이 LIS 문제 응용이라고 할 수 있다. 전깃줄이 교차하지 않으려면 전깃줄 번호의 오름차순으로 연결되어야 교차하지 않는다. 그러므로, 부분 수열 중 가장 긴 부분 수열의 수를 전체에서 빼주면 원하는 답이 나온다. 그전에 A 전깃줄이 순서대로 어떻게 연결되어 있는지 정렬을 하고 난 뒤(A전깃줄 번호를 index로 칭하여 그에 해당되는 a...

Posted by Yongmin on June 9, 2021

[BOJ] 10814번 나이순 정렬 - C++

"정렬"

문제 나이순 정렬 풀이 안정정렬은 정렬 후에도 정렬이 되지 않은 상태에서 같은 값을 가진 값들의 순서가 계속 유지되는 정렬을 말하는 것이라고 한다. 해당 나이순 정렬의 문제가 곧 안정정렬 문제라고 볼 수 있다. stable_sort 함수를 이용하여 간단하게 구현이 가능했다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15...

Posted by Yongmin on June 9, 2021

FEATURED TAGS
Format BOJ C++ Python Algorithm
ABOUT ME

짱구