알고리즘 문제풀이/백준134 [백준 2012] 등수 매기기 www.acmicpc.net/problem/2012 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 정렬을 사용하는 문제이다. 주의할 점은 예상 등수가 1 ~ n 사이를 벗어날 수 있다!! 그래서 입력값을 소팅한 다음에 본래 등수와의 차이를 더하여 결과값을 리턴한다. #include #include #include #include using namespace std; int n; int main(void) { scanf("%d", &n); vector rank; long long sum = 0; for (int i .. 2020. 12. 16. [백준 1543] 문서 검색 www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 브루트포스를 돌면 tle가 아닐까..했으나 길이가 짧아서 아닌거 같다. 접근 방식은 간단하다. 모든 문자열 비교 - 브루트포스이다. 처음엔 0부터 비교하는 걸로 했으나 반례가 존재했다. ababaa abaa 같은 로직으로 앞에서 부터 비교를 시작하면 aba까지 체크하고 a와 b가 달라서 지나가버리지만 뒤에서 부터 비교하면 abaa를 잡아낼 수 있다. 공백이 포함된 입력값도 제공되므로 getline(cin, 문자열)을.. 2020. 12. 16. [백준 1541] 잃어버린 괄호 www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net -등장 이후로 전부 -로 계산하면 되는 쉬운 문제였으나..처음에 어렵게 접근하여 스택쓰고 난리났다.. 괄호는 맘대로 칠 수 있으므로 -가 등장한 이상 뒤에 수를 전부 -로 계산가능하다. 식에서 숫자가 마지막으로 등장하기 때문에 i 2020. 12. 16. [백준 2011] 암호코드 www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net DP를 사용하는 문제이며 리트코드에서도 유사한 문제를 푼 경험이 있다. DP[i]는 i번째 숫자를 포한해서 만들 수 있는 암호코드 최대 갯수로 정의한다. dp[i]에 영향을 주는 요소는 dp[i-1]과 dp[i-2]가 있다. 25114의 경우 2 -> B 25 -> B + E / ' ' +Y 251 -> BE + A / Y + A 2511 -> BEA + A / YA + A / BE + K / YA + K 25114 -> BEA.. 2020. 12. 15. 이전 1 ··· 19 20 21 22 23 24 25 ··· 34 다음