![]()
acm-icpc 2020 서울 리저널에서 E번으로 출제되었던 문제이다. 내 기억상으로 3번째로 많이 풀렸던 문제였는데.. 그때 우리는 풀지 못했었다 🥺 하지만 지금은 다르다!! dp를 계속 풀다 생각나서 보니, 해답이 20분? 만에 떠올랐다. 디버깅 과정에서 많이 틀리긴 했는데,, 암튼 나 혼자 해결했다! 지금 생각해보니 그때 결과 보신 교수님은 우릴 어떻게 생각하셨을지... 😰 문제 출처 : https://www.acmicpc.net/problem/20173 문제는 출처 참고하세요! 풀이 문제에서 컴퓨터가 잘못 판단할 경우는 수가 인접할 때 (1과 2, 2와 3 등) 밖에 없다. 따라서 모든 대결(?)을 볼 필요 없이 수가 다음과 같이 줄어들게 된다. (1, 2), (2, 3), (3, 4), ...,..
![]()
출처 : https://www.acmicpc.net/problem/20176 참고한 글 : https://koosaga.com/263 문제 및 풀이 3개의 선분이 위에서부터 차례대로 하나씩 있고, 각 선분 당 특정 좌표에는 구멍이 뚫려있습니다. 아래 그림은 정답이 될 수 있는 바늘이 3개의 선분을 통과한 사례입니다. 기본적으로 바늘이 3개의 선분을 지나가기 위해서는 a~b, b~c 를 지나갈 때 선분의 기울기가 같아야 하고, b의 위치가 동일해야 합니다. 즉, a+c = 2 * b 를 만족한다면 바늘은 선분을 지날 수 있습니다. (편의상, 배열 A, B, C 의 어떤 한 원소를 a, b, c 라 하겠습니다) 일반적으로 모든 a+c 를 구하기 위해선, 어쩔 수 없이 배열 A, C의 원소를 모두 순회하며 구..
![]()
문제 S는 다음과 같이 정의된다. S(0, n) = n (모든 양의 정수 n) S(k, n) = S(k-1, 1) + S(k-1, 2) + ... + S(k-1, n) (모든 양의 정수 k, n) k와 n이 주어졌을 때, S(k, n)을 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 풀이 이 문제같은 경우 어떤 성질을 이용해 점화식을 도출하고 ... 라는 일련의 과정보단, 직접 써보는 것이 이해가 빠를 것이다. 직접 써보니 이런 식의 표가 나왔다. 실제로 문제의 수식대로 저기까지만 계산해도 상당히 머리아픈데, 사람은 귀찮은걸 싫어하다보니.. 저거 쓰는 과정에서도 수를 빨리 도출해내는 법을 찾게 된다. 쓰다 보면 금방 찾는 규칙인데, 규칙은 다음과 같다. 파란색 원 안의 수는 그 ..
![]()
문제 링크 : https://www.acmicpc.net/problem/1014 문제 N행 M열 크기의 직사각형 교실이 주어지고, 각 교실은 1x1 단위 정사각형으로 이루어져 있다. 컨닝을 방지하기 위해 모든 학생은 자신의 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위에 다른 학생이 없도록 자리배치를 하고자 할 때, 교실에 배치할 수 있는 최대 학생 수를 구하여라. 풀이 문제를 보고, 가장 먼저 든 생각은 "다 해볼 수 있는 가?"였다. 물론 최대 10x10 정사각형의 교실이 주어지면, 각 교실 자리는 100개이고, 모든 경우의 수를 다 해보는 것은 2^100 이므로 당연히 불가능하다. 하지만, 이 문제의 경우 i번 째 줄이 어떤 상태이고, 이 상태 배치의 경우 최대 학생 수를 알 수 있다면 i+1..
![]()
제목을 잘못 적은 게 아니라, 문제 이름이 박성원이다.. 심지어 solved ac 공식 standard 문제! 풀이 이 문제는 3가지 부분 문제가 포함되어 있다고 볼 수 있다. 무려 길이가 최대 50인 자연수에 K로 나눈 나머지를 어떻게 구할 것인가 기약 분수 형태 출력은 어떻게 하는 게 빠를까? 위에 두 개 알았는데.. 그래서 어떻게 푸는데..? 우선 하나씩 해결해보자. 1. 큰 수(BigInteger) 나누기 우린 초등학교 3학년 때 구구단을 외우고, 4학년 때 나누는 방법을 배운다. 초4 수환이 큰 수 111111을 3으로 나누면 이런 방식으로 나눌 것이다. 이 과정을 살짝 프로그래밍적으로 분석하면 과정은 이러하다. 가장 앞자리 (자릿수가 가장 큰)부터 시작한다. 갖고 있는 수에 10을 곱한 후, ..
![]()
문제 링크 : https://www.acmicpc.net/problem/1946 문제 분류 - 그리디 알고리즘 풀이 우선 문제를 읽고, 지원자의 숫자 N의 제한이 10만이라는 점을 보고 빠르게 O(n^2)로 모든 지원자들을 계속해서 비교해나가는 풀이는 포기했다. 그렇다고 O(nlgn)의 방법으로 이분탐색을 하자니.. 딱히 절반 절반 줄여나갈 포인트가 생각이 안 났고 그다음 생각난 것이 아래와 같은 풀이이다. 먼저, 입력에서 각 지원자들의 성적 순위가 주어졌기 때문에 본능적으로 무언가 정렬을 해야 할 듯하다. 따라서 정렬을 하고 보니 두 성적 중 아무 성적이나 1위를 하고 있는 신입 사원은 어떻게 뽑든 반드시 선발되기 마련이다. 만약 성적이 (1, x)인 신입 사원이 선발이 되지 않았다면, 선발될 수 있는..
![]()
접두사를 찾는 문제로 트라이를 이용하여 간단하게 풀 수 있는 문제입니다. 트라이란? https://suhwanc.tistory.com/98 주어진 문자열들을 (0 ~ 9) 정렬한 후, 뒤에서 부터 트라이에 이 문자열이 있는지 find 하고 없으면 insert를 반복해 전화번호 목록의 일관성을 찾아내면 됩니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 #include #include #incl..
![]()
문제 링크 :https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 가장 간단한 LCS(Longest Common Subsequence)를 찾는 문제입니다. LCS 문자열 찾기 : https://suhwanc.tistory.com/80 LCS 알고리즘 1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다...
![]()
문제 링크 : https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다. 두 문자열 ABRACADABRA와 ECADADABRBCR www.acmicpc.net 풀이 가장 간단한 LCS(Longest Common Subsequence)를 찾는 문제입니다. LCS 문자열 찾기..
![]()
문제 링크 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 가장 대표적이고 기본적인 LCS 길이 찾기 문제이다. LCS 길이 찾기 방법 : https://suhwanc.tistory.com/80 LCS 알고리즘 1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다. 부분 문자열(Subsequence..
![]()
문제 링크 : https://www.acmicpc.net/problem/1042210422번: 괄호‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 ST도 올바른 괄호 문자열이다. (()())()은 올바른 괄호 문자열이지만 (()은 올바른 괄호 문자열이 아니다. 괄호 문자열이 주어졌을 때 올바른 괄호 문자열인지 확인하는 방법은 여러 www.acmicpc.net문제 설명괄호 문자열의 길이가 주어졌을 때, 올바른 괄호 문자열의 개수를 구하는 문제이다.출력에서 10억+7로 나눈 나머지를 출력..
![]()
문제 링크 : https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. www.acmicpc.net 문제 설명 N개의 숫자가 주어졌을 때, N-1 개의 수 가운데에 + 또는 - 를 추가하여 n번 째 수를 만들 수 있는 등식의 ..
