🌀 알고리즘(Algorithm)

백준 9251번: LCS 알고리즘 분류: 문자열, 다이나믹 프로그래밍(DP) 파이썬(Python) 풀이 링크: https://www.acmicpc.net/problem/9251 LCS(Longest Common Subsequence)란 최장 공통 부분 수열이라는 의미로 두 문자열 사이에서 모든 부분 수열이 되는 수열 중 가장 긴 문자열을 찾아내는 것이다. 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 100..

백준 11687번: 팩토리얼 0의 개수 알고리즘 분류: 수학, 정수론, 이분 탐색 파이썬(Python) 풀이 링크: https://www.acmicpc.net/problem/11687 문제 가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 찾는 프로그램을 작성하시오. 입력 첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다. 출력 가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 출력한다. 그러한 N이 없는 경우에는 -1을 출력한다. 풀이 예를 들어 1이 입력되면 0의 개수가 1개인 N은 5이다( 5! = 120이기 때문) 그러면 2가 입력된다면 0의 개수가 2개이므로 N은 10이 된다 ( 10! = 3628800이기 때문) 여기까지만 본다면 M과 N의 관계는 M * 5 =..

getchar()을 쓰자...ㅠ 보통 C언어에서는 입력 버퍼를 비우기 위해 fflush를 사용하는 경우가 있다. 예를 들어 배열의 크기를 입력받고, 그 안에 요소들을 한개씩 입력받는 경우에 개행문자('\n')가 그대로 들어가는 문제가 발생한다. 이를 방지하기 위해 백준에서 위 1991번 문제를 풀 때 fflush를 사용하였다. 예전부터 입력 버퍼 비우려면 fflush(stdin);이 정답이라고만 생각해서 생각없이 썼는데 이번 기회에 왜 쓰면 안되는지를 생각해보았다. fflush는 출력 스트림에 대해서는 정의가 되어있지만 입력 스트림에 대해서는 정의가 되어있지 않다고 나와있다. 또한 공식 문서를 확인해보니 2015년 부터에서는 아무런 효과가 나타나지 않는다고 적혀있어서 https://en.cpprefere..

백준 25345번: 루나의 게임 세팅 알고리즘 분류: 수학. 조합론 파이썬(Python) 풀이 링크: https://www.acmicpc.net/problem/25345 문제 루나와 리나는 타워 건설 게임을 하려고 한다. 타워 건설 게임은 K개의 타워를 사용하는 게임이고 루나는 이 게임을 세팅하려고 한다. 게임 세팅은 서로 다른 높이의 N개의 타워 중 K개를 선택해 원하는 순서로 일렬로 배치하는 것이다. 이때 앞과 뒤에서 바라볼 때 모든 타워가 최소 한 번은 보여야 한다. 즉, 어떤 타워에 대해서 그보다 높은 타워가 그 타워의 앞쪽과 뒤쪽에 모두 존재하면 안된다는 것이다. 게임 세팅을 하던 루나는 문득 게임을 세팅하는 방법이 얼마나 많을 지가 궁금해졌다. 루나를 도와서 게임 세팅을 하는 경우의 수를 구해..

백준 1152번: 단어의 개수 알고리즘 분류: 구현, 문자열 파이썬(Python) 풀이 링크: https://www.acmicpc.net/problem/1152 문제 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다. 입력 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열은 공백으로 시작하거나 끝날 수 있다. 출력 첫째 줄에 단어의 개수를 출력한다. 풀이 처음 이 문제를 접했을 때에는 단어 사이의 공백이 있다는 점..

백준 17202번: 핸드폰 번호 궁합 알고리즘 분류: 구현, 다이나믹 프로그래밍, 문자열 파이썬(Python) 풀이 링크: https://www.acmicpc.net/problem/17202 17202번: 핸드폰 번호 궁합 어린시절 다들 한 번씩은 이름으로 궁합을 본 적이 있을 것이다. 이것과 비슷한 방식으로 중앙대학교에는 핸드폰 번호 궁합을 보는 것이 유행이라고 한다. 핸드폰 번호 궁합을 보기 위해서는 www.acmicpc.net 문제 어린시절 다들 한 번씩은 이름으로 궁합을 본 적이 있을 것이다. 이것과 비슷한 방식으로 중앙대학교에는 핸드폰 번호 궁합을 보는 것이 유행이라고 한다. 핸드폰 번호 궁합을 보기 위해서는 먼저 궁합을 보고싶은 두 중앙대생 A와 B의 핸드폰 번호에서 맨 앞의 010과 "-"(..

백준 24039번: 2021은 무엇이 특별할까? 알고리즘 분류: 수학, 정수론, 소수 판정 파이썬(Python) 풀이 링크: https://www.acmicpc.net/problem/24039 문제 백준 온라인 저지의 송년대회 Good Bye BOJ, 2021!의 개최일은 2021년 12월 31일이다. 원이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2021이 무언가 특별하다는 사실을 깨달았다. 그렇다. 2021은 연속한 두 소수 43과 47의 곱이다. 다음에 이런년도가 오려면 무려 470년 뒤인 2491년이 되어야 한다. 원이는 어떤 수가 연속한 두 소수의 곱으로 이루어져 있으면 특별한 수라 부르기로 하였다. 주어진 수보다 큰 특별한 수 중 가장 작은 수를 구하는 프로그램을 작성하시오. 입..

백준 2535번: 아시아 정보올림피아드 알고리즘 분류: 구현, 정렬 파이썬(Python) 풀이 링크: https://www.acmicpc.net/problem/2535 2535번: 아시아 정보올림피아드 첫 번째 줄에는 대회참가 학생 수를 나타내는 N이 주어진다. 단, 3 ≤ N ≤ 100이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 학생의 소속 국가 번호, 학생 번호, 그리고 성적이 하나의 빈칸을 사 www.acmicpc.net 문제 최근 아시아 지역의 학생들만 참여하는 정보 올림피아드 대회가 만들어졌다. 이 대회는 온라인으로 치러지기 때문에 각 나라에서 이 대회에 참여하는 학생 수의 제한은 없다. 참여한 학생들의 성적순서대로 세 명에게만 금, 은, 동메달을 수여한다. 단, 동점자는 없다고 가정한다..

백준 2869번: 달팽이는 올라가고 싶다. 알고리즘 분류: 수학 파이썬(Python) 풀이 링크: https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 ..