[백준(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) 9095] 1, 2, 3 더하기 문제 백준 9095 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 예시 n = 4; 1+1+1+1 / 1+1+2 / 1+2+1 / 2+1+1 / 2+2 / 1+3 / 3+1 input 첫째줄 : T(테스트 개수) 그 다음 줄 부터 : n(11보다 작은 자연수, T번 반복됨) 해결 우리가 찾고자 하는 수는 1, 2, 3의 조합이다. 즉, 쉽게 생각해 1, 2, 3으로 각각 시작하는 경우의 수를 모두 찾아보면 답이 나온다. 예를 들어 n = 6라고 할 때, 1, 2, 3 을 기준으로 생각해 본다면, 6 = 1 + 5, 6 = 2 + 4, 6 = 3 + 3로 나타낼 수 있다. 즉 n = 6의 경우,..

문제 백준 11726 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 주의 할 것은 출력이 10007을 나눈 나머지 라는 것..! (이거 안 읽고 계속 틀렸었다…. 문제는 제대로 읽어야 한다..) 해결 처음에는 width 2인 정사각형이 몇 개가 들어가는 지에 따라 경우의 수를 나누어 보았는데, 결과적으로 더 쉬운 패턴을 발견할 수 있었다…. 1.n = 1 : answer = 1 2.n = 2 : answer = 2 3.n = 3 : answer = 결론적으로, 이러한 점화식 형태를 보인다. 그러니 우린 간단하게 점화식을 풀면 됨..! 알고리즘 DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다. 모두 알테지만, 다시 한번 간..

문제 백준 1463 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오. 해결 문제가 쉬운 편이지만, 자주 쓰이는 간단한 원리이니만큼 정리를 해보고, memorization 유무에 따른 시간 비교를 해보았다. 알고리즘 BFS 방식으로 해보았다. 트리 구조로 정리하자면 아래와 같다. Queue를 만들어 입력값을 우선 넣는다.(시작점) Queue안의 원소들은 하나씩 pop되어 문제에 정의된 1~3번 과정을 거쳐 Queue에 삽입된다. 일단 가능한 경우의 수를 모두 넣어..

[백준(baekjoon) 2609] 최대공약수, 최소공배수(GCD/LCM) 원리/코드/유클리드 호제법 문제 백준 2609 최대공약수(GCD) 와 최소공배수(LCM) 를 구하시오. 원리 최대공약수 : 유클리드 호제법 사용 최소공배수 : 최대공약수 활용 유클리드 호제법 GCD(A, B) = A, B의 최대공약수 r = A % B 일 때, GCD(A, B) = GCD(B, r)이다. 단, r == 0이면 GCD(B, r) = B이다. 딱 r = A % B = 0으로, 딱 나누어 떨어지므로 최대공약수는 B 예시 A = 24, B = 82 GCD(24, 82) r = 24 % 82 = 24 r > 0 -> GCD(82, 24)호출 GCD(82, 24) r = 82 % 24 = 10 r > 0 -> GCD(24, ..