문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 코드 n, m = map(int, input().split()) hear = set() see = s..
전체 글
항공대 알고리즘 동아리 Koala 🥰https://www.acmicpc.net/problem/14724 14724번: 관리자는 누구? PROBRAIN, GROW, ARGOS, ADMIN, ANT, MOTION, SPG, COMON, ALMIGHTY중 동문 커뮤니티 관리자로 선발되는 후보가 소속한 동아리의 이름을 대문자로 출력한다. www.acmicpc.net [ 문 제 ] BIG 프로젝트로 동문 커뮤니티 웹사이트를 만들려고 한다. 동문 커뮤니티의 관리자는 홈페이지와 선후배 네트워크를 담당하는 일을 한다. 동문 커뮤니티 제작 프로젝트를 맡으신 Mr.Nam 교수님은 동문 커뮤니티 운영을 맡을 중요한 관리자를 뽑아달라는 부탁을 동아리에 전달했다. 회의 결과 다음과 같은 규칙으로 매년 각 동아리에서 관리자를 선출하자는 의견이 나왔다. 각 동아리에..
https://www.acmicpc.net/problem/1652 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 문제 N*N(1 n; for (int i = 0; i > arr[i]; } for (int i = 0; i = 2) r++; cnt = 0; } } if (cnt >= 2) r++; ..
https://www.acmicpc.net/problem/2153 2153번: 소수 단어 소수란 1과 자기 자신으로만 나누어떨어지는 수를 말한다. 예를 들면 1, 2, 3, 5, 17, 101, 10007 등이 소수이다. 이 문제에서는 편의상 1도 소수로 하자. 알파벳 대소문자로 이루어진 영어 단어가 하나 www.acmicpc.net 문제 소수란 1과 자기 자신으로만 나누어떨어지는 수를 말한다. 예를 들면 1, 2, 3, 5, 17, 101, 10007 등이 소수이다. 이 문제에서는 편의상 1도 소수로 하자. 알파벳 대소문자로 이루어진 영어 단어가 하나 있을 때, a를 1로, b를 2로, …, z를 26으로, A를 27로, …, Z를 52로 하여 그 합을 구한다. 예를 들어 cyworld는 합을 구하면 ..
문제 https://www.acmicpc.net/problem/9996 Algorithm 정규식을 활용한다. C++ 정규식에서 regex_match(str, e)는 정규표현식 e와 문자열 str이 일치함을 나타내고, 모든 문자열을 표현하기위한 정규식 e는 ".*"으로 나타낼 수 있다. input의 표현식에서 *를 .*으로 바꾸어 정규표현식을 생성한 뒤, regex_match를 수행한다. Code #include using namespace std; #define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0); typedef long long ll; typedef pair pii; typedef pair pll; int n; string str; void IN..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 문제 분석 난이도 골드 5 분류 투포인터 문제 풀이 전형적인 투 포인터 문제, 투 포인터를 사용하기 위해 정렬해준 뒤 앞 포인터와 뒤 포인터의 차이를 이용해 투 포인터를 진행시키면 되는 문제이다. 소스코드 from sys import stdin input=stdin.readline n,m=map(int,input().split()) arr=[int(input()) for i i..
https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; struct Birth { string name; int month; int day; int year; }; Birth arr[100]; bool compare(const Birth& a, ..
문제 링크 문제 링크 문제 풀이 '세 용액' 문제는 '용액' 문제의 심화 문제이다. 용액 문제 링크 '용액' 문제는 두 개의 용액을 선택하여, 두 용액의 값의 합이 0에 가장 가까운 경우의 조합을 구하는 문제이다. '세 용액' 문제를 풀기 전에 '용액' 문제의 풀이를 먼저 한 뒤 '세 용액' 문제의 풀이를 해보겠다. '용액' 문제 풀이 용액을 오름차순으로 정렬하고, 그 중 가장 값이 작은 용액을 A[i]로 칭하고 가장 값이 큰 용액을 A[j]라고 하자. 그 둘의 합이 양수인 경우를 생각해보자. 문제의 최적해는 용액의 합이 0에 가장 가까운 경우의 해이기 때문에 A[i]가 아닌 A[i+k]를 A[j]와 더하면 그 값이 더 커지기 때문에 최적해를 절대 찾을 수 없게 된다. 반대로, 둘의 합이 음수인 경우를 ..
회전 초밥 !https://d2gd6pc034wcta.cloudfront.net/tier/12.svg 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 17881 6251 4435 34.223% 문제 회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다. https://upload.acmicpc.net/f29f0bd9-6114-4543-aa72-797208dc9cdd/-/preview/ 새로 문을 연 회전 초밥 음식점이 불경기로 영업..
https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, ..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net N = int(input()) dp = [0, 1 ,2] for i in range(3, N + 1): dp.append(dp[i - 1] + dp[i - 2]) print(dp[N] % 10007)
문제 링크 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 접근 방법 이 문제를 완전 탐색으로 풀려고 한다면 모든 칸을 접근하며 정사각형 형태인지를 판별해야할 것 입니다. 정사각형 형태인지 판별하는 것은 쉽지만 정사각형의 길이가 1 ~ min(n, m)인 경우까지 확인해보아야 하므로 정확한 계산은 어렵지만 못해도 n * m * min(n, m)의 수행 시간을 가질 것이라고 생각되고 이는 최악의 경우에 1초를 넘길 것입니다. 따라서 이전의 정사각형 크기를 기록하여(dp 배열을 이용한 메모이제이션) 현재 위치에서의 최..