[백준(baekjoon) 2902] KMP는 왜 KMP일까? 문제 백준 2902 알고리즘 명을 지을 때, 주로 만든 사람들의 성의 첫글자만 따서 줄여 부른다. 긴 형태 : 하이픈(-)으로 이어 붙인 것 예시 : Knuth-Morris-Pratt 짧은 형태 : 첫 글자만 딴 것 예시 : KMP 긴 형태의 알고리즘 명이 주어졌을 때, 짧은 형태로 바꿔 출력하라. 해결 알고리즘 굳이 구분하자면 문자열 알고리즘이라고 할 수있다. 설명 하이픈 (-) 기준으로 이름을 나누고, 앞 문자만 가져와 붙이는 쉬운 문제이다. String.split(String regex)로 정규 표현식에 따라 문자열을 구분하였고, String.charAt(int index)로 각 이름의 첫글자에 접근하였다. 그리고 가변객체인 StringB..

[백준(baekjoon) 1744] 수 묶기 문제 백준 1744 길이가 N(1…10000)인 수열이 주어질 때, 그냥 더 하거나 두 수 씩 묶어 곱한 후 더한 값이 최대가 되는 경우를 찾아 최대 값을 출력하시오. 주의 : 자신과 자신은 곱할 수 없으며, 이미 한번 묶인 수는 재 이용될 수 없다. 예시 : {0, 1, 2, 4, 3, 5}일 때, 최대 값 = 0 + 1 + (2 * 3) + (4 * 5) = 27 해결 알고리즘 그리디 알고리즘을 사용해 해결하였다. 최적이 되는 순간이 어떤 경우인지 파악하였다. 그리디 알고리즘에 대해 잘 모르신다면 이 글을 참고하세요! 설명 간단히 최대 값이 되기 위해선 어떤 조건이 있어야 할지 생각해보았다. -는 -와 묶여 양수가 되어야 한다. 혹은, 0과 묶여 0이 되어..

[백준(baekjoon) 2875] 잃어버린 괄호 문제 백준 2875 N(1…100)명의 여자, M(1…100)명의 남자, 제외해야할 K(0…M+N)명이 주어질 때, 대회에 나가는 팀의 구성은 반드시 2명의 여자 + 1명의 남자가 되어야 한다. 이때, 대회에 나갈 수 있는 최대의 팀 수를 구하시오. 해결 두가지 방식으로 풀었다. 단순히 if문과 연산만을 사용해 K값을 0으로 줄이는 방식 K가 M + N보다 클 경우는 말할 필요도 없이 0이 답이다. 2 : 1비율로 M, N을 비교해 적은 값(비율 1)이 K를 고려하지 않았을 때의 팀의 수가 된다. 팀으로 확정되지 않은 나머지 사람 수를 구한다. 그리고 그 사람들을 K에서 제외한다. 그래도 K가 0이상이라면, 제외할 팀의 수를 구해 기존 확정된 팀에서 빼준..

[백준(baekjoon) 1541] 잃어버린 괄호 문제 백준 1541 ‘+’,’-‘, 양수로 이루어진 식(최대 길이 50)이 입력 되었을 때, 괄호를 적절히 식의 최종 값을 최소로 만든 후 그 값을 출력 하시오. 해결 두가지 방식으로 풀었는데 둘다 원리는 동일하다. 단지 for문을 한번만 쓰고 싶어서 좀 더 줄여 보았다. 1) 방식은 Stack을 이용한 중위 표기법 계산 방식 사용, 2중 for문을 사용하였다. 2) 방식은 for문을 한번만 사용하고, Stack을 따로 쓰지 않았다. 원리는 이러하다. 입력 값을 숫자, 연산자로 구분한다. 입력 값이 30+40-29형식으로 붙어서 한줄로 들어오기 때문에, char로 한 문자씩 딴다. 연산자를 기준으로 숫자를 구분, 저장한다. 1) 방식의 경우 첫번 째 fo..

문제 백준 11399 N(1…1000)명의 사람이 돈을 인출하는데 걸리는 시간 Pi(1…1000) 이 각각 주어진다고 할 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최소값을 구하시오. 주의 : i번째 사람이 돈을 인출하는데 필요한 시간은 1...i-1번째 사람을 기다리는 대기 시간도 포함한다. 예시 : P1 = 3, P2 = 1, P3 = 4일 때, [1, 2, 3]순서로 돈을 뽑을 때는 3 + (3 + 1) + (3 + 1 + 4) = 15의 시간이 걸린다. [2, 1, 3]순서로 돈을 뽑아야 1 + (1 + 3) + (1 + 3 + 4) = 13인 최소값이 나온다. 해결 아주 쉬운 문제이다. 대기시간을 줄이는게 관건이다. 즉, 시간을 오름차순으로 정렬하여 앞에서 부터 사용 시간 = 이전 값(..

[백준(baekjoon) 11047] 동전 0 문제 백준 11047 N개의 종류의 동전의 가치 Ai가 주어질 때 (각 종류의 동전은 무한히 많다.) 동전 들을 사용해 K원을 만들려고 한다. 이때, 필요한 동전 종류 개수의 최소 값은? 주의 : A1 = 1은 Default이며, i > 1을 만족하는 Ai = Ai-1의 배수이다. 해결 처음에는 DP를 사용해야 하나 했다. N = 3, K = 2000, A1 = 100, A2 = 500, A3 = 800의 경우 정답은 A2 * 4 = 2000이 되기 때문에. 하지만, 역시 문제는 자세히 읽어야 한다…! i > 1을 만족하는 Ai = Ai-1의 배수이다. 이 부분에 의해서 그리디 알고리즘으로 문제를 해결할 수 있다. 가장 큰 동전 종류부터 확인, 차액을 구하여..