[백준(baekjoon) 5525] IOIOI 문제 백준 5525 N+1개의 I와 N개의 O가 교대로 이루어진 문자열 PN = IOIOI...OI (O가 N개)가 있다. 예시 : P1 = IOI, P3 = IOIOIOI I, O로만 이루어진 문자열 S와 N이 주어질 때, S안에 PN이 몇개 들어있는지 구하시오. 해결 알고리즘 정해진 패턴을 찾는 문자열 매칭 알고리즘이라고 할 수있다. PN은 IOI가 N개 만큼 반복되는 형태이기 때문에, KMP와 같은 별도의 알고리즘을 사용하지 않고 for문을 사용해 일일이 IOI패턴을 찾아 횟수를 센 후 N과 비교하는 방식으로 진행하였다. 시간 복잡도 : O(N) 설명 앞서 말한 것처럼 PN은 IOI가 N개 만큼 반복되는 형태이다. 즉, 각 index를 비교해 IOI 패..

[백준(baekjoon) 10769] 행복한지 슬픈지 문제 백준 10769 1.행복한 표정 : :-), 2.슬픈 표정 : :-( 입력 받은 문자열에 두가지 이모티콘이 섞여 들어올 때, 아래 규칙에 따라, 전체적인 분위기를 파악해 결과를 출력하라. 어떤 이모티콘도 포함되어 있지 않음 : none 행복한 이모티콘과 슬픈 이모티콘의 수가 동일하게 포함 : unsure 행복한 이모티콘이 슬픈 이모티콘보다 많이 포함 : happy 슬픈 이모티콘이 행복한 이모티콘보다 많이 포함 : sad 해결 알고리즘 정해진 패턴을 찾는 문자열 매칭 알고리즘이라고 할 수있다. 찾고자 하는 패턴이 모두 다른 3문자이므로 for문을 사용해 일일이 확인하였다. 시간 복잡도 : O(N) 설명 우선 이모티콘 3문자가 연속으로 나오는지 확인..

[백준(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..