BOJ - 1541 - 잃어버린 괄호 문제 1541번: 잃어버린 괄호 문제 개념 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작...

greedy 개요 이번 포스팅에선 알고리즘의 탐욕법(greedy), 완전탐색(brute force)에 대해 알아보도록 하겠다. 탐욕법(greedy) 문제 풀이를 위한 아이디어를 추출하고, 정당한지 확인하자. 특징 문제 풀이를 위한 아이디어를 추출한다. 추출된 아이디어가 문제 상황에 적합한지 판단 후 적용한다. 예...

BOJ - 10825 - 국영수 문제 10825번: 국영수 문제 개념 문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 ...

BOJ - 1676 - 팩토리얼 0의 개수 문제 1676번: 팩토리얼 0의 개수 문제 개념 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 10!이 12314400 이라 할 때 2가 출력 되어야 한다. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 ...

BOJ - 6588 - 골드바흐의 추측 문제 6588번: 골드바흐의 추측 문제 개념 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, ...

BOJ - 9020 - 골드바흐의 추측 문제 9020번: 골드바흐의 추측 문제 개념 문제 1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수...

BOJ - 2231 - 분해합 문제 2231번: 분해합 문제 개념 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성...

BOJ - 4673 - 셀프 넘버 문제 4673번: 셀프 넘버 문제 개념 문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시...

BOJ - 2941 - 크로아티아 알파벳 문제 2941번: 크로아티아 알파벳 문제 개념 문제 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주...

BOJ - 2941 - 크로아티아 알파벳 문제 1316번: 그룹 단어 체커 문제 개념 문제 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, a...